N-皇后问题

小橘子 2025年6月13日 5

0 评论

 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 }

输出：