算法
33 分钟 读完 (大约 5018 个字)

八皇后(回溯算法)

概述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上（反斜线），问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n × n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

解题思路

可归纳问题的条件为，8皇后之间需满足：

  • 不在同一行上
  • 不在同一列上
  • 不在同一斜线上
  • 不在同一反斜线上

    解题思路

  1. 从第一行第一列开始逐行摆放棋子，找到符合条件的位置放置棋子。
  2. 接着就到下一行遍历下一个棋子的合适位置，遍历过程中有一个条件是绝对符合的——就是下一个棋子摆放位置与前面的棋子不在同一行。
  3. 在当前行，遍历列。判断当前位置是否符合棋子的条件，如果符合条件，则到下一行，继续寻找棋子合适的位置；如果不符合，则同行下一列继续判断，直到最后一列。
  4. 如果一个行的所有位置都不合适，就返回上一行，清除上一行的摆放记录，并且继续该行的其他位置遍历，尝试摆放下一位置的皇后（回溯算法的核心），当我们顺利遍历到最后一行，且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加1次八皇后可行方案的个数。
  5. 然后继续遍历该行（因为递归函数，前面的行并没有改变，递归是从最后函数开始，所以前面行数据没有变化，最后一行重新遍历，寻找皇后的位置）其他位置是否有合适的，如果没有，则返回上一行，清除上一行的摆放记录，遍历该行其他位置，依此下去。
  6. 这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。

    程序代码

    程序代码分2类：代码1和代码2。

    代码1

    使用：回溯算法，递归算法。
    时间：耗时【15豪秒】。
    截图：queen[]存：y行x列，皇后的位置。
    1
    2
    3
    1  2  3
    1  2  3
    1  2  3

左下->右上：(1，1)，(2，2)，(3，3)
左上->右下：(3，1)，(2，2)，(1，3)
左下->右上：任意2点都满足i1-i2=j1-j2，演变i1-j1=i2-j2
左上->右下：任意2点(i1，j1)和(i2，j2)都满足i1+j1=i2+j2

则定义对角线2个数组：
rup = new int[(2 * 8) + 1]; i+j,这i属于(1-8),j属于(1-8),i+j范围(1-16)
lup = new int[(2 * 8) + 1]; i-j,这为了避免出现负数，程序里在这里+8。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package demo1;

/**
 * 百度百科-八皇后
 * 92个结果
 *
 */
public class Queen {
	// 同列是否有皇后，1表示有，0表示没有
	private int[] column;
	//左下至右上是否有皇后，对角线
	private int[] rup;
	//左上至右下是否有皇后，反对角线
	private int[] lup;
	// queen[i]=j：i行j列
	private int[] queen;
	// 解答编号
	private int num;

	// 生成8*8队列，初始定义全部无皇后
	public Queen() {
		column = new int[8 + 1];
		
	 /* 1  2  3
		1  2  3
		1  2  3

		左下->右上：（1，1），（2，2），（3，3）
		左上->右下：（3，1），（2，2），（1，3）

		左下->右上：任意2点都满足i1-i2=j1-j2，演变i1-j1=i2-j2
		左上->右下：任意2点（i1，j1）和（i2，j2）都满足i1+j1=i2+j2

		则定义对角线2个数组：rup = new int[(2 * 8) + 1];   i+j,这i属于（1-8）,j属于（1-8）,i+j范围（1-16）
							lup = new int[(2 * 8) + 1];   i-j,这为了避免出现负数，程序里在这里+8.

	*/

		
		rup = new int[(2 * 8) + 1];//对角线上任意2点（i1，j1）和（i2，j2）都满足i1+j1=i2+j2，因为i+j可能的取值范围是从0到15，所以把这个数组的长度定义为16
		lup = new int[(2 * 8) + 1];//反对角线上任意2点都满足i1-i2=j1-j2，演变i1-j1=i2-j2，i-j的范围是-8到8，为了避免出现负数，程序里在这里+8，所以把这个数组的长度定义为16
		
		for (int i = 1; i <= 8; i++) {
			column[i] = 0;
		}
		for (int i = 1; i <= (2 * 8); i++) {
			rup[i] = lup[i] = 0;
		}
		queen = new int[8 + 1];
	}

