N-Queens

update Jan 16,2018 21:32

LeetCode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,

 There exist two distinct solutions to the 4-queens puzzle:

 [
  [".Q..",  // Solution 1
   "...Q",
   "Q...",
   "..Q."],

  ["..Q.",  // Solution 2
   "Q...",
   "...Q",
   ".Q.."]
 ]

Basic Idea:

  首先想到这是一道 dfs 的题目，因为要生成所有的解的集合。大致思路如下：   首先明确queen的性质，她可以杀与其同在一条直线上的其他棋子（横竖斜），而我们要在 N*N 大小的棋盘中放入 N 个 queen，所以我们一定是每个 row 放一个 queen。然后，具体地，我们对每一个 row，考虑其上每个 col 位置放 queen 的话会不会影响之前放置好的第 0 to row-1 row 上的queen。如果当前 (row, col) 可以，就继续向 row + 1 继续 dfs。

时间空间复杂度分析：   整个算法如果是 brute force 解，求出所有可能的组合再判断是否 valid，需要 O(N^N) 的时间复杂度，因为在每一个 row，都需要考虑 N 个 col 的情况。但是因为我们可以每次判断当前 col 能否放置 queen，相当于在搜索的过程中进行了剪枝，所以我们至少可以将时间复杂度优化为 O(N!) (即不考虑之前放置过queen的col，所以每次可选col数量递减1)； 因为我们还剪掉了斜线上的情况，所以最后的时间复杂度应该是优于 O(N!)；   空间的话，recursion 的 call stack 最大深度为 N，如果不考虑储存和处理解集的空间，整个空间复杂度应该是 O(N);

Java Code:

由于题目要求的返回值是一个 List<List<String>> ，而对于每一个棋盘，我们认为 List<Integer> 更加容易进行判断当前col放queen是否会影响到之前，所以我们的dfs只会将结果存储在一个 List<List<Integer>> 中，然后另外用一个 drawChessboard() 来将解转化为所需要的return value;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<Integer>> lst = new ArrayList<>();
        dfs(lst, 0, new ArrayList<>(), n);
        List<List<String>> res = drawChessboard(lst, n);
        return res;
    }

    // 对于每个row，考虑每个col能否放queen，如果可以，继续向下一个row dfs
    // path 中存放的是每个 row 放置queen的 col 的值 (0 to n-1)
    private void dfs(List<List<Integer>> res, int row, List<Integer> path, int n) {
        if (row == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        // consider each col
        for (int col = 0; col < n; ++col) {
            if (isValid(path, row, col, n)) {
                path.add(col);
                dfs(res, row + 1, path, n);
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断当前 row，col 位置放 queen 的话会不会影响到之前的 row
    private boolean isValid(List<Integer> path, int row, int col, int n) {
        int k = 1;
        while (k <= row) {
            int queen = path.get(row - k);
            if (queen == col || queen == col - k || queen == col + k) return false;
            k++;
        }
        return true;
    }

    // 将用数字表示每行queen位置的所有解转化为string的二维list形式
    private List<List<String>> drawChessboard(List<List<Integer>> lst, int n) {
        List<List<String>> ret = new ArrayList<>();
        for (List<Integer> intList : lst) {
            List<String> stringList = new ArrayList<>();
            for (int queenPos : intList) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; ++i) {
                    if (i != queenPos) sb.append(".");
                    else sb.append("Q");
                }
                stringList.add(sb.toString());
            }
            ret.add(stringList);
        }
        return ret;
    }
}

update 2018-07-29 17:11:37

Update, 更简洁的写法

这里的写法更简单，也可以把 boolean[n][n] 换成一个 int[n]，存放没row的queen的col.

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        dfs(n, 0, new boolean[n][n], res);
        return res;
    }

    private void dfs(int n, int row, boolean[][] board, List<List<String>> res) {
        if (row == n) {
            List<String> currBoard = new ArrayList<>();
            for (boolean[] r : board) {
                StringBuilder sb = new StringBuilder();
                for (boolean val : r) {
                    if (val) sb.append('Q');
                    else sb.append('.');
                }
                currBoard.add(sb.toString());
            }
            res.add(currBoard);
            return ;
        }
        for (int col = 0; col < n; ++col) {
            if (isValid(board, row, col)) {
                board[row][col] = true;
                dfs(n, row + 1, board, res);
                board[row][col] = false;
            }
        }
    }

    private boolean isValid(boolean[][] board, int r, int c) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
        for (int i = 1; r - i >= 0; ++i) {
            if (c - i >= 0 && board[r - i][c - i]) return false;
            if (c + i < board[0].length && board[r - i][c + i]) return false;
            if (board[r - i][c]) return false;
        }
        return true;
    }
}