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
| class Solution
{
private int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
private int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
private int[][] occupy;
private char[][] grid;
private int cellNum;
public List<List<String>> solveNQueens(int n)
{
init(n);
List<List<String>> result = new LinkedList<>();
searchQueen(0, result);
return result;
}
private void searchQueen(int num, List<List<String>> result)
{
if (cellNum == num)
{
result.add(getGridValueAsList());
return;
}
for (int i = 0; i < cellNum; i++)
{
if (occupy[num][i] == 0)
{
grid[num][i] = 'Q';
handleOccupy(num, i, 1);
searchQueen(num + 1, result);
grid[num][i] = '.';
handleOccupy(num, i, -1);
}
}
}
private List<String> getGridValueAsList()
{
List<String> ans = new LinkedList<>();
for (int i = 0; i < cellNum; i++)
{
StringBuilder sb = new StringBuilder();
for (int j = 0; j < cellNum; j++)
{
sb.append(grid[i][j]);
}
ans.add(sb.toString());
}
return ans;
}
private void handleOccupy(int row, int col, int step)
{
occupy[row][col] += step;
for (int i = 0; i < dx.length; i++)
{
int nextX = row + dx[i];
int nextY = col + dy[i];
while (isInBoundary(nextX, nextY))
{
occupy[nextX][nextY] += step;
nextX = nextX + dx[i];
nextY = nextY + dy[i];
}
}
}
private boolean isInBoundary(int row, int col)
{
return row >= 0 && row < cellNum && col >=0 && col < cellNum;
}
private void init(int n)
{
cellNum = n;
grid = new char[n][n];
occupy = new int[n][n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
grid[i][j] = '.';
}
}
}
}
|