The eight queens problem is a question with chess as the background: how to place eight queens on an 8×8 chess board so that no queen can directly eat other queens? In order to achieve this purpose, any two queens are not in the same horizontal, vertical or diagonal. The eight queen problem can be extended to the more general N-Queens Problem.

more information about n-queens problem please google it.

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12

intNQueens(int n){ int upperlim = (1 << n) - 1, sum = 0; std::function<void(int,int,int)> dfs = [&](int row,int ld,int rd) { if(row == upperlim) {++sum;return;} for(int cur = upperlim & (~(row|ld|rd)),pos = 0;cur ;dfs(row|pos,(ld|pos)<<1,(rd|pos)>>1)) { pos = cur & (-cur); cur -= pos; } }; dfs(0,0,0); return sum; }

The first round of search is completed, there is a kind of thought is the depth first search, is to find a solution and then press forward to the enemy’s capital to find second solution, because the eight queens problem belongs to the scope of the graph, so the idea of graph theory can be found in this problem.