题目

题解

N皇后问题是一个经典的问题，在一个 N * N 的棋盘上放置 N 个皇后，
每行一个并使其不能互相攻击。
（同一行、同一列、同一斜线（包括主对角线和副对角线）上的皇后都会自动攻击）。

回溯算法

代码

方法一

import java.util.*;

public class code52 {

    public static int count;

    public static int totalNQueens(int n) {
        count = 0;
        char board[][] = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        dfs(board, 0);
        return count;
    }

    public static void dfs(char board[][], int colIndex) {
        if (colIndex == board.length) {
            count++;
            return;
        }

        // 按列进行放置，若到了第 colIndex 列，
        // 那么第 0~colIndex-1 列已经是放置好的
        for (int i = 0; i < board.length; i++) {
            if (validate(board, i, colIndex)) {
                board[i][colIndex] = 'Q';
                dfs(board, colIndex + 1);
                board[i][colIndex] = '.';
            }
        }
    }

    // x == i 同一行
    // x + j == y + i (y - x == j - i,斜率 1,在同一条直线上) 同一主斜行
    // x + y == i + j (x - i == -( y - j),斜率 -1,在同一条直线上) 同一副斜行
    public static boolean validate(char board[][], int x, int y) {
        for (int i = 0; i < board.length; i++) {
            // 判断放置第 j 列的时候，是否与前面的冲突，
            // 不需要判断 y == j（循环 j < y），只是与前面的进行比较
            for (int j = 0; j < y; j++) {
                // 等同于 if(board[i][j] == 'Q' && (Math.abs(x - i) == Math.abs(y - j) || x == i))
                if (board[i][j] == 'Q' && (x - y == i - j || x + y == i + j || x == i)) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int res = totalNQueens(n);
            System.out.println(res);
        }
    }

}

方法二

import java.util.*;

public class code52_1 {

    public static int count;

    public static int totalNQueens(int n) {
        count = 0;
        int x[] = new int[n + 2];
        place(x, 1, n);
        return count;
    }

    // t 扩展的是行
    public static void place(int x[], int t, int n) {
        if (t > n) {
            count++;
            return;
        }

        // 探索第 t 行的每一列是否有元素满足要求
        for (int i = 1; i <= n; i++) {
            x[t] = i;
            if (check(x, t)) {
                place(x, t + 1, n);
            }
        }
    }

    public static boolean check(int x[], int k) {
        for (int j = 1; j < k; j++) {
            if ((Math.abs(k - j) == Math.abs(x[k] - x[j])) || (x[j] == x[k])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int res = totalNQueens(n);
            System.out.println(res);
        }
    }
}

52. N皇后 II

题目

题解

代码

方法一

方法二

参考