-
Notifications
You must be signed in to change notification settings - Fork 0
/
dcp-038-queens.linq
70 lines (56 loc) · 1.43 KB
/
dcp-038-queens.linq
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
<Query Kind="Program" />
// This problem was asked by Microsoft.
//
// You have an N by N board. Write a function that, given N,
// returns the number of possible arrangements of the board
// where N queens can be placed on the board without threatening
// each other, i.e. no two queens share the same row, column, or diagonal.
void Main()
{
for (int n = 1; n <= 12; n++)
{
Count(n).Dump(n.ToString());
}
}
public struct Point
{
public int X { get; set; }
public int Y { get; set; }
public Point(int x, int y)
{
X = x;
Y = y;
}
}
int Count(int n)
{
var solutions = new List<Point[]>();
Place(n, new List<Point>(), solutions);
return solutions.Count();
}
void Place(int n, List<Point> placed, List<Point[]> solutions)
{
// the job before recursion step is to find all possible placements
// for next queen and then place to each place and then recusion step happens
if (placed.Count == n)
{
solutions.Add(placed.ToArray());
return;
}
for (int x = 0; x < n; x++)
{
// note that queens are the same, so we always can place 1st queen at first row, 2nd at second
// and be sure that we do not miss anything
int y = placed.Count;
//for (int y = 0; y < n; y++)
{
bool canPlace = !placed.Any(p => p.X == x || p.Y == y || Math.Abs(x - p.X) == Math.Abs(y - p.Y));
if (canPlace)
{
placed.Add(new Point(x, y));
Place(n, placed, solutions);
placed.RemoveAt(placed.Count - 1);
}
}
}
}