Challenge of eight queens

Consider such a favorite task of understanding algorithms, as the “eight queens problem”. The classic definition is “to place 8 queens on a chessboard so that neither of them hits the other”. Ok, the problem is very popular at various interviews, and Wikipedia immediately gives us a solution on my favorite Python .

And this is probably the right decision from the point of view of an ordinary person, but absolutely meaningless from the point of view of a hacker, and now I'll tell you why:
')
Let us analyze the algorithm: a classical search with a return is used, we represent the solution area in the form of a graph, each vertex of which is a queen position in which he is not in combat and does not hit the queens already placed on the board, we just need to collect all the "branches" consisting of exactly eight peaks. As a method of searching for these “branches”, the author proposes to us a classic search algorithm wide, i.e. The traversal order of the graph will look like this:



And as soon as the algorithm works, we get all possible solutions.

So what's the problem? In our case, for the 8x8 board, we get 92 different solutions, but imagine that, as is often the case in real problems, we do not know the size of the board. If the board is 25x25, as in Tai Shogi , then the number of solutions will already be 275,986,683,743,434.

Table, the number of decisions depending on the size of the board:

n :	one	2	3	four	five	6	7	eight	9	ten	eleven	12	13	14	..	24	25	26
unique:	one	0	0	one	2	one	6	12	46	92	341	1,787	9,233	45.752	..	28,439,272,956,934	275,986,683,743,434	2,789,712,466,510,289
different:	one	0	0	2	ten	four	40	92	352	724	2,680	14,200	73,712	365,596	..	227,514,171,973,736	2,207,893,435,808,352	22,317,699,616,364,044

What does this mean for our script? And the fact that he will go into a very long search, and since he has to keep all the decisions in mind, after 15 minutes Python will eat up 300 megabytes of memory. Who has a powerful processor and a large amount of RAM can check whether this process is completed at all ...

And all we needed to solve such a problem was to choose the right algorithm for traversing the graph, which in our case would be the usual search in depth, then the traversal of the graph would occur in this order:



And the code would be much simpler, and even after 15 minutes the script would eat exactly as much memory as a second after launch. And here is how its implementation would look like in Python:

def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: for n_row in range(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width, sol+[n_row]) def safe_queen(new_row, new_col, sol): for col in range(len(sol)): if (sol[col] == new_row or abs(col - new_col) == abs(sol[col] - new_row)): return 0 return 1 if __name__ == "__main__": for n in range(8): rc_queens(1, 8, [n]) 

PS This is just a look at the problem from the side of the hacker, can someone offer a view from the side of “theoretical computer science”?