N-皇后问题是一个经典的计算机科学和数学问题，其目标是在一个N×N的棋盘上放置N个皇后，使得它们彼此之间互不攻击，即没有两个皇后在同一行、同一列或同一斜线上。
这个问题最早由卡尔·弗里德里希·高斯于1850年提出，它在计算机科学领域中被广泛研究，被用作算法和人工智能的基础问题。
问题描述
给定一个N×N的棋盘，要求在每一行放置一个皇后，以确保它们不会互相攻击。攻击的条件包括：
- 同一行：两个皇后不能在同一行上。
- 同一列：两个皇后不能在同一列上。
- 同一对角线：两个皇后不能在同一对角线上（包括正对角线和反对角线）。
解决方法
解决N-皇后问题的一种常见方法是使用回溯算法。回溯算法是一种深度优先搜索方法，它通过逐行尝试放置皇后，然后检查是否满足攻击条件来解决问题。
如果某个皇后的位置导致了冲突，就会回溯到前一行并尝试放置皇后的不同位置，直到找到一个合适的解决方案或确定无解。
示例
python
1 def solve_n_queens(n): 2 def is_safe(board, row, col): 3 # 检查同一列上是否有皇后 4 for i in range(row): 5 if board[i][col] == 'Q': 6 return False 7 8 # 检查左上方斜线是否有皇后 9 i, j = row, col 10 while i >= 0 and j >= 0: 11 if board[i][j] == 'Q': 12 return False 13 i -= 1 14 j -= 1 15 16 # 检查右上方斜线是否有皇后 17 i, j = row, col 18 while i >= 0 and j < n: 19 if board[i][j] == 'Q': 20 return False 21 i -= 1 22 j += 1 23 24 return True 25 26 def backtrack(row): 27 if row == n: 28 solutions.append(["".join(row) for row in board]) # 存放结果，每个结果通过""连接 29 return 30 31 for col in range(n): 32 if is_safe(board, row, col): 33 board[row][col] = 'Q' 34 backtrack(row + 1) 35 board[row][col] = '.' # 回溯 36 # 1. 初始化棋盘，都是. 37 board = [['.' for _ in range(n)] for _ in range(n)] 38 solutions = [] # 2. 存放所有结果 39 backtrack(0) 40 return solutions 41 42 43 def print_solutions(solutions): 44 for solution in solutions: 45 for row in solution: 46 print(row) 47 print() 48 49 50 n = 8 # 例如，解决8皇后问题 51 solutions = solve_n_queens(n) 52 print_solutions(solutions)
输出结果：
Q....... ....Q... .......Q .....Q.. ..Q..... ......Q. .Q...... ...Q.... Q....... .....Q.. .......Q ..Q..... ......Q. ...Q.... .Q...... ....Q... Q....... ......Q. ...Q.... .....Q.. .......Q .Q...... ....Q... ..Q..... Q....... ......Q. ....Q... .......Q .Q...... ...Q.... .....Q.. ..Q..... .Q...... ...Q.... .....Q.. .......Q ..Q..... Q....... ......Q. ....Q... .Q...... ....Q... ......Q. Q....... ..Q..... .......Q .....Q.. ...Q.... .Q...... ....Q... ......Q. ...Q.... Q....... .......Q .....Q.. ..Q..... .Q...... .....Q.. Q....... ......Q. ...Q.... .......Q ..Q..... ....Q... .Q...... .....Q.. .......Q ..Q..... Q....... ...Q.... ......Q. ....Q... .Q...... ......Q. ..Q..... .....Q.. .......Q ....Q... Q....... ...Q.... .Q...... ......Q. ....Q... .......Q Q....... ...Q.... .....Q.. ..Q..... .Q...... .......Q .....Q.. Q....... ..Q..... ....Q... ......Q. ...Q.... ..Q..... Q....... ......Q. ....Q... .......Q .Q...... ...Q.... .....Q.. ..Q..... ....Q... .Q...... .......Q Q....... ......Q. ...Q.... .....Q.. ..Q..... ....Q... .Q...... .......Q .....Q.. ...Q.... ......Q. Q....... ..Q..... ....Q... ......Q. Q....... ...Q.... .Q...... .......Q .....Q.. ..Q..... ....Q... .......Q ...Q.... Q....... ......Q. .Q...... .....Q.. ..Q..... .....Q.. .Q...... ....Q... .......Q Q....... ......Q. ...Q.... ..Q..... .....Q.. .Q...... ......Q. Q....... ...Q.... .......Q ....Q... ..Q..... .....Q.. .Q...... ......Q. ....Q... Q....... .......Q ...Q.... ..Q..... .....Q.. ...Q.... Q....... .......Q ....Q... ......Q. .Q...... ..Q..... .....Q.. ...Q.... .Q...... .......Q ....Q... ......Q. Q....... ..Q..... .....Q.. .......Q Q....... ...Q.... ......Q. ....Q... .Q...... ..Q..... .....Q.. .......Q Q....... ....Q... ......Q. .Q...... ...Q.... ..Q..... .....Q.. .......Q .Q...... ...Q.... Q....... ......Q. ....Q... ..Q..... ......Q. .Q...... .......Q ....Q... Q....... ...Q.... .....Q.. ..Q..... ......Q. .Q...... .......Q .....Q.. ...Q.... Q....... ....Q... ..Q..... .......Q ...Q.... ......Q. Q....... .....Q.. .Q...... ....Q... ...Q.... Q....... ....Q... .......Q .Q...... ......Q. ..Q..... .....Q.. ...Q.... Q....... ....Q... .......Q .....Q.. ..Q..... ......Q. .Q...... ...Q.... .Q...... ....Q... .......Q .....Q.. Q....... ..Q..... ......Q. ...Q.... .Q...... ......Q. ..Q..... .....Q.. .......Q Q....... ....Q... ...Q.... .Q...... ......Q. ..Q..... .....Q.. .......Q ....Q... Q....... ...Q.... .Q...... ......Q. ....Q... Q....... .......Q .....Q.. ..Q..... ...Q.... .Q...... .......Q ....Q... ......Q. Q....... ..Q..... .....Q.. ...Q.... .Q...... .......Q .....Q.. Q....... ..Q..... ....Q... ......Q. ...Q.... .....Q.. Q....... ....Q... .Q...... .......Q ..Q..... ......Q. ...Q.... .....Q.. .......Q .Q...... ......Q. Q....... ..Q..... ....Q... ...Q.... .....Q.. .......Q ..Q..... Q....... ......Q. ....Q... .Q...... ...Q.... ......Q. Q....... .......Q ....Q... .Q...... .....Q.. ..Q..... ...Q.... ......Q. ..Q..... .......Q .Q...... ....Q... Q....... .....Q.. ...Q.... ......Q. ....Q... .Q...... .....Q.. Q....... ..Q..... .......Q ...Q.... ......Q. ....Q... ..Q..... Q....... .....Q.. .......Q .Q...... ...Q.... .......Q Q....... ..Q..... .....Q.. .Q...... ......Q. ....Q... ...Q.... .......Q Q....... ....Q... ......Q. .Q...... .....Q.. ..Q..... ...Q.... .......Q ....Q... ..Q..... Q....... ......Q. .Q...... .....Q.. ....Q... Q....... ...Q.... .....Q.. .......Q .Q...... ......Q. ..Q..... ....Q... Q....... .......Q ...Q.... .Q...... ......Q. ..Q..... .....Q.. ....Q... Q....... .......Q .....Q.. ..Q..... ......Q. .Q...... ...Q.... ....Q... .Q...... ...Q.... .....Q.. .......Q ..Q..... Q....... ......Q. ....Q... .Q...... ...Q.... ......Q. ..Q..... .......Q .....Q.. Q....... ....Q... .Q...... .....Q.. Q....... ......Q. ...Q.... .......Q ..Q..... ....Q... .Q...... .......Q Q....... ...Q.... ......Q. ..Q..... .....Q.. ....Q... ..Q..... Q....... .....Q.. .......Q .Q...... ...Q.... ......Q. ....Q... ..Q..... Q....... ......Q. .Q...... .......Q .....Q.. ...Q.... ....Q... ..Q..... .......Q ...Q.... ......Q. Q....... .....Q.. .Q...... ....Q... ......Q. Q....... ..Q..... .......Q .....Q.. ...Q.... .Q...... ....Q... ......Q. Q....... ...Q.... .Q...... .......Q .....Q.. ..Q..... ....Q... ......Q. .Q...... ...Q.... .......Q Q....... ..Q..... .....Q.. ....Q... ......Q. .Q...... .....Q.. ..Q..... Q....... ...Q.... .......Q ....Q... ......Q. .Q...... .....Q.. ..Q..... Q....... .......Q ...Q.... ....Q... ......Q. ...Q.... Q....... ..Q..... .......Q .....Q.. .Q...... ....Q... .......Q ...Q.... Q....... ..Q..... .....Q.. .Q...... ......Q. ....Q... .......Q ...Q.... Q....... ......Q. .Q...... .....Q.. ..Q..... .....Q.. Q....... ....Q... .Q...... .......Q ..Q..... ......Q. ...Q.... .....Q.. .Q...... ......Q. Q....... ..Q..... ....Q... .......Q ...Q.... .....Q.. .Q...... ......Q. Q....... ...Q.... .......Q ....Q... ..Q..... .....Q.. ..Q..... Q....... ......Q. ....Q... .......Q .Q...... ...Q.... .....Q.. ..Q..... Q....... .......Q ...Q.... .Q...... ......Q. ....Q... .....Q.. ..Q..... Q....... .......Q ....Q... .Q...... ...Q.... ......Q. .....Q.. ..Q..... ....Q... ......Q. Q....... ...Q.... .Q...... .......Q .....Q.. ..Q..... ....Q... .......Q Q....... ...Q.... .Q...... ......Q. .....Q.. ..Q..... ......Q. .Q...... ...Q.... .......Q Q....... ....Q... .....Q.. ..Q..... ......Q. .Q...... .......Q ....Q... Q....... ...Q.... .....Q.. ..Q..... ......Q. ...Q.... Q....... .......Q .Q...... ....Q... .....Q.. ...Q.... Q....... ....Q... .......Q .Q...... ......Q. ..Q..... .....Q.. ...Q.... .Q...... .......Q ....Q... ......Q. Q....... ..Q..... .....Q.. ...Q.... ......Q. Q....... ..Q..... ....Q... .Q...... .......Q .....Q.. ...Q.... ......Q. Q....... .......Q .Q...... ....Q... ..Q..... .....Q.. .......Q .Q...... ...Q.... Q....... ......Q. ....Q... ..Q..... ......Q. Q....... ..Q..... .......Q .....Q.. ...Q.... .Q...... ....Q... ......Q. .Q...... ...Q.... Q....... .......Q ....Q... ..Q..... .....Q.. ......Q. .Q...... .....Q.. ..Q..... Q....... ...Q.... .......Q ....Q... ......Q. ..Q..... Q....... .....Q.. .......Q ....Q... .Q...... ...Q.... ......Q. ..Q..... .......Q .Q...... ....Q... Q....... .....Q.. ...Q.... ......Q. ...Q.... .Q...... ....Q... .......Q Q....... ..Q..... .....Q.. ......Q. ...Q.... .Q...... .......Q .....Q.. Q....... ..Q..... ....Q... ......Q. ....Q... ..Q..... Q....... .....Q.. .......Q .Q...... ...Q.... .......Q .Q...... ...Q.... Q....... ......Q. ....Q... ..Q..... .....Q.. .......Q .Q...... ....Q... ..Q..... Q....... ......Q. ...Q.... .....Q.. .......Q ..Q..... Q....... .....Q.. .Q...... ....Q... ......Q. ...Q.... .......Q ...Q.... Q....... ..Q..... .....Q.. .Q...... ......Q. ....Q...
这段代码定义了一个solve_n_queens函数，用于解决N-皇后问题。主要思路是使用回溯法，在每一行依次尝试放置皇后，如果当前位置是安全的（不受攻击），就放置皇后并继续递归下一行。如果无法放置皇后，就回溯到上一行，重新尝试其他位置。当放置了N个皇后时，就找到了一个解。
注意事项：
is_safe函数用于检查当前位置是否安全。它会检查同一列、左上方斜线和右上方斜线是否有皇后。- 使用一个二维数组
board来表示棋盘，其中'.'表示空白格，'Q'表示皇后。 backtrack函数是核心的回溯递归函数，它递归地尝试放置皇后并搜索解决方案。- 最终，函数返回所有的解决方案，并通过
print_solutions函数打印出来。
Javascript
1 function solveNQueens(n) { 2 const result = []; 3 // 二维数组，模拟棋盘 4 const board = new Array(n).fill('.').map(() => new Array(n).fill('.')); 5 6 function isSafe(row, col) { // 判断当前方法是否可行，true 可行，false不行 7 // 检查同一列是否有皇后 8 for (let i = 0; i < row; i++) { 9 if (board[i][col] === 'Q') { 10 return false; 11 } 12 } 13 14 // 检查左上对角线 15 for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) { 16 if (board[i][j] === 'Q') { 17 return false; 18 } 19 } 20 21 // 检查右上对角线 22 for (let i = row, j = col; i >= 0 && j < n; i--, j++) { 23 if (board[i][j] === 'Q') { 24 return false; 25 } 26 } 27 28 return true; 29 } 30 31 function backtrack(row) { 32 if (row === n) { 33 // 找到一种解决方案，将棋盘添加到结果中 34 result.push([...board.map(row => row.join(''))]); 35 return; 36 } 37 38 for (let col = 0; col < n; col++) { 39 if (isSafe(row, col)) { 40 board[row][col] = 'Q'; 41 backtrack(row + 1); 42 board[row][col] = '.'; // 重置 43 } 44 } 45 } 46 47 backtrack(0); 48 49 return result; 50 } 51 52 // 通过调用solveNQueens来解决N-皇后问题 53 const n = 4; // 4-皇后问题的示例 54 const solutions = solveNQueens(n); 55 56 // 打印解决方案 57 for (const solution of solutions) { 58 for (const row of solution) { 59 console.log(row); 60 } 61 console.log('\n'); 62 }
输出：
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
Java
1 package org.allen.data.structure.suanfa; 2 3 public class NQueens { 4 private int[] queens; // 存储每一行皇后的列索引 5 private int n; // 棋盘大小 6 7 public NQueens(int n) { 8 this.n = n; 9 this.queens = new int[n]; 10 } 11 12 // 检查在第row行和col列放置皇后是否合法 13 private boolean isSafe(int row, int col) { 14 for (int i = 0; i < row; i++) { 15 if (queens[i] == col || // 检查同一列 16 queens[i] - i == col - row || // 检查左上至右下对角线 17 queens[i] + i == col + row) { // 检查右上至左下对角线 18 return false; 19 } 20 } 21 return true; 22 } 23 24 // 递归求解N-皇后问题 25 private void solveNQueens(int row) { 26 if (row == n) { // 所有皇后都已放置完毕 27 printSolution(); 28 return; 29 } 30 31 for (int col = 0; col < n; col++) { 32 if (isSafe(row, col)) { 33 queens[row] = col; // 放置皇后 34 solveNQueens(row + 1); // 递归放置下一行的皇后 35 queens[row] = -1; // 回溯，撤销皇后的位置 36 } 37 } 38 } 39 40 // 打印解决方案 41 private void printSolution() { 42 for (int i = 0; i < n; i++) { 43 for (int j = 0; j < n; j++) { 44 if (queens[i] == j) { 45 System.out.print("Q "); 46 } else { 47 System.out.print(". "); 48 } 49 } 50 System.out.println(); 51 } 52 System.out.println(); 53 } 54 55 public void solve() { 56 solveNQueens(0); // 从第一行开始解决问题 57 } 58 59 public static void main(String[] args) { 60 int n = 4; // 棋盘大小 61 NQueens solver = new NQueens(n); 62 solver.solve(); 63 } 64 }
输出：
. Q . . . . . Q Q . . . . . Q . . . Q . Q . . . . . . Q . Q . .