[算法] - 8皇后问题(回溯法)

1. 问题

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？

2. 解题过程

该问题使用回溯法，其本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。

3. 代码

package com.jfp;

/**
 * @author jiafupeng
 * @desc   8皇后
 * @create 2021/3/17 14:54
 * @update 2021/3/17 14:54
 **/
public class Queen8 {

    static final int MAX_NUM = 8;
    int chessBoard[][] = new int[MAX_NUM][MAX_NUM];

    boolean check(int x, int y){
        for(int i = 0; i<y; i++){
            if(chessBoard[x][i] == 1){
                return false;
            }

            if(x-1-i >= 0 && chessBoard[x-1-i][y-1-i] == 1){
                return false;
            }

            if(x+1+i < MAX_NUM && chessBoard[x+1+i][y-1-i] == 1){
                return false;
            }
        }

        return true;
    }

    boolean settleQueen(int y){
        if(y == MAX_NUM){
            return true;
        }

        for(int i=0;i<MAX_NUM;i++){
            for(int x=0;x<MAX_NUM;x++){
                chessBoard[x][y] = 0;
            }

            if(check(i,y)){
                chessBoard[i][y] =1;
                if(settleQueen(y+1)){
                    return true;
                }
            }
        }

        return false;
    }

    void printChessBoard() throws InterruptedException {
        for(int j=0;j<MAX_NUM;j++){
            for(int i=0;i<MAX_NUM;i++){
                int a = chessBoard[i][j];
                Thread.sleep(1);
                if(a == 1){
                    System.err.print(a + " ");
                } else {
                    System.out.print(a + " ");
                }

            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Queen8 queen8 = new Queen8();
        queen8.settleQueen(0);
        queen8.printChessBoard();
    }
}

4. 输出

5. 参考

1. 漫画：什么是八皇后问题？ - 小灰