Reference: LeetCode
Difficulty: Hard

My Post:

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.

From LeetCode

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.

Note: A queen can attack other queens that are at the same row or column or at the diagonal line.

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.

Analysis

Brute-Force

Enumerate all possible placements of queens on a nxn chessboard and check if each is valid.

Time: $O(N^N)$
Space: $O(1)$ if we do not consider the output list.

Backtracking

The basic idea is to examine each row and use an array attack to restrict the possibilities in the future searching.

Check out the comments. Be careful about the following aspects:

  • Why will we stop? In other words, what is the base case?
  • How do we make string generation more efficiently? StringBuilder
  • Why should we initialize attack array with int type rather than boolean?
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
public List<List<String>> solveNQueens(int n) {
  List<List<String>> result = new ArrayList<>();
  List<Integer> queens = new ArrayList<>(); // store (i, j) where to place queens
  int[][] attack = new int[n][n];  // > 0 -> could be attacked
  backtrack(0, n, queens, attack, result);
  return result;
}

// d is the depth (here it means the current row)
// queens stores the col of a placed queen
private void backtrack(int d, int n, List<Integer> queens, int[][] attack, List<List<String>> result) {
  // base case
  if (d == n) {
    // Init dot builder
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; ++i) sb.append(".");
    // Set queen
    List<String> strList = new ArrayList<>();
    for (int row = 0; row < n; ++row) {
      int col = queens.get(row);
      sb.setCharAt(col, 'Q');
      strList.add(sb.toString());
      sb.setCharAt(col, '.');
    }
    result.add(strList);
    return;
  }
  // backtrack
  for (int i = 0; i < n; ++i) {
    if (attack[d][i] == 0) {
      // pick
      queens.add(i);
      updateAttack(d, i, n, attack);
      backtrack(d + 1, n, queens, attack, result);
      // restore
      queens.remove(queens.size() - 1);
      restoreAttack(d, i, n, attack);
    }
  }
}

The graph is from LeetCode solution section.

Each time we pick a queen (i, j) we need to update all the attacked positions below it, which include three cases as shown in the graph:

  • Left-Below positions
  • Below positions
  • Right-Below positions

Notice that we cannot use boolean since some attacked positions might be overlapped.

In the example above, when we restore attacked position for queen B, the orange position will be restored to no-attack state if we use true/false; however, it is still under attack by queen A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void updateAttack(int i, int j, int n, int[][] attack) {
  // update all below/hill/dale positions by +1
  for (int k = i + 1, offset = 1; k < n; ++k, ++offset) {
    attack[k][j] += 1; // mid
    if (j - offset >= 0) attack[k][j - offset] += 1; // left
    if (j + offset < n) attack[k][j + offset] += 1; // right
  }
}

private void restoreAttack(int i, int j, int n, int[][] attack) {
  // restore all below/hill/dale positions by -1
  for (int k = i + 1, offset = 1; k < n; ++k, ++offset) {
    attack[k][j] -= 1;
    if (j - offset >= 0) attack[k][j - offset] -= 1; // left
    if (j + offset < n) attack[k][j + offset] -= 1; // right
  }
}

Time: $O(N \times N!)$. There is $N$ possibilities to put the first queen, then no more than $N(N-2)$ to put the second one, and no more than $N(N-2)(N-4)$ to put the third one, and so forth. In total, there are $N$ layers. The number of calls of backtracking at each layer is upper bounded by $N!$. (not consider string construction)
Space: $O(N^2)$ since there are call stacks and attack array (do not consider output).

The space complexity can be optimized by using $N$-size array rows, dale, and hill. Each element of them denotes a specific vertical line or diagonal line that a queen can attack.

From LeetCode solution section:

N-Queens II

Returns the number of solutions. Modify based on the above 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
public int totalNQueens(int n) {
  int[][] attack = new int[n][n];  // > 0 -> could be attacked
  return backtrack(0, n, attack);
}

// d is the depth (here it means the current row)
private int backtrack(int d, int n, int[][] attack) {
  // base case
  if (d == n) {
    return 1;
  }
  // backtrack
  int count = 0;
  for (int i = 0; i < n; ++i) {
    if (attack[d][i] == 0) {
      updateAttack(d, i, n, attack);
      count += backtrack(d + 1, n, attack);
      restoreAttack(d, i, n, attack);
    }
  }
  return count;
}


private void updateAttack(int i, int j, int n, int[][] attack) {
  // update all below/hill/dale positions by +1
  for (int k = i + 1, offset = 1; k < n; ++k, ++offset) {
    attack[k][j] += 1; // mid
    if (j - offset >= 0) attack[k][j - offset] += 1; // left
    if (j + offset < n) attack[k][j + offset] += 1; // right
  }
}

private void restoreAttack(int i, int j, int n, int[][] attack) {
  // restore all below/hill/dale positions by -1
  for (int k = i + 1, offset = 1; k < n; ++k, ++offset) {
    attack[k][j] -= 1;
    if (j - offset >= 0) attack[k][j - offset] -= 1; // left
    if (j + offset < n) attack[k][j + offset] -= 1; // right
  }
}