N-Queens LeetCode solution in Java

1
// Simple backtracking logic, try out each row and col and check position is valid or not.
2
// since we are going row one by one, there is no way queen is placed in that row.
3
// so, we need to check col, diagonals for valid position.
4
// col is straightforward flag for each column
5

6
// dia1
7
// 0 1 2 3
8
// 1 2 3 4
9
// 2 3 4 5
10
// 3 4 5 6
11

12
// dia2
13
// 0 -1 -2 -3
14
// 1  0 -1 -2
15
// 2  1  0 -1
16
// 3  2  1  0
17

18
// negative numbers are not allowed as index, so we add n - 1 to diagonal2.
19

20
class Solution {
21
  List<List<String>> ans = new LinkedList<>();
22
  int n;
23

24
  public List<List<String>> solveNQueens(int n) {
25
    this.n = n;
26
    int[][] board = new int[n][n];
27

28
    boolean[] col = new boolean[n];
29
    boolean[] dia1 = new boolean[2 * n];
30
    boolean[] dia2 = new boolean[2 * n];
31

32
    solve(0, col, dia1, dia2, board);
33

34
    return ans;
35
  }
36

37
  public void solve(int row, boolean[] col, boolean[] dia1, boolean[] dia2, int[][] board) {
38
    if (row == n) {
39
      copyBoardToAns(board);
40
      return;
41
    }
42
    // brute force all col in that row
43
    for (int i = 0; i < n; i++) {
44
      if (isValid(col, dia1, dia2, i, row)) {
45
        col[i] = true;
46
        dia1[row + i] = true;
47
        dia2[row - i + n - 1] = true;
48
        board[row][i] = 1;
49
        solve(row + 1, col, dia1, dia2, board);
50
        col[i] = false;
51
        dia1[row + i] = false;
52
        dia2[row - i + n - 1] = false;
53
        board[row][i] = 0;
54
      }
55
    }
56
  }
57

58
  public boolean isValid(boolean[] col, boolean[] dia1, boolean[] dia2, int curCol, int curRow) {
59
    return !col[curCol] && !dia1[curCol + curRow] && !dia2[curRow - curCol + n - 1];
60
  }
61

62
  public void copyBoardToAns(int[][] board) {
63
    List<String> res = new LinkedList<>();
64
    for (int i = 0; i < n; i++) {
65
      String row = "";
66
      for (int j = 0; j < n; j++) {
67
        if (board[i][j] == 1) {
68
          row += "Q";
69
        } else {
70
          row += ".";
71
        }
72
      }
73
      res.add(row);
74
    }
75
    ans.add(res);
76
  }
77
}