算法：N-皇后问题
2024-08-28 07:02:01
一、八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8 × 8 的国际象棋棋盘上放置八个皇后（Queen），使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的N皇后摆放问题：这时棋盘的大小变为 N ×N，而皇后个数也变成 N。当且仅当 n = 1 或 n ≥ 4 时问题有解。
二、利用回溯法递归求解N-皇后问题
生成棋盘所有皇后摆放的可能配置，并打印满足给定约束的配置。回溯算法的思想是将皇后从最左边的列开始一一放置在不同的列中。 当我们将皇后放在一列中时，检查是否与已经放置的皇后发生冲突。 在当前列中，如果找到没有冲突的行，则将该行和列标记为解决方案的一部分。 如果由于冲突而找不到这样的行，那么我们将回溯并返回 false。
首先是从棋盘最左边的列开始摆放皇后。
算法主要内容：
1. 当 col = N 时，所有皇后摆放完毕，问题有解
2. 算法从每一列的每一行来推进问题的求解：
- a) 如果该位置 (i, j) 能把皇后无冲突的放进去，标记这个位置为 1，然后一直递归求解下一列的某行位置能否求解问题；
- b) 如果这个位置能摆放皇后则返回 true；
- c) 如果放置皇后并不能解决问题，取消标记此 (i, j)（回溯），然后转到步骤（a）尝试其他行。
3. 如果所有列所有行都尝试探索过后依然无解，返回 false（回溯）。
三、N-皇后问题的实现
检查当前位置放置皇后会与之前放置的皇后冲突。这里的时间复杂度为 O(N)。
1 /**
2 * 用于检查是否可以将Queen放在当前位置上
3 *
4 * @param board
5 * @param row
6 * @param col
7 * @return
8 */
9 private boolean isSafe(int[][] board, int row, int col) {
10 int i, j;
11
12 /* 是否在同一行（左侧） */
13 for (i = 0; i < col; i++)
14 if (board[row][i] == 1)
15 return false;
16
17 /* 是否在反对角线方向上 */
18 for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
19 if (board[i][j] == 1)
20 return false;
21
22 /* 是否在对角线方向上 */
23 for (i = row, j = col; j >= 0 && i < N; i++, j--)
24 if (board[i][j] == 1)
25 return false;
26
27 return true;
28 }
通过递归方式来探索问题的解，在所有位置尝试完之前，探索问题的解失败时通过回溯来寻找下一个皇后的摆放位置，回溯同时把摆放位置的标记复原。对于N皇后的时间复杂度，分析起来有点复杂，但从中可以分析其时间复杂度为 O(N3)。
1 /**
2 * 递归求解N-Queen问题
3 *
4 * @param board
5 * @param col
6 * @return
7 */
8 private boolean solveNQUtils(int[][] board, int col) {
9 /* 如果所有皇后都被放置, 然后返回true */
10 if (col >= N)
11 return true;
12
13 /* 考虑当前col能否摆放Queen */
14 for (int i = 0; i < N; i++) {
15 /* 当前位置是否能摆放Queen */
16 if (isSafe(board, i, col)) {
17 board[i][col] = 1;
18
19 /* 再次摆放Queen, 如果成功直接返回true */
20 if (solveNQUtils(board, col + 1)) {
21 return true;
22 }
23
24 /* 这是在某列无法放Queen回溯时把queen移走 */
25 board[i][col] = 0;
26 }
27 }
28
29 return false;
30 }
本文源代码：
1 package algorithm;
2
3 /**
4 * N皇后问题，回溯法，简单分析一下，时间复杂度大概为 O(N^3)
5 */
6 public class NQueenProblem {
7 private final int N = 8;
8
9 /**
10 * 打印符合条件的摆放棋盘
11 *
12 * @param board
13 */
14 private void printSolution(int[][] board) {
15 for (int i = 0; i < N; i++) {
16 for (int j = 0; j < N; j++) {
17 System.out.print(" " + board[i][j] + " ");
18 }
19 System.out.println();
20 }
21 }
22
23 /**
24 * 用于检查是否可以将Queen放在当前位置上
25 *
26 * @param board
27 * @param row
28 * @param col
29 * @return
30 */
31 private boolean isSafe(int[][] board, int row, int col) {
32 int i, j;
33
34 /* 是否在同一行（左侧） */
35 for (i = 0; i < col; i++)
36 if (board[row][i] == 1)
37 return false;
38
39 /* 是否在反对角线方向上 */
40 for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
41 if (board[i][j] == 1)
42 return false;
43
44 /* 是否在对角线方向上 */
45 for (i = row, j = col; j >= 0 && i < N; i++, j--)
46 if (board[i][j] == 1)
47 return false;
48
49 return true;
50 }
51
52 /**
53 * 递归求解N-Queen问题
54 *
55 * @param board
56 * @param col
57 * @return
58 */
59 private boolean solveNQUtils(int[][] board, int col) {
60 /* 如果所有皇后都被放置, 然后返回true */
61 if (col >= N)
62 return true;
63
64 /* 考虑当前col能否摆放Queen */
65 for (int i = 0; i < N; i++) {
66 /* 当前位置是否能摆放Queen */
67 if (isSafe(board, i, col)) {
68 board[i][col] = 1;
69
70 /* 再次摆放Queen, 如果成功直接返回true */
71 if (solveNQUtils(board, col + 1)) {
72 return true;
73 }
74
75 /* 这是在某列无法放Queen回溯时把queen移走 */
76 board[i][col] = 0;
77 }
78 }
79
80 return false;
81 }
82
83 /**
84 * 解决并打印N-Queen的问题
85 *
86 * @return
87 */
88 private boolean solveNQ() {
89 int[][] board = new int[N][N];
90
91 if (!solveNQUtils(board, 0)) {
92 System.out.println("Solution does not exist");
93 return false;
94 }
95
96 printSolution(board);
97 return true;
98 }
99
100 public static void main(String[] args) {
101 NQueenProblem queen = new NQueenProblem();
102 queen.solveNQ();
103 }
104 }
最新文章
- JavaScript知识点总结（命名规范，变量的作用域）
- Eclipse版本android 65535解决方案(原理等同android studio现在的分包方式)
- [已解决] github merge指定commit
- Atitit 异常机制与异常处理的原理与概论
- django使用gmail
- SqlServer int型转varchar型 出现*号
- VS2010 VB 连接数据库SQL2005
- 如何避免JSP页面自动生成session对象？为什么要这么做？
- python_json常用的方法
- c语言 创建链表
- mysql2 - 基础
- linux目录详细介绍
- [转]innodb的锁时间
- BZOJ4482[Jsoi2015]套娃——贪心+set
- vue使用vue-awesome-swiper及一些问题
- FTP相关、用vsftpd搭建ftp、xshell使用xftp传输文件、使用pure-ftpd搭建ftp服务
- Python高级网络编程系列之第一篇
- Muse UI 样式
- windows7触屏编程
- smarty学习——变量