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
|
#include <iostream>
const unsigned BOARD_SIZE = 4;
bool inrange(unsigned lower, unsigned x, unsigned upper) {
return lower <= x && x <= upper;
}
bool isSolved(int board[BOARD_SIZE][BOARD_SIZE]) {
unsigned firstSum = 0;
for (unsigned row = 0; row < BOARD_SIZE; ++row) {
unsigned rowSum = 0;
for (unsigned col = 0; col < BOARD_SIZE; ++col) {
// Валидно решение
if (board[row][col] != 0 && board[row][col] != 1)
return false;
if (row == 0)
firstSum += board[row][col];
rowSum += board[row][col];
// Последователност на 0ли и 1ци в реда
if (inrange(1, col, BOARD_SIZE - 2) &&
!inrange(1, board[row][col - 1] + board[row][col] + board[row][col + 1], 2))
return false;
// Последователност на 0ли и 1ци в колоната
if (inrange(1, row, BOARD_SIZE - 2) &&
!inrange(1, board[row - 1][col] + board[row][col] + board[row + 1][col], 2))
return false;
}
// Еднакъв брой нули и единици на всеки ред
if (firstSum != rowSum)
return false;
}
for (unsigned col = 0; col < BOARD_SIZE; ++col) {
unsigned colSum = 0;
for (unsigned row = 0; row < BOARD_SIZE; ++row)
colSum += board[row][col];
// Еднакъв брой нули и единици на всяка колона (и това еднакво с всеки ред)
if (firstSum != colSum)
return false;
}
return true;
}
bool solve(unsigned index, int board[BOARD_SIZE][BOARD_SIZE]) {
if (index == BOARD_SIZE * BOARD_SIZE)
return isSolved(board);
int& curr = board[index / BOARD_SIZE][index % BOARD_SIZE];
if (curr != -1)
return solve(index + 1, board);
curr = 0;
if (solve(index + 1, board))
return true;
curr = 1;
if (solve(index + 1, board))
return true;
curr = -1;
return false;
}
int main() {
int board[BOARD_SIZE][BOARD_SIZE];
for (unsigned row = 0; row < BOARD_SIZE; ++row)
for (unsigned col = 0; col < BOARD_SIZE; ++col)
std::cin >> board[row][col];
solve(0, board);
for (unsigned row = 0; row < BOARD_SIZE; ++row) {
for (unsigned col = 0; col < BOARD_SIZE; ++col)
std::cout << board[row][col] << ' ';
std::cout << std::endl;
}
return 0;
}
|
