回溯法求解N皇后问题（Java实现）

回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。

为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。

光说不做没意思，用学过的算法题来运用一下。

N 皇后问题：在一个 N * N 的国际象棋棋盘中，怎样放置 N 个皇后才能使 N 个皇后之间不会互相有威胁而共同存在于棋局中，即在 N * N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。

求解思路：最容易想到的方法就是有序地从第 1 列的第 1 行开始，尝试放上一个皇后，然后再尝试第 2 列的第几行能够放上一个皇后，如果第 2 列也放置成功，那么就继续放置第 3 列，如果此时第 3 列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。

需要解决的问题：如何表示一个 N * N 方格棋盘能够更有效？怎样测试当前所走的试探路径是否符合要求？这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结构有利于简化编程求解问题的难度。

为此，我们使用以下的数据结构：

int column[col] = row 表示第 col 列的第 row 行放置一个皇后

boolean rowExists[i] = true 表示第 i 行有皇后

boolean a[i] = true 表示右高左低的第 i 条斜线有皇后（按 →  ↓ 顺序从1~ 2*N -1 依次编号）

boolean b[i] = true 表示左高右低的第 i 条斜线有皇后（按 →  ↑ 顺序从1~ 2*N -1 依次编号）

对应这个数据结构的算法实现如下：

1. /**  
2.  * 回溯法求解 N 皇后问题  
3.  * @author haolloyin  
4.  */ 
5. public class N_Queens {  
6.       
7.     // 皇后的个数  
8.     private int queensNum = 4;  
9.  
10.     // column[i] = j 表示第 i 列的第 j 行放置一个皇后  
11.     private int[] queens = new int[queensNum + 1];  
12.  
13.     // rowExists[i] = true 表示第 i 行有皇后  
14.     private boolean[] rowExists = new boolean[queensNum + 1];  
15.  
16.     // a[i] = true 表示右高左低的第 i 条斜线有皇后  
17.     private boolean[] a = new boolean[queensNum * 2];  
18.  
19.     // b[i] = true 表示左高右低的第 i 条斜线有皇后  
20.     private boolean[] b = new boolean[queensNum * 2];  
21.       
22.     // 初始化变量  
23.     private void init() {  
24.         for (int i = 0; i < queensNum + 1; i++) {  
25.             rowExists[i] = false;  
26.         }  
27.           
28.         for(int i = 0; i < queensNum * 2; i++) {  
29.             a[i] = b[i] = false;  
30.         }  
31.     }  
32.  
33.     // 判断该位置是否已经存在一个皇后,存在则返回 true  
34.     private boolean isExists(int row, int col) {  
35.         return (rowExists[row] || a[row + col - 1] || b[queensNum + col - row]);  
36.     }  
37.  
38.     // 主方法：测试放置皇后  
39.     public void testing(int column) {  
40.  
41.         // 遍历每一行  
42.         for (int row = 1; row < queensNum + 1; row++) {  
43.             // 如果第 row 行第 column 列可以放置皇后  
44.             if (!isExists(row, column)) {  
45.                 // 设置第 row 行第 column 列有皇后   
46.                 queens[column] = row;  
47.                 // 设置以第 row 行第 column 列为交叉点的斜线不可放置皇后  
48.                 rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = true;  
49.                   
50.                 // 全部尝试过，打印  
51.                 if(column == queensNum) {  
52.                     for(int col = 1; col <= queensNum; col++) {  
53.                         System.out.print("("+col + "," + queens[col] + ")  ");  
54.                     }  
55.                     System.out.println();  
56.                 }else {  
57.                     // 放置下一列的皇后  
58.                     testing(column + 1);  
59.                 }  
60.                 // 撤销上一步所放置的皇后，即回溯  
61.                 rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = false;  
62.             }  
63.         }  
64.     }  
65.       
66.     // 测试  
67.     public static void main(String[] args) {  
68.         N_Queens queen = new N_Queens();  
69.         queen.init();  
70.         // 从第 1 列开始求解  
71.         queen.testing(1);  
72.     }  
73. } 

当 N = 8 时，求解结果如下（注：横坐标为 列数， 纵坐标为 行数）：