八皇后问题

发表于 | 分类于 | 阅读次数:

八皇后问题

一些笔记

「为了有规律地枚举所有可能的解，避免遗漏和重复，把问题求解的过程分为多个阶段。每个阶段，都会面对一个岔路口，先随意选择一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另一种走法继续走。」

反复理解下：递归是一种栈结构的形式，最后一个入栈的最先执行完，然后返回上一层栈桢继续执行（对照八皇后的代码实现）。

八皇后是怎么打印出所有的解的？？

理解是

  1. 首先是深度有点搜索找到最优的一组解，这时候打印输出，然后递归会返回到棋盘的倒数第二行（找到解后返回和遇到错误后是一样的）。
  2. 然后找到下一个可能的位置，一个位置能够放置ok，那么再到下一行，找可放置的位置，如果ok，就能输出第二种解；
  3. 直到第七行找完，就依次找第六行，知道最后一行都找不到了，即所有解都已经找到。

代码可以看成 第一行的循环*第二行的循环*第三行的循环* … *第八行的循环

下面代码中回溯算法非常隐蔽，其实是在 result[row] = col; 这一步，每次之前的值都会被替换。

Java代码

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
/**
 * @description: 八皇后问题
 * @author: rhsphere
 * @since: 2019-11-04 10:52 by jdk 1.8
 */
public class MyEightQueen {
    /** 八皇后问题的数 */
    private static final int QUEEN_SIZE = 8;

    /** 用来进行队列结果的存储 */
    private int[] result = new int[QUEEN_SIZE];

    private int count = 1;

    /**
     * 八皇后问题求解
     * @param row 行号
     */
    public void call8Queens(int row) {
    	 // 如果当前已经到行的末尾，则打印当前的结果
    	if (row == QUEEN_SIZE) {
    		System.out.println(count++);
    		print(result);
    		return;
    	}
    	 // 进行当前列的遍历
    	for (int col = 0; col < QUEEN_SIZE; col++) {
		   // 检查当前是否满足要求,如果满足，则设置result，并进行下一轮的遍历
    		if (isOK(row, col)) {
    			result[row] = col;
    			call8Queens(row+1);
    		}
    	}
    }

    /**
     * 检查当前行列是否满足要求
     *
     * @param row 行信息
     * @param col 列信息
     * @return true 满足要求 false 不满足要求
     */
    private boolean isOK(int row, int col) {
    	int leftup = col - 1;
    	int rightup = col + 1;
    	 // 按行逐行向上进行遍历
    	for (int i = row - 1; i >= 0; i--) {
 		    // 1，检查当前行是否已经设置
    		if (result[i] == col)
    			return false;
   			 // 2，检查左上部分是否被放置了棋子
    		if (leftup >= 0 && result[i] == leftup)
    			return false;
     	   // 进行右上部分的检查是否被放置了棋子
    		if (rightup < QUEEN_SIZE && result[i] == rightup)
    			retrun false;
    		 // 左上部分继续向左上
    		leftup++;
    		rightup++;
    	}
    }

    /**
     * 打印当前匹配的结果
     *
     * @param result
     */
    private void print(int[] result) {
    	for (int row = 0; row < QUEEN_SIZE; row++) {
    		for (int col = 0; col < QUEEN_SIZE; col++) {
    			if (result[row] == col) {
    				System.out.print("Q ");
    			} else {
    				System.out.print("* ");
    			}
    		}
			System.out.println();
    	}
		System.out.println();    	
    }

}

代码更加显式地展现回溯

https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/

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
/* Java program to solve N Queen Problem using 
backtracking */
public class NQueenProblem { 
	final int N = 4; 

	/* A utility function to print solution */
	void printSolution(int board[][]) 
	{ 
		for (int i = 0; i < N; i++) { 
			for (int j = 0; j < N; j++) 
				System.out.print(" " + board[i][j] 
								+ " "); 
			System.out.println(); 
		} 
	} 

	/* A utility function to check if a queen can 
	be placed on board[row][col]. Note that this 
	function is called when "col" queens are already 
	placeed in columns from 0 to col -1. So we need 
	to check only left side for attacking queens */
	boolean isSafe(int board[][], int row, int col) 
	{ 
		int i, j; 

		/* Check this row on left side */
		for (i = 0; i < col; i++) 
			if (board[row][i] == 1) 
				return false; 

		/* Check upper diagonal on left side */
		for (i = row, j = col; i >= 0 && j >= 0; i--, j--) 
			if (board[i][j] == 1) 
				return false; 

		/* Check lower diagonal on left side */
		for (i = row, j = col; j >= 0 && i < N; i++, j--) 
			if (board[i][j] == 1) 
				return false; 

		return true; 
	} 

	/* A recursive utility function to solve N 
	Queen problem */
	boolean solveNQUtil(int board[][], int col) 
	{ 
		/* base case: If all queens are placed 
		then return true */
		if (col >= N) 
			return true; 

		/* Consider this column and try placing 
		this queen in all rows one by one */
		for (int i = 0; i < N; i++) { 
			/* Check if the queen can be placed on 
			board[i][col] */
			if (isSafe(board, i, col)) { 
				/* Place this queen in board[i][col] */
				board[i][col] = 1; 

				/* recur to place rest of the queens */
				if (solveNQUtil(board, col + 1) == true) 
					return true; 

				/* If placing queen in board[i][col] 
				doesn't lead to a solution then 
				remove queen from board[i][col] */
				board[i][col] = 0; // BACKTRACK 
			} 
		} 

		/* If the queen can not be placed in any row in 
		this colum col, then return false */
		return false; 
	} 

	/* This function solves the N Queen problem using 
	Backtracking. It mainly uses solveNQUtil () to 
	solve the problem. It returns false if queens 
	cannot be placed, otherwise, return true and 
	prints placement of queens in the form of 1s. 
	Please note that there may be more than one 
	solutions, this function prints one of the 
	feasible solutions.*/
	boolean solveNQ() 
	{ 
		int board[][] = { { 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 } }; 

		if (solveNQUtil(board, 0) == false) { 
			System.out.print("Solution does not exist"); 
			return false; 
		} 

		printSolution(board); 
		return true; 
	} 

	// driver program to test above function 
	public static void main(String args[]) 
	{ 
		NQueenProblem Queen = new NQueenProblem(); 
		Queen.solveNQ(); 
	} 
} 
// This code is contributed by Abhishek Shankhadhar
0%