回溯算法n皇后問題

N-皇后問題 (N - Queen's problem)

The n – queen problem is the generalized problem of 8-queens or 4 – queen’s problem. Here, the n – queens are placed on a n * n chess board, which means that the chessboard has n rows and n columns and the n queens are placed on thus n * n chessboard such that no two queens are placed in the same row or in the same column or in same diagonal. So that, no two queens attack each other.

n皇后問題是8皇后或4 皇后問題的廣義問題 。 在這里，將n –皇后放置在* n棋盤上，這意味著該棋board具有n行和n列，并且將n個皇后放置在n * n棋盤上，這樣就不會在同一行中放置兩個皇后。在同一列或同一對角線中。 因此，沒有兩個女王互相攻擊。

Here, we suppose that the queen i is to be placed in row i. We can say that 1 queen is placed in the first row only but can have columns from 1, 2... n so that they satisfy all the explicit and implicit constraints.

在這里，我們假設將女王i放在第i行。 我們可以說1個皇后只放在第一行，但是可以有1、2 ... n個列，這樣它們就可以滿足所有顯式和隱式約束。

All solutions to the n – queen’s problem can be therefore represented as n – tuples (x1, x2... xn) where xi is the column on which queen i is to be placed.

因此，n- 皇后問題的所有解決方案都可以表示為n-元組(x1，x2 ... xn)，其中xi是放置女王i的列。

The explicit constraints using this formulation are Si = {1, 2, 3... n-1, n}, where 1 <= I <= n. Therefore, the solution space consists of n?n n- tuples. Now, while considering the implicit constraints, that no two xi’s can be same i.e., two queens cannot be in the same row, same column, or in same diagonal. So, each xi should be different. Now by the above constraint, the solution is the permutations of the n – tuples (1, 2, 3, 4... n-1, n).

使用此公式的顯式約束為Si = {1,2,3 ... n-1，n}，其中1 <= I <= n。 因此，解空間由n?n個元組組成。 現在，在考慮隱式約束時，沒有兩個xi可以相同，即兩個皇后不能在同一行，同一列或同一對角線中。 因此，每個xi應該不同。 現在，根據上述約束，解決方案是n個元組的排列(1、2、3、4 ... n-1，n)。

算法 (Algorithm )

For all the solutions of the n - queen’s problem...

對于n-皇后問題的所有解...

1. Algorithm N Queen (k, n) 2. // Using backtracking, this procedure prints all possible placements of 3. // n- queens on the n*n chess board so that they are non-attacking. 4. { 5. For I = 1 to n do 6. { 7. If Place (k, i) then 8. { 9. X[k] = I; 10. If (k = n) then write (x[1: n ]) ; 11. Else N Queens (k+1, n); 12. } 13. } 14. }

翻譯自: https://www.includehelp.com/algorithms/n-queens-problem-and-solution-using-backtracking-algorithm.aspx

回溯算法n皇后問題

總結

以上是生活随笔為你收集整理的回溯算法n皇后问题_使用回溯算法的N Queen问题和解决方案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。