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
| #include <cstdio>
#include <iostream>
using namespace std;
/* создаем массивы для строк, столбиков, диагоналей и комбинаций ферзей */
int str[8], col[8], up_free[15], dn_free[15], coln[8];
main( )
{
int i ;
/* забиваем массивы комбинаций ферзей, для строк, столбиков, диагоналей единицами */
for ( i = 0 ; i <= 7 ; i++ )
{
col[i] = str[i] = 1 ;
coln[i] = -1;
}
for ( i = 0 ; i <= 14 ; i++ )
up_free[i] = dn_free[i] = 1 ;
/* запускаем рекурсию */
addqueen( ) ;
printf( "\n\n" );
system("PAUSE");
return 0;
}
addqueen( )
{
int i, c, r, row, x, stlb, strk, z=0, y=0;
static int comb, queen=0;
/* Проверяем строки и колонки */
for ( row = 0 ; row <= 7 ; row++ )
{
for ( i = 0 ; i <= 7 ; i++ )
{
/* если строка не находится под ударом */
if ( str[row] == 0 )
{
++y;/* подсчитываем сколько занятых строк (см. if ( y == queen ) */
break;
}
else
{
/* сравниваем кол-во занятых строк с кол-вом уже найденных ферзей,
чтобы очередную фигуру не ставить между уже найденными */
if ( y == queen )
{
/* если столбец и диагонали не находятся под ударом */
if ( col[i] && up_free[i+row] && dn_free[row-i+7] )
{
++queen;
/* маркируем колонку и диагональ */
str[row] = 0;
col[i] = 0 ;
up_free[i+row] = 0 ;
dn_free[row-i+7] = 0 ;
/* запоминаем, что в строке находится ферзь */
coln[row] = i ;
/* если ферзь пятый, то проверяем комбинации и выводим на экран */
if ( queen == 5 )
{
/* Находим пустые клетки, чтоб проверить их диагонали */
for ( strk = 0 ; strk <= 7 ; strk++ )
{
for ( stlb = 0 ; stlb <= 7 ; stlb++ )
{
if ( (str[strk] == 1) && (col[stlb] == 1) )
{
if ( (up_free[strk+stlb] == 1) && (dn_free[strk-stlb+7] == 1) )
{
z = 1;
strk = 7;
stlb = 7;
}
}
}
}
/* Если комбинация удачная выводим ее на экран */
if ( z == 0 )
{
x = 0;
comb++ ;
printf ( "\n\n\ncombination no. %d", comb ) ;
for ( r = 0 ; r <= 7 ; r++ )
{
printf ( "\n\n" ) ;
for ( c = 0 ; c <= 7 ; c++ )
{
if ( (c == coln[r])&&(x <= 4 ))
{
printf ( " Q " ) ;
++x;
}
else
printf ( " [] " ) ;
}
}
}
}
else {
addqueen( ) ;
}
/* снимаем пометку с массива комбинаций, столбца, колонки и диагонали */
str[row] = 1;
col[ coln[row] ] = 1 ;
up_free[ row + coln[row] ] = 1 ;
dn_free[ row - coln[ row ] + 7 ] = 1 ;
coln[row] = -1 ;
--queen;
z = 0;
}
}
else
break;
}
}
}
} |
(
