递归——回溯算法解决八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路分析

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
  3. 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
  4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
  5. 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤

说明：用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列

代码

warning:在judge方法中特别注意array[ i ] == array[ n ] || Math.abs ( n - i ) == Math.abs ( array[ n ] - array[ i ] )
//说明
//1.array[ i ] == array[ n ] 表示判断第n个皇后和前面的n-1个皇后是否在同一列，
//2.Math.abs ( n - i ) == Math.abs ( array[ n ] - array[ i ] ) 表示判断第n个皇后和前面的n-1个皇后是否在同一斜线
//3.因为我们的下标表示行-1所以下标不断递增所以不用判断是否在同一行

        //因为我们之前规定，一维数组下标表示行-1，下标对应的值表示在该行上第几列，
        //举例1.第一行第一个为皇后1 arr[0]=0  第二个皇后第二行第二列arr[1]=1
        //Math.abs ( 1 - 0 ) == Math.abs ( array[ 1 ] - array[ 0 ] )=1
        //第三行第二列arr[2]=1   第6行第5列arr[5]=4
        //Math.abs ( 5 - 2 ) == Math.abs ( array[ 5 ] - array[ 2 ] )=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
public class Queen8 {
    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义一个数组array,保存皇后放置位置的结果，比如arr = {0 , 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[ max ];
    static int count = 0;  //表示有多少种成功结果
    static int num = 0;   //表示不断回溯判断，判断了多少次

    public static void main ( String[] args ) {
        //测试
        Queen8 queen8 = new Queen8 ( );
        queen8.check (0  );
        System.out.printf ( "一共有%d种解法，不断回溯，判断是否冲突%d次", count, num );
    }

    //放置第n个皇后
    //特别注意，check每一次递归时，check都for ( int i = 0 ; i < max ; i++ ) { ，不断回溯，把第一个第一列所有情况弄完后，进行第一行第二列在不断check在回溯
    public void check ( int n ) {
        if ( n == max ) {  //n=8表示8个皇后就已经放好了
            print ();
            count++;
            return;
        }
        //依次放入皇后，并判断是否冲突
        for ( int i = 0 ; i < max ; i++ ) {
            //先把当前这个皇后，放到该行的第一个
            array[ n ] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if ( judge ( n ) ){
                //接着放n+1个皇后
                check ( n+1 );
            }
            //如果冲突就继续执行array[n]=i;即将该皇后移动到本行下一列

        }
    }



    //查看当我们放置第n个皇后，就就去检测，该皇后与已经拜放的皇后是否冲突
    /**
     *
     * @param n 表示第n个皇后
     * @return 位置是否符合规则
     */
    public boolean judge ( int n ) {
        num++;
        for ( int i = 0; i < n; i++ ) {

            //说明
            //1.array[ i ] == array[ n ] 表示判断第n个皇后和前面的n-1个皇后是否在同一列，
            //2.Math.abs ( n - i ) == Math.abs ( array[ n ] - array[ i ] )  表示判断第n个皇后和前面的n-1个皇后是否在同一斜线
            //3.因为我们的下标表示行-1所以下标不断递增所以不用判断是否在同一行

			//因为我们之前规定，一维数组下标表示行-1，下标对应的值表示在该行上第几列，
            //举例1.第一行第一个为皇后1 arr[0]=0  第二个皇后第二行第二列arr[1]=1
            //Math.abs ( 1 - 0 ) == Math.abs ( array[ 1 ] - array[ 0 ] )=1
            //第三行第二列arr[2]=1   第6行第5列arr[5]=4
            //Math.abs ( 5 - 2 ) == Math.abs ( array[ 5 ] - array[ 2 ] )=3
            //此时画图他们确实为一条斜线
            if ( array[ i ] == array[ n ] || Math.abs ( n - i ) == Math.abs ( array[ n ] - array[ i ] ) ) {
                return false;
            }
        }
        return true;
    }

    //将皇后拜访的位置打印出来
    private void print ( ) {
        for ( int i = 0 ; i < array.length ; i++ ) {
            System.out.print ( array[ i ] + " " );
        }
        System.out.println ( );
    }
}