Problem Description
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
Solution
One important observation is that we cannot place two Queens in the same row (or even the column). The target is to place N Queens. So, we must try to place 1 Queen in each row.
We solve this by trying every possibility and back tracking when it’s not possible to place the Queen in any of the columns for a given row. For every row, we go through all the columns and check if it’s possible to place the Queen at that position. If yes, mark that position and go to the next row. After each call is complete, we revert the change made (backtrack).
Remember: Time Complexity - O(N!)
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
List<List<String>> ans = new ArrayList<List<String>>();
public List<List<String>> solveNQueens(int n) {
nQueen(new int[n][n], 0, n);
return ans;
}
public void save(int[][] mat){
List<String> list = new ArrayList<>();
for(int i=0; i<mat.length; i++){
StringBuilder sb = new StringBuilder();
for(int j=0; j<mat[0].length; j++){
if(mat[i][j] == 0){
sb.append(".");
}else{
sb.append("Q");
}
}
list.add(sb.toString());
}
ans.add(list);
}
public boolean check(int[][] mat, int i, int j){
int r=i, c=j;
//Check same column
while(r>=0){
if(mat[r--][c] == 1) return false;
}
//left side diagonal
r=i; c=j;
while(r>=0 && c>=0){
if(mat[r--][c--] == 1) return false;
}
//right side diagonal
r=i; c=j;
while(r>=0 && c<=mat[0].length-1){
if(mat[r--][c++] == 1) return false;
}
return true;
}
public void nQueen(int[][] mat, int i, int n){
if(i == n){
//Queen was placed on every row
save(mat);
return;
}
//Check for every column in ith row
for(int j=0; j<n; j++){
//If it's possible to place it at mat[i][j]
if(check(mat, i, j)){
//Mark the queen at mat[i][j]
mat[i][j] = 1;
//Try to place the Queen in the next row
nQueen(mat, i+1, n);
//IMPORTANT STEP: revert the change to backtrack, and look for other ways
mat[i][j]=0;
}
}
}
}