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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
#include <iostream>
using namespace std;
bool sudokusolver(int col, int row); //Tries to solve the sudoku puzzle
bool samecol(int row, int sudoku[][9][9], int num); //Determines if there is a conflict along the column
bool samerow(int col, int sudoku[][9][9], int num); //Along a row
bool samebox(int col, int row, int sudoku[][9][9], int num); //Determines if there is a conflict in the same box
void sudokubacktrack(int col, int row, int sudoku[][9][9], int num); //If all solutions fail, goes backwards until a new answer is made
int main() {
int col=0, row=0;
sudokusolver(col,row);
return 0;
}
bool sudokusolver(int col, int row) {
int num;
num = 1; //Num starts at 1, and goes up to 9 to test possible answer on a spot
int sudoku[2][9][9] = {{
{ 3, -1, 6, 5, -1, 8, 4, -1, -1 }, //Just the sudoku example
{ 5, 2, -1, -1, -1, -1, -1, -1, -1 },
{ -1, 8, 7, -1, -1, -1, -1, 3, 1 },
{ -1, -1, 3, -1, -1, -1, -1, 8, -1 },
{ 9, -1, -1, 8, 6, 3, -1, -1, 5 },
{ -1, 5, -1, -1, 9, -1, 6, -1, -1 },
{ 1, 3, -1, -1, -1, -1, 2, 5, -1 },
{ -1, -1, -1, -1, -1, -1, -1, 7, 4 },
{ -1, -1, 5, 2, -1, 6, 3, -1, -1 }
}};
for (int i = 0; i < 9; i++) { //Determines if the spot on the sudoku was originally a given number, or a blank space
for (int j = 0; j < 9; j++) { //So in the case of when we need to backtrack, when the program has reached a spot filled
if (sudoku[0][i][j] == -1) { //in spot, it still knows that it was originally blank, and can be changed.
sudoku[1][i][j] = 0; //it's a blank spot
}
else {
sudoku[1][i][j] = 1; //it's given
}
}
}
if(sudoku[1][col][row] == 1){
cout<<sudoku[0][col][row]<<" is given!!!!"<<endl; //if spot is a given number, skips ahead
if(row == 8){ //if it has reached the end of a row, row resets to 0; col goes up.
row = 0;
col++;
}
else{
row++;
}
sudokusolver(col,row); //Solves the next spot
}
else{
while(num < 10){
samecol(row,sudoku,num);
samerow(col,sudoku,num);
samebox(col,row,sudoku,num);
if(!samecol(row,sudoku,num)&&!samerow(col,sudoku,num)){
//IF there are no conflicts on the column, row, and box
cout<<"All Clear! ["<<col<<"]["<<row<<"] is now (("<<num<<"))"<<endl; //The value of num is placed in that spot
sudoku[0][col][row] = num;
if(row == 8){ //If it reaches the end of a row, resets row to 0, and col advances
row = 0;
col++;
}
else{
row++;
}
sudokusolver(col,row); //After moving, goes back and solves the next spot. Num resets to 1.
}
else{
num++;
}
} //Goes here if all possible numbers failed to not have a conflict
if(col > 8){ //If col exceeds 8, that means all blanks have been filled in with no errors.
for(int i; i < 9; i++){ //Time to print out the fully answered sudoku
cout<<"=================="<<endl;
cout<<"|";
for(int j; j < 9; j++){
cout<<sudoku[0][i][j]<<"|";
}
cout<<endl;
}
return true;
}
else{
cout<<endl<<"Time to backtrack"<<endl; //If all numbers fail, there must be a problem on the previous spots
sudokubacktrack(col,row,sudoku,num); //Goes back and tries a new solution
}
}
}
bool samecol(int row, int sudoku[][9][9], int num){
for(int i; i < 9; i++){
if(sudoku[0][i][row] == num){
cout<<"============col=============="<<endl; //Compares num to numbers on the column
cout<<"Is "<<sudoku[0][i][row]<<" equal to "<<num<<"?"<<endl;
return true;
}
}
return false;
}
bool samerow(int col, int sudoku[][9][9], int num){
for(int i; i < 9; i++){
cout<<"============row=============="<<endl; //Compares the num to numbers on the row
cout<<"Is "<<sudoku[0][col][i]<<" equal to "<<num<<"?"<<endl;
if(sudoku[0][col][i] == num){
return true;
}
}
return false;
}
bool samebox(int col, int row, int sudoku[][9][9], int num){
int boxcol=0, boxrow=0;
if(row<4){
boxrow = 0; //Depending on the value of row and col determines which box to start on.
}
else if(row<7){ //If col = 4 and row = 5; boxcol becomes = 3 and boxrow = 3. This means it starts on the middle box.
boxrow = 3;
}
else{
boxrow = 6;
}
if(col<4){
boxcol = 0;
}
else if(col<7){
boxcol = 3;
}
else{
boxcol = 6;
}
for(int i=0; i < 3; i++){
for (int j=0; j < 3; j++){
cout<<"============box=============="<<endl; //Compares num to the number on the box
cout<<"Is "<<sudoku[0][boxcol+i][boxrow+j]<<" equal to "<<num<<"?"<<endl;
if(sudoku[0][boxcol+i][boxrow+j] == num){
return true;
}
}
}
return false;
}
void sudokubacktrack(int col, int row, int sudoku[][9][9], int num){
num = sudoku[0][col][row]; //num equals to the previously given number of this spot
if (sudoku[1][col][row] == 1){ //if this spot is a given, goes backwards
if(row == 0){
row = 8;
col--;
}
else{
row--;
}
}
else{ //if this spot was not given, and used to be blank
while(num < 10){
if(!samecol(row,sudoku,num)&&!samerow(col,sudoku,num)&&!samebox(col,row,sudoku,num)){ //checks current number
sudoku[0][col][row] = num;
cout<<endl<<"Back done!!!"<<endl;
sudokusolver(col,row);
}
else{
num++;
}
}
sudoku[0][col][row] = -1; //Compared up to 9, and there still isn't a free spot. Resets it
if(row == 0){ //to a blank space, and goes backwards one spot.
row = 8;
col--;
}
else{
row--;
}
sudokubacktrack(col, row, sudoku, num); //Repeats
}
}
|
