-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
34 lines (33 loc) · 1.06 KB
/
Solution.cs
File metadata and controls
34 lines (33 loc) · 1.06 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
public class Solution
{
public IList<IList<string>> SolveNQueens(int n)
{
IList<IList<string>> ret = [];
bool[] cols = new bool[n];
bool[] diag1 = new bool[2 * n];
bool[] diag2 = new bool[2 * n];
BackTracking(ret, 0, n, diag1, diag2, cols, []);
return ret;
}
void BackTracking(IList<IList<string>> ret, int pos, int n, bool[] diag1, bool[] diag2, bool[] cols, IList<string> choose)
{
if (pos >= n)
{
ret.Add([.. choose]);
return;
}
StringBuilder sb = new();
sb.Append('.', n);
for (int i = 0; i < n; i++)
{
if (cols[i] || diag1[i + pos] || diag2[pos - i + n]) continue;
cols[i] = diag1[i + pos] = diag2[pos - i + n] = true;
sb[i] = 'Q';
choose.Add(sb.ToString());
BackTracking(ret, pos + 1, n, diag1, diag2, cols, choose);
choose.RemoveAt(choose.Count - 1);
sb[i] = '.';
cols[i] = diag1[i + pos] = diag2[pos - i + n] = false;
}
}
}