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

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();
    }
}