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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| /*
* Задача:
* Расставить на шахматной доске NхN M ферзей, чтобы они:
* 1) не били друг друга
* 2) держали все клетки под боем
*
* перебор организовать рекурсивно
*/
using System;
using System.Collections.Generic;
using System.Text;
namespace Merhaba_FiveQueen
{
public class myPoint
{
public int x, y;
public myPoint(int x, int y)
{
this.x = x;
this.y = y;
}
}
class Program
{
const int N = 8; //размерность доски
const int M = 5; //количество ферзей
static bool[] d1 = new bool[2*N]; //главная диагональ
static bool[] d2 = new bool[2*N];
static bool[] g = new bool[N];
static bool[] v = new bool[N];
static Stack<myPoint> s = new Stack<myPoint>();
static int count = 0;
//return true если все клетки под боем
static bool allFill()
{
bool res = true;
bool [,] f = new bool[N,N];
for (int i = 0; i < N; i++)
{
if (!g[i])
for (int j = 0; j < N; j++)
f[i, j] = true;
if (!v[i])
for (int j = 0; j < N; j++)
f[j, i] = true;
}
//d1
for (int i = 0; i < N; i++)
{
int x = i,
y = 0;
if (!d1[N-i])
for (int j = 0; j < N-i; j++)
f[x++, y++] = true;
x = 0;
y = i;
if (!d1[N+i])
for (int j = 0; j < N - i; j++)
f[x++, y++] = true;
}
//d2
for (int i = 0; i < N; i++)
{
int x = 0,
y = N-1-i;
if (!d2[y])
for (int j = 0; j <= N-1 - i; j++)
f[x++, y--] = true;
x = i;
y = N-1;
if (!d2[i+N-1])
for (int j = 0; j <= N-1 - i; j++)
f[x++, y--] = true;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
res &= f[i, j];
return res;
}
//вывод ответа в шахматной нотации
static void output()
{
myPoint[] tmp = new myPoint[s.Count];
s.CopyTo(tmp, 0);
Console.Write("{0} ", count);
for (int i = s.Count - 1; i >= 0 ; i--)
Console.Write("{0} {1} ", (char)(N-1 - i + 97), tmp[i].y+1);
Console.WriteLine();
}
//основная процедура поиска
static void search(int x, int y, int level)
{
if (level == M)
{
if (allFill())
{
count++;
output();
}
}
else
if (x < N)
{
while (x < N)
{
if (g[x] && v[y] && d1[N - x + y] && d2[x + y])
{
s.Push(new myPoint(x, y));
g[x] = false;
v[y] = false;
d1[N - x + y] = false;
d2[x + y] = false;
search(x + 1, 0, level + 1);
s.Pop();
g[x] = true;
v[y] = true;
d1[N - x + y] = true;
d2[x + y] = true;
}
x += (++y / N);
y %= N;
}
}
}
static void Main(string[] args)
{
Console.SetOut(new System.IO.StreamWriter("output.txt"));
int x = 0, y = 0;
for (int i = 0; i < N; i++)
{
v[i] = true;
g[i] = true;
}
for (int i = 0; i < 2*N; i++)
{
d1[i] = true;
d2[i] = true;
}
search(0, 0, 0);
Console.Out.Close();
}
}
} |