	/**
	 * 回溯算法
	 * 
	 * @param i 行
	 */
	public void backtrack(int i) {
		if (i > 8) {
			// 打印日志
			showAnswer();
		} else {
			//遍历同行的列
			for (int j = 1; j <= 8; j++) {
				//同列不能有皇后；反对角线不能有皇后，对角线不能有皇后，符合条件进入循环体
				//同列：column[j]
				//对角线：rup[i + j] =（1,1），（2,2），（3,3）
				//反对角线：lup[i - j + 8] = （1,3），（2,2），（3,1）；为了避免出现负数，程序里在这里+8。
				if ((column[j] == 0) && (rup[i + j] == 0) && (lup[i - j + 8] == 0)) {
					//i行j列，放置一个皇后
					queen[i] = j;
					//设置当前列、对角线，反对角线不能有皇后
					column[j] = rup[i + j] = lup[i - j + 8] = 1;
					// 循环调用，获取当前行的下一行，继续进行判断是否在皇后路线上
					backtrack(i + 1); 
					//"下一行"不能放置皇后，回退到上一行，清空上一行遍历记录，然后再次遍历该行的其他列
					column[j] = rup[i + j] = lup[i - j + 8] = 0;//清空遍历记录
				}
			}
		}
	}

	/**
	 *  打印日志
	 */
	protected void showAnswer() {
		num++;
		System.out.print("\n解答" + num+" = ");
		for (int i = 0; i < queen .length; i++) {
			System.out.print(queen[i]+",");
		}
		System.out.println();
		for (int y = 1; y <= 8; y++) {//行
			for (int x = 1; x <= 8; x++) {//列
				//y行x列，queen[y]的值是皇后所在列
				if (queen[y] == x) {
					System.out.print("Q");
				} else {
					System.out.print("X");
				}
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		System.out.println("开始解决8皇后算法问题");
		long s1 = System.currentTimeMillis();

		Queen queen = new Queen();
		//从第1行第1列开始
		queen.backtrack(1);
		
 		long s2 = System.currentTimeMillis();
		System.out.println("耗时【"+(s2 - s1) +"豪秒】【" + ((s2 - s1) / 1000) + "秒】.............................");
	}
}

代码2

时间：耗时【8豪秒】（这里时间比代码1小，可能是因为日志打印少的原因）
注意：这方法代码很高效，在同一行X列，如果不符合皇后放置条件，不比清除当前行的皇后数据，直接遍历当前行的下一列。
不同点：

  • 代码1是先比较皇后是否符合条件，符合在放置皇后，标记皇后，遍历下一行；如果不符合条件，清空上一行皇后数据，重新遍历该行之后的列，再次寻找皇后的位置。
  • 代码2是先放置皇后的位置，然后在比较该位置的皇后是否符合提交，如果符合条件继续遍历下一行；不符合条件，则遍历该行之后的列，这里节省一步骤：清空上一行皇后的数据。 
    1
    2
    3
    1  2  3
    1  2  3
    1  2  3

x[j] == x[k]：同一列。
(Math.abs(k - j)) == (Math.abs(x[j] - x[k]):i1-i2=j1-j2 -> i1-j1=i2-j2，对角线上。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package demo2;

/**
 * 92个结果
 * 
 * 很高效的方法。
 * 省一步骤：清除当前行的皇后
 *
 */
public class Empress {
	private int n; // 皇后个数
	private int[] x; // 当前解
	private long sum; // 当前已找到的可行方案数
	private static int h; // 记录遍历方案序数

	public Empress() {
		this.sum = 0; // 初始化方案数为1，当回溯到最佳方案的时候，就自增1
		this.n = 8; // 求n皇后问题，由自己定义
		this.x = new int[n + 1]; // x[i]表示皇后i放在棋盘的第i行的第x[i]列，x[i]值是列
		h = 1; // 这个是我额外定义的变量，用于遍历方案的个数，请看backTrace()中h变量的作用，这里将它定义为static静态变量
	}

	/**
	 * 验效
	 * 
	 * @param k  行
	 * @return
	 */
	public boolean place(int k) {
		//遍历列
		for (int j = 1; j < k; j++) {
			// 这个主要是刷选符合皇后条件的解，因为皇后可以攻击与之同一行同一列的或同一斜线上的棋子
			//x[j] == x[k]：同一列
			//(Math.abs(k - j)) == (Math.abs(x[j] - x[k])：i1-i2=j1-j2 -> i1-j1=i2-j2，对角线上
 			if ((Math.abs(k - j)) == (Math.abs(x[j] - x[k])) || (x[j] == x[k])) {
				return false; // 如果是与之同一行同一列的或同一斜线上的棋子，返回false;
			}
		}
		return true;// 如果不是与之同一行同一列的或同一斜线上的棋子，返回true;
	}

	/**
	 * 
	 * @param t
	 *            行
	 */
	public void backTrace(int t) {
		// 当t>n时,算法搜索到叶节点，得到一个新的n皇后互不攻击放置方案，方案数加1
		//达到皇后数目，结束1次方案
		if (t > n) {
			sum++; // 方案数自增1
			System.out.println("");
			System.out.println("方案" + (h++) + "");
			//打印皇后
			print(x);
			System.out.println("");// 华丽的分割线
		} else {  // 当t<=n时，当前扩展的结点Z是解空间中的内部结点，该节点有x[i]=1,2，…,n共n个子结点，
					// 对于当前扩展结点Z的每一个儿子结点，由place()方法检测其可行性，
					// 并以深度优先的方式递归地对可行子树搜索，或剪去不可行子数
			//遍历列
			for (int i = 1; i <= n; i++) {
				//t行i列：在t行i列上放置皇后
				x[t] = i;
				// 检查结点是否符合条件
				// 不符合皇后规则，继续遍历当前行的下一列（注意：这里如果不符合条件，少一个清除当上一行皇后的数据）
				// 符合条件，则进入下一行
				if (place(t)) {
					backTrace(t + 1); // 递归调用下一行
				}
			}
		}
	}

	public void print(int[] a) { // 打印数组，没啥的
		for (int i = 1; i < a.length; i++) {
			System.out.print("皇后" + i + "在" + i + "行" + a[i] + "列、");
		}
	}

	public static void main(String[] args) {
		long s1 = System.currentTimeMillis();

		Empress em = new Empress();
		em.backTrace(1); // 从1开始回溯
		System.out.println("");
		System.out.println("详细方案如上所示，" + "可行个数为:" + em.sum);
		
 		long s2 = System.currentTimeMillis();
		System.out.println("耗时【"+(s2 - s1) +"豪秒】 .............................");
	}
}/*
 * output:八皇后问题只有92种方案，这里只给出其中的三个方案 方案1
 * 皇后1在1行1列、皇后2在2行5列、皇后3在3行8列、皇后4在4行6列、皇后5在5行3列、皇后6在6行7列、皇后7在7行2列、皇后8在8行4列、
 * ---------------- 方案2
 * 皇后1在1行1列、皇后2在2行6列、皇后3在3行8列、皇后4在4行3列、皇后5在5行7列、皇后6在6行4列、皇后7在7行2列、皇后8在8行5列、
 * ---------------- . . . 方案92
 * 皇后1在1行8列、皇后2在2行4列、皇后3在3行1列、皇后4在4行3列、皇后5在5行6列、皇后6在6行2列、皇后7在7行7列、皇后8在8行5列、
 * ----------------
 */// ~

代码3

时间：耗时【15豪秒】。
详细：此代码和代码1类似，只是把每个方法拆分开。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package demo3;

/**
 * 92种方法
 * 耗时【15豪秒】
 *
 */
public class Queen {

	private final int size = 8; // 棋盘的大小
	private int[] location; // 皇后在棋盘上的每一行的列的位子，location[i]=j：i行j列
	private int[] colsOccupied; // 皇后在棋盘上占据的列
	private int[] cross1Occuptied; // 皇后在棋盘上占据的正对角线
	private int[] cross2Occuptied; // 皇后在棋盘上占据的是反对角线
	private static int count; // 解决的方法的个数

	private static final int STATUS_OCCUPIED = 1; // 占据的状态
	private static final int STATUS_OCCUPY_CANCELED = 0; // 没有占据的状态

	//初始化数据
	public Queen() {
		this.location = new int[this.size];
		this.colsOccupied = new int[this.size];
		this.cross1Occuptied = new int[2 * this.size];
		this.cross2Occuptied = new int[2 * this.size];
	}

	//打印棋盘皇后位置
	public void printLocation() {
		System.out.println();
		System.out.println("以下是皇后在棋盘上的第" + count + "种方式的摆放");
		/*for (int i = 0; i < this.size; i++) {
			System.out.println("行：" + i + " 列：" + this.location[i]);
		}*/
		System.out.println();
		for (int y = 0; y <= 7; y++) {//行
			for (int x = 0; x <= 7; x++) {//列
				//y行x列，queen[y]的值是皇后所在列
				if (this.location[y] == x) {
					System.out.print("Q");
				} else {
					System.out.print("X");
				}
			}
			System.out.println();
		}
	} // end 打印

	/**
	 * 判断位子（i,j）是否被占领了
	 * @param i  行
	 * @param j  列
	 * @return
	 */
	private boolean isOccupied(int i, int j) {
		//同一列
		if (this.colsOccupied[j] == 1) {
			return true;
		}
		//对角线
		if (this.cross1Occuptied[i - j + this.size - 1] == 1) {
			return true;
		}
		
		//反对角线
		if (this.cross2Occuptied[i + j] == 1) {
			return true;
		}
		return false;
	}

	/**
	 * 设置棋盘位置状态，如果flag为1，表示占领位子（i,j）; 如果flag为0，表示取消占领位子（i,j) ;
	 */
	private void setStatus(int i, int j, int flag) {
		this.colsOccupied[j] = flag; // 宣布占领或者是取消占领第j列
		this.cross1Occuptied[i - j + this.size - 1] = flag; // 宣布占领或者取消占领正对角线
		this.cross2Occuptied[i + j] = flag; // 宣布占领或取消占领反对角
	}

	/**
	 * 第一行开始摆放皇后
	 * @param i 行
	 */
	public void place(int i) {
		// 在第i行尝试把皇后放在每一列
		for (int j = 0; j < this.size; j++) { 
			// 判断该位子是不是已经被占领了的
			if (!this.isOccupied(i, j)) { 
				// 摆放皇后，在第i行把皇后放在第j列
				this.location[i] = j; 
				//设置状态，该点已经放置皇后
				this.setStatus(i, j, this.STATUS_OCCUPIED); 
				if (i < this.size - 1) {
					//遍历下一行
					this.place(i + 1);
				} else {//当前方案遍历完，打印该方案
					this.count++;
					this.printLocation();
				}
				// 设置状态，该点皇后位置被清空（回溯法）
				this.setStatus(i, j, STATUS_OCCUPY_CANCELED);
			}
		}
	}

	/**
	 * 从第0行0列开始
	 */
	public void start() {
		this.place(0);
	}

	public static void main(String[] args) {
		long s1 = System.currentTimeMillis();

		Queen queen = new Queen();
		queen.start();
		
		long s2 = System.currentTimeMillis();
		System.out.println("耗时【" + (s2 - s1) + "豪秒】 .............................");
	}
}

代码4

时间：耗时【15豪秒】。
详细：此代码和代码1类似，只是把每个方法拆分开。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package demo4;

/**  
 * 回溯法求解 N 皇后问题 
 * 
 * 和demo1的方法一样
 *  
 */ 
public class N_Queens {  
    // 皇后的个数  
    private int queensNum = 8;  
    // column[i] = j 表示第 i 列的第 j 行放置一个皇后  
    private int[] queens = new int[queensNum + 1];  
    // rowExists[i] = true 表示第 i 行有皇后  
    private boolean[] rowExists = new boolean[queensNum + 1];  
    // a[i] = true 表示右高左低的第 i 条斜线有皇后  
    private boolean[] a = new boolean[queensNum * 2];  
    // b[i] = true 表示左高右低的第 i 条斜线有皇后  
    private boolean[] b = new boolean[queensNum * 2];  
      
    // 初始化变量  
    private void init() {  
        for (int i = 0; i < queensNum + 1; i++) {  
            rowExists[i] = false;  
        }  
        for(int i = 0; i < queensNum * 2; i++) {  
            a[i] = b[i] = false;  
        }  
    }  
 
    // 判断该位置是否已经存在一个皇后，存在则返回 true
    // 同列，对角线，反对角线
    private boolean isExists(int row, int col) {  
        return (rowExists[row] || a[row + col - 1] || b[queensNum + col - row]);  
    }  
 
    // 主方法：测试放置皇后  
    public void testing(int column) {  
        // 遍历每一行  
        for (int row = 1; row < queensNum + 1; row++) {  
            // 如果第 row 行第 column 列可以放置皇后  
            if (!isExists(row, column)) {  
                // 设置第 row 行第 column 列有皇后   
                queens[column] = row;  
                // 设置以第 row 行第 column 列为交叉点的斜线不可放置皇后  
                rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = true;  
                // 全部尝试过，打印  
                if(column == queensNum) {  
                    for(int col = 1; col <= queensNum; col++) {  
                        System.out.print("("+col + "," + queens[col] + ")  ");  
                    }  
                    System.out.println();  
                }else {  
                    // 放置下一列的皇后  
                    testing(column + 1);  
                }  
                // 撤销上一步所放置的皇后，即回溯  
                rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = false;  
            }  
        }  
    }  
      
    // 测试  
    public static void main(String[] args) {  
        N_Queens queen = new N_Queens();  
        queen.init();  
        // 从第 1 列开始求解  
        queen.testing(1);  
    }  
}

代码5

时间：耗时【15豪秒】。
详细：此代码和代码1类似，只是把每个方法拆分开。

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
54
55
56
57
58
59
60
61
62
63
64
package demo5;

/**
 * 
 * 和demo1的方法一样
 *
 */
public class Queen {

	int num; // 记录方案数
	int[] queenline = new int[8]; // 记录8个皇后所占用的列号
	boolean[] col = new boolean[8]; // 列安全标志
	boolean[] diagonal = new boolean[16]; // 对角线安全标志
	boolean[] undiagonal = new boolean[16]; // 反对角线安全标志

	void solve(int i) {
		for (int j = 0; j < 8; j++) {
			// 表示第i行第j列是安全的可以放皇后
			if (col[j] && diagonal[i - j + 7] && undiagonal[i + j]) {
				queenline[i - 1] = j + 1;
				// 修改安全标志
				col[j] = false;
				diagonal[i - j + 7] = false;
				undiagonal[i + j] = false;
				// 判断是否放完8个皇后
				if (i < 8) {
					// 未放完8个皇后则继续放下一个
					solve(i + 1);
				} else // 已经放完8个皇后
				{
					num++;
					System.out.println("\n皇后摆放第" + num + "种方案:");
					System.out.println("行分别为1 2 3 4 5 6 7 8 列分别为");
					for (int i1 = 0; i1 < 8; i1++) {
						System.out.print(queenline[i1] + " ");
					}
				}
				// 修改安全标志，回溯
				col[j] = true;
				diagonal[i - j + 7] = true;
				undiagonal[i + j] = true;
			}
		}
	}

	public static void main(String[] args) {
		Queen q = new Queen();
		System.out.println("////////////////////////////八皇后问题////////////////////////////////");
		System.out.println("在8行8列的棋盘上放置8个皇后,皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子,使任一个皇后都不能吃掉其他的7个皇后共有92种方法");
		// 方案初始化
		q.num = 0; 
		// 置所有列为安全
		for (int i = 0; i < 8; i++) { 
			q.col[i] = true;
		}
		// 置所有对角线为安全
		for (int i0 = 0; i0 < 16; i0++)
		{
			q.diagonal[i0] = q.undiagonal[i0] = true;
		}
		//开始第1行第1列
		q.solve(1);
	}
}

代码6

解析：代码有点绕，整体思路和代码1一样

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package demo6;

/**
 * 92种方法
 * 
 */
public class Queen8 {
	public static int num = 0; // 累计方案总数
	public static final int MAXQUEEN = 8;// 皇后个数，同时也是棋盘行列总数
	public static int[] cols = new int[MAXQUEEN]; // 定义cols数组，表示8列棋子摆放情况

	public Queen8() {
		// 第0行开始
		getArrangement(0);
		System.out.print("");
		System.out.println(MAXQUEEN + "皇后问题有" + num + "种摆放方法。");
	}

	/**
	 * 
	 * @param n  行
	 */
	public void getArrangement(int n) {
		// 遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true
		// 当前行的列数组
		boolean[] rows = new boolean[MAXQUEEN];
		//遍历行i，进行左边点判断是否符合皇后标准
		for (int i = 0; i < n; i++) {
			//当前行cols[i]列 不符合条件
			//同列不能存皇后
			rows[cols[i]] = true;
			//可以理解为：i1-i2=j1-j2=d
			int d = n - i;
			
			//cols[i]：i行x列，这x列就是皇后的位置，那么皇后可能在d（对角线）（cols[i]-j1+j2），皇后位置减去d位置=0，在对角线上
			if (cols[i] - d >= 0) {
				rows[cols[i] - d] = true;
			}
			//cols[i]：i行x列，这x列就是皇后的位置，那么皇后可能在d（反对角线）（cols[i]+j1-j2）
			if (cols[i] + d <= MAXQUEEN - 1) {
				rows[cols[i] + d] = true;
			}
		}
		
		//遍历下一列
		for (int i = 0; i < MAXQUEEN; i++) {
			// 判断该行i列是否合法
			// true：不符合皇后条件，遍历下一列
			// false：符合皇后条件，放置皇后在当前位置
			if (rows[i]) {
				continue;
			}
			// 设置当前列皇后所在行数
			cols[n] = i;
			// 当前列不为最后一列时，遍历下一行
			if (n < MAXQUEEN - 1) {
				getArrangement(n + 1);
			} else {
				// 累计方案个数
				num++;
				// 打印棋盘信息
				printChessBoard();
			}
		}
	}

	public void printChessBoard() {
		System.out.println("第" + num + "种走法  ");
		//列
		for (int i = 0; i < MAXQUEEN; i++) {
			//行
			for (int j = 0; j < MAXQUEEN; j++) {
				//j行i列：cols[j]=i，值：列
				if (i == cols[j]) {
					//皇后位置
					System.out.print("0 ");
				} else {
					System.out.print("+ ");
				}
			}
			System.out.println(" ");
		}
	}

	public static void main(String args[]) {
		long s1 = System.currentTimeMillis();
		Queen8 queen = new Queen8();
		long s2 = System.currentTimeMillis();
		System.out.println("耗时【" + (s2 - s1) + "豪秒】 .............................");
	}

}

# 回溯算法, 算法

喜欢这篇文章？打赏一下作者吧

最佳调度问题(回溯算法)
Mybatis一级缓存和二级缓存

评论

关注我

链接

分类

标签云

Android Centos Effect Java JDK6 源码 JDK7 源码 JDK8 源码 JMM JVM Java Linux MongoDB Mongodb MyBatis MySQL Redis Spring Think In Java Tomcat Ubuntu 一致性哈希算法 书 倒排索引 内存泄漏 分支限界算法 分治法 分治算法 分词算法 动态规划 动态规划算法 华为 回溯算法 多线程 工具 并发 开源项目 手机游戏 排序算法 推荐 散列表 数学 数据库 数据结构 日语 最优路径算法 机器学习 源码 算法 线程安全 编程珠玑 计算机基础 设计模式 贪心算法 跳表 面试

最新文章

归档

标签

Android 1
Centos 3
Effect Java 2
JDK6 源码 18
JDK7 源码 6
JDK8 源码 1
JMM 7
JVM 10
Java 40
Linux 4
MongoDB 1
Mongodb 1
MyBatis 3
MySQL 2
Redis 1
Spring 4
Think In Java 1
Tomcat 7
Ubuntu 1
一致性哈希算法 1
书 3
倒排索引 1
内存泄漏 1
分支限界算法 2
分治法 1
分治算法 1
分词算法 2
动态规划 1
动态规划算法 2
华为 1
回溯算法 4
多线程 2
工具 1
并发 5
开源项目 17
手机游戏 1
排序算法 1
推荐 1
散列表 1
数学 1
数据库 2
数据结构 5
日语 1
最优路径算法 1
机器学习 1
源码 3
算法 26
线程安全 2
编程珠玑 3
计算机基础 1
设计模式 4
贪心算法 3
跳表 1
面试 1

最新文章

归档

标签

Android 1
Centos 3
Effect Java 2
JDK6 源码 18
JDK7 源码 6
JDK8 源码 1
JMM 7
JVM 10
Java 40
Linux 4
MongoDB 1
Mongodb 1
MyBatis 3
MySQL 2
Redis 1
Spring 4
Think In Java 1
Tomcat 7
Ubuntu 1
一致性哈希算法 1
书 3
倒排索引 1
内存泄漏 1
分支限界算法 2
分治法 1
分治算法 1
分词算法 2
动态规划 1
动态规划算法 2
华为 1
回溯算法 4
多线程 2
工具 1
并发 5
开源项目 17
手机游戏 1
排序算法 1
推荐 1
散列表 1
数学 1
数据库 2
数据结构 5
日语 1
最优路径算法 1
机器学习 1
源码 3
算法 26
线程安全 2
编程珠玑 3
计算机基础 1
设计模式 4
贪心算法 3
跳表 1
面试 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×