N皇后问题 Java 代码实现及回溯法解析

public class NQueens {

public static void main(String[] args) {
    int n = 4;
    solveNQueens(n);
}

public static void solveNQueens(int n) {
    int[] board = new int[n];
    solveNQueens(board, 0, n);
}

public static boolean solveNQueens(int[] board, int row, int n) {
    if (row == n) {
        printBoard(board);
        return true;
    }
    boolean hasSolution = false;
    for (int i = 0; i < n; i++) {
        if (isValid(board, row, i)) {
            board[row] = i;
            hasSolution = solveNQueens(board, row + 1, n) || hasSolution;
        }
    }
    return hasSolution;
}

public static boolean isValid(int[] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || row - i == Math.abs(col - board[i])) {
            return false;
        }
    }
    return true;
}

public static void printBoard(int[] board) {
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            if (board[row] == col) {
                System.out.print('Q' + ' ');
            } else {
                System.out.print('. ' + ' ');
            }
        }
        System.out.println();
    }
    System.out.println();
}

}