题目

题解

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

回溯算法

代码

方法一

import java.util.*;

public class code51 {

    public static List<List<String>> solveNQueens(int n) {
        char board[][] = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(board, 0, res);
        return res;
    }

    public static void dfs(char board[][], int colIndex, List<List<String>> res) {
        if (colIndex == board.length) {
            res.add(construct(board));
            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, res);
                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 List<String> construct(char board[][]) {
        List<String> res = new ArrayList<String>();
        for (int i = 0; i < board.length; i++) {
            String s = String.valueOf(board[i]);
            res.add(s);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            List<List<String>> res = solveNQueens(n);
            // System.out.println(res);
            for (List<String> str : res) {
                System.out.println(str);
            }
        }
    }

}

方法二

import java.util.*;

public class code51_1 {

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        int x[] = new int[n + 2];
        place(x, 1, n, res);
        return res;
    }

    // t 扩展的是行
    public static void place(int x[], int t, int n, List<List<String>> res) {
        if (t > n) {
            List<String> list = new ArrayList<String>();
            for (int i = 1; i <= n; i++) {
                String str = "";
                for (int j = 1; j <= n; j++) {
                    if (x[i] == j) {
                        str += "Q";
                    } else {
                        str += ".";
                    }
                }
                list.add(str);
            }
            res.add(list);
        }
        // 按照行进行放置
        // 循环每一列
        // 探索第 t 行的每一列是否有元素满足要求
        for (int i = 1; i <= n; i++) {
            x[t] = i;
            // 如果在该列放入 Q 不冲突的话
            if (check(x, t)) {
                // 没有回溯，因为没有修改原结果集
                // 只是临时记录结果
                place(x, t + 1, n, res);
            }
        }
    }

    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();
            List<List<String>> res = solveNQueens(n);
            // System.out.println(res);
            for (List<String> str : res) {
                System.out.println(str);
            }
        }
    }
}

51. N皇后

题目

题解

代码

方法一

方法二

参考