N-皇后问题

共计 11858 个字符，预计需要花费 30 分钟才能阅读完成。

N- 皇后问题是一个经典的计算机科学和数学问题，其目标是在一个 N×N 的棋盘上放置 N 个皇后，使得它们彼此之间互不攻击，即没有两个皇后在同一行、同一列或同一斜线上。

这个问题最早由卡尔·弗里德里希·高斯于 1850 年提出，它在计算机科学领域中被广泛研究，被用作算法和人工智能的基础问题。

问题描述

给定一个 N×N 的棋盘，要求在每一行放置一个皇后，以确保它们不会互相攻击。攻击的条件包括：

1. 同一行：两个皇后不能在同一行上。
2. 同一列：两个皇后不能在同一列上。
3. 同一对角线：两个皇后不能在同一对角线上（包括正对角线和反对角线）。

解决方法

解决 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)

输出结果：

这段代码定义了一个 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 }

输出：

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 }

输出：