递归与动态规划——N皇后问题

Posted on | In ,

问题：N皇后问题是在N*N的棋盘上要摆N个皇后，要求任意两个皇后不同行、不同列，也不在同一斜线上。给定一个整数n，返回n皇后的摆法有多少种。
例：n<1，返回0.
n=1，返回1.
n=2或3，2皇后和3皇后无论怎么摆都不行，返回0.
n=8，返回92.（经典八皇后问题）

分析：如果在weizhi(i,j)放置了一个皇后，接下来在哪些位置不能放皇后呢？

  1. 整个第i行不能放；
  2. 整个第j列不能放；
  3. 同一斜线位置(a,b)上不能放，即|a-i|==|b-j|。

实现：

  1. 把逐行放置皇后设置成递归问题，避开条件1中的位置。
  2. 用一个数组record保存已经放置皇后的位置，record[i]表示第i行皇后所在的列。
  3. 在递归计算到第i行第j列时，查看record0,…k的值（0,..k行，record[0,..k]列），
    1）若有record[k]==j，则(i,j)位置不能放置；（在同一列了）
    2）若|k-i|==|record[k]-j|，则(i,j)位置也不能放置。（在同一行了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class NQueen {
	/**
	 * 计算n皇后问题，以后有多少种放置方法
	 * @param n 皇后个数
	 * @return 总的放置方法数
	 */
	public int num (int n) {
		if (n < 1) {
			return 0;
		}
		int[] record = new int[n]; //保存已经放置皇后的位置
		return process(0, record, n); //从第0行开始遍历
	}
	/**
	 * 逐行递归计算总的放置方法数
	 * @param i 行数
	 * @param record 保存已经放置皇后的位置
	 * @param n 皇后个数
	 * @return 总的放置方法数
	 */
	public int process(int i, int[] record, int n) {
		if (i == n) {
			return 1; //遍历到最后一行，返回
		}
		int rst = 0; // 记录总的方法数
		for (int j = 0; j < n; j++) 
			if (isValid(record, i, j)) {
				record[i] = j; //将第i行j列的记录加到record数组中
				rst += process(i + 1, record, n); //开始遍历下一行
			}
		return rst;
	}
	/**
	 * 判断当前位置(i,j)是否有效
	 * @param record 已经记录了有效的皇后位置
	 * @param i 第i行
	 * @param j 第j列
	 * @return 是否有效
	 */
	public boolean isValid(int[] record, int i, int j) {
		for (int k = 0; k < i; k++) { //k是记录了有效皇后位置record数组的行
			if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
				return false;
			}
		}
		return true;
	}
	//Test
	    public static void main (String[] args){  
	        NQueen em = new NQueen();  
	        System.out.println(em.num(8));
	    }  
}