[LeetCode] 51. N-Queens

Posted on | In

Problem

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

51. N-Queens

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.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Explanation

  1. We can use backtracking to solve this problem. First, create a res list, and a col[] array has length equal to the number of row. The col[] is used to store each row’s Queen’s column. From the above solution 1’s example, the col[] will be col[1, 3, 0, 2], which represents in first row, store the Queen in index1’s column; in second row, store the Queen in second row’s index3 column; in third row, store the Queen in the third row’s index0 column; in the fourth row, store the Queen in the fourth row’s index2 column. So, in the helper function, we pass res, col[], and the current row as arguments.

  2. The base case is if the current row if it is greater than the board’s row number. If it is, then we translate col[] to a list of string (first string represents first row, second string represents second row, etc), then pass to res because col[] stores each row’s Queen column index.

  3. If the board has length $n$, then we loop $n$ times to try every column in each row. First, we try the first row that passed by the main caller’s function. So in the first row, we loop every column, and if it is valid, then we recursively call the next row.

  4. To know if the column index we pass if it is valid, we need to create another function to check. For example, if we finish passing the first three rows col[2, 0, 3, -], now we need to pass the fourth row’s Queen’s column index to the array. By the way, we don’t need to check row because each row only has one number. To check the column, we try col[2, 0, 3, 0] which is not valid because index1 also has 0; then we try col[2, 0, 3, 1] which is valid because before 1 is not present before. After checking column, we also need to check diagonal. We have the following statement: If two points’ row differences is equal to column difference, then these two points are in diagonal.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    void helper(List<List<String>> res, int[] col, int row) {
        if (row == col.length) {
            addRes(res, col);
            return;
        }
        for (int i = 0; i < col.length; i++) {
            col[row] = i;
            if (isValid(col, row)) {
                helper(res, col, row+1);
            }
        }
    }
    boolean isValid(int[] col, int row) {
        for (int i = 0; i < row; i++) {
            if (col[i] == col[row]) {
                return false;
            } else if (Math.abs(i - row) == Math.abs(col[i] - col[row])) {
                return false;
            }
        }
        return true;
    }
    void addRes(List<List<String>> res, int[] col) {
        List<String> temp = new ArrayList<String>();
        for (int curCol = 0; curCol < col.length; curCol++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < col.length; j++) {
                if (col[curCol] == j) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            temp.add(sb.toString());
        }
        
        res.add(new ArrayList<String>(temp));
    }
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        if (n <= 0) return res;
        helper(res, new int[n], 0);
        return res;
    }
}