forked from walnutown/CodingInTheDeep
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNQueens.java
More file actions
107 lines (95 loc) · 3.19 KB
/
Copy pathNQueens.java
File metadata and controls
107 lines (95 loc) · 3.19 KB
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
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 Backtracking
// Note, we use a int matrix to mark the position of Queen and build board finally.
// Becuase operations on int array is easy than on string array
// time: O(2^(N*N)), each cell has two options
public class Solution {
public ArrayList<String[]> solveNQueens(int n){
ArrayList<String[]> res = new ArrayList<String[]>();
if (n<=0) return res;
dfs(new int[n][n], 0, res);
return res;
}
private void dfs(int[][] M, int rowNum, ArrayList<String[]> res){
if (rowNum == M.length){
res.add(buildBoard(M));
return;
}
int N = M.length;
for (int i=0; i<N; i++){
if (isValid(M, rowNum, i)){
M[rowNum][i] = 1;
dfs(M, rowNum+1, res);
M[rowNum][i] = 0;
}
}
}
private String[] buildBoard(int[][] M){
int N = M.length;
String[] board = new String[N];
for (int i=0; i<N; i++){
StringBuilder sb = new StringBuilder();
for (int j=0; j<N; j++){
if (M[i][j]==0) sb.append('.');
else sb.append('Q');
}
board[i] = sb.toString();
}
return board;
}
private boolean isValid(int[][] M, int rowNum, int colNum){
for (int i=0; i<rowNum; i++){
if (M[i][colNum]==1) return false;
}
for (int i=rowNum-1, j=colNum-1; i>=0 && j>=0; i--,j--){
if (M[i][j]==1) return false;
}
for (int i=rowNum-1, j=colNum+1; i>=0 && j<M.length; i--,j++){
if (M[i][j]==1) return false;
}
return true;
}
}
// bit manipulation, performance improvement in valid check step
public class Solution {
public ArrayList<String[]> solveNQueens(int n){
ArrayList<String[]> res = new ArrayList<String[]>();
finder( 0, 0, 0, 0, new long[n], res);
return res;
}
public void finder(int x, long col, long lDiagonal, long rDiagonal, long[] rows, ArrayList<String[]> res){
if (x == rows.length){
String[] r = new String[rows.length];
for (int i=0; i<rows.length; i++){
r[i] = Long.toBinaryString(rows[i]).replace('0', '.').replace('1', 'Q');
while (r[i].length() < rows.length) r[i] = '.' + r[i]; // add '.' to fill the missing 0s
}
res.add(r);
}
else{
long avail = ~(col | lDiagonal | rDiagonal);
for (int i=0; i<rows.length; i++){
long pos = avail & (1<<i);
if (pos > 0){
rows[x] = pos;
finder(x+1, (col | pos), ((lDiagonal | pos) << 1), ((rDiagonal | pos) >> 1), rows, res);
}
}
}
}
}