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
|
#include <iostream>
bool validity_check(int sudoku[9][9], int n, int p, int q)
{
for (int i { }; i < 9; i++)
{
if (sudoku[p][i] == n && q != i) { return false; }
}
for (int i { }; i < 9; i++)
{
if (sudoku[i][q] == n && p != i) { return false; }
}
int bx { q / 3 };
int by { p / 3 };
for (int i { by * 3 }; i < by * 3 + 3; i++)
{
for (int j { bx * 3 }; j < bx * 3 + 3; j++)
{
if (sudoku[i][j] == n && i != p && j != q) { return false; }
}
}
return true;
}
int blank(int sudoku[9][9], int* r, int* c)
{
for (*r = 0; *r < 9; (*r)++)
{
for (*c = 0; *c < 9; (*c)++)
{
if (sudoku[*r][*c] == 0) { return 1; }
}
}
return 0;
}
bool solver(int sudoku[9][9])
{
int row { };
int col { };
int x { -1 };
int y { -1 };
if (!blank(sudoku, &row, &col)) { return 1; }
for (int i { 1 }; i <= 9; i++)
{
if (validity_check(sudoku, i, row, col))
{
sudoku[row][col] = i;
if (solver(sudoku)) { return true; }
sudoku[row][col] = 0;
}
}
return false;
}
void print_sudoku(int sudoku[9][9])
{
for (int i { }; i < 9; i++)
{
for (int j { }; j < 9; j++)
{
std::cout << sudoku[i][j] << " ";
}
std::cout << "\n\n";
}
}
int main()
{
int sudoku[9][9] = { {3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0} };
std::cout << "-------------------------\n";
if (solver(sudoku) == true)
{
std::cout << " SOLVED! \n";
std::cout << "-------------------------\n";
print_sudoku(sudoku);
}
else
{
std::cout << "Solution Does Not Exist!\n";
}
}
| |
