-
Notifications
You must be signed in to change notification settings - Fork 1
/
Solver.c
237 lines (209 loc) · 6.09 KB
/
Solver.c
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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include "Bool.h"
#include "Solver.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
/* last one */
/*bool valid_array_number[9][9][9] = {false};*/
void swap(int* randArr, int index1, int index2){
int temp = randArr[index1];
randArr[index1] = randArr[index2];
randArr[index2] = temp;
}
bool solver_randomizeBacktracking(int** matrixSolve){
int randArr[9]={0};
int i, j, value,n, countof_Legalvalues = 0, randomized_index;
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if (matrixSolve[i][j] == 0)
{
for (value = 1; value < 10; value++)
{ /*filling the array with legal values.*/
if (solver_is_legalValue(matrixSolve, i, j, value) == 1)
{
randArr[countof_Legalvalues] = value;
countof_Legalvalues++;
}
}
while (countof_Legalvalues > 1) { /*randomly picking and recursively calling the function.
we have several options and we want to check if one of them is legal solution*/
randomized_index = rand() % countof_Legalvalues;
/* as the array with the legal indexes is filled from the first cell it ensures that the size is the
* count of legal values and the array is empty from the end until 9 minus count of legal values.
* choose randomly an index from legal values */
matrixSolve[i][j] = randArr[randomized_index];
for (n=randomized_index; n<countof_Legalvalues;n++){
swap(randArr,n,n+1);
}
countof_Legalvalues--; /*now we have one less valid value.*/
if (solver_randomizeBacktracking(matrixSolve) == 1)
{
return true;
} else
{
matrixSolve[i][j] = 0;/*delete the value and try again recursivly to check the other options */
}
}
if (countof_Legalvalues == 1)
{ /*no need for choosing a value in randomized way as only one is remain.*/
matrixSolve[i][j] = randArr[0];
countof_Legalvalues=0;
if (solver_randomizeBacktracking(matrixSolve) == 1)
{/* after putting the remained value check if matrix can be solved */
return true;
}else{
matrixSolve[i][j]=0;
}
}
if (countof_Legalvalues == 0)
{ /*all values failed for this cell.*/
matrixSolve[i][j]=0;
return false; /* no value remain is a valid one so no */
}
} else if ((i == 8) && (j == 8)&& (solver_is_legalValue(matrixSolve, 8, 8, matrixSolve[i][j]) == 1)) {
return true;
}
}
}
return false;
}
/*
* this function checks if the value entered in a specific cell is a valid one. if there is the same value in the same row
* the function returns 0 otherwise it is a legal value and the function returns 1.
*/
bool check_row(int **matrixPlay, int row, int col, int checked_value){
int i;
for (i = 0; i< 9; i++)
{
if (i != col)
{
if (matrixPlay[row][i] == checked_value)
{
return false;
}
}
}
return true;
}
/*
* this function checks if the value entered in a specific cell is a valid one. if there is the same value in the same colomn
* the function returns 0 otherwise it is a legal value and the function returns 1.
*
*/
bool check_col(int **matrixPlay, int row, int col, int checked_value){
int i;
for (i = 0; i< 9; i++)
{
if (i != row)
{
if (matrixPlay[i][col] == checked_value)
{
return false;
}
}
}
return true;
}
/*
* checks if the number exists in the same block. this function divides the matrix into 9 blocks.
* first it checks for which block the index belongs and after it iterates over the 9 elements.
* it returns 1 if value is valid
*
*
*/
bool checkBlock(int **matrixPlay, int x, int y, int checked_value) {
int a, b, c, d;
a = (x / 3) * 3;/* it tells in which block the index is. 0-2 are in block 0. 3-5 in block 2 which start at index 3 and 6-8 in block 3
that start in index 6. */
b = (y / 3) * 3; /* the same with the col*/
for (c = 0; c < 3; c++)
{ /* iterates over the elements in the block */
for (d = 0; d < 3; d++)
{
if ( !((a+c==x) &&(b+d==y)) )
{
if (matrixPlay[a + c][b + d] == checked_value)
{
return false;
}
}
}
}
return true;
}
/* return whether the value is valid- different from all values in the same row block and column */
bool solver_is_legalValue(int **matrixPlay, int x, int y, int checked_value){
if(checked_value==0)
{
return true;
}
if(checkBlock(matrixPlay, x, y, checked_value)==0)
{
return false;
}
if(check_row(matrixPlay, x, y, checked_value)==0)
{
return false;
}
if(check_col(matrixPlay, x, y, checked_value)==0)
{
return false;
}
return true;
}
void copy_boards(int** old, int**new,int size){
int i;
for(i=0; i<size;i++){
memcpy(new[i], old[i],size);
}
}
/* this function receives a board in a current position and checks if there is a solution.
* incase there is, it updates the solved board to the new solution and returns 1 */
bool solver_determenistic_algo(int **matrixPlay,int **matrixSolve){
int row, col, number;
for (row = 0; row < 9; row++)
{
for (col = 0; col < 9; col++)
{
/* if cell is empty check if it can be filled*/
if (matrixPlay[row][col] == 0)
{
for (number = 1; number< 10; number++)
{
if (solver_is_legalValue(matrixPlay, row, col, number) == 1)
{
/* if the cell is empty and the value is legal fill the cell */
matrixPlay[row][col] = number;
/* recursive call. check the next cell. the previous cells are not empty anymore
* we put a value with the previous calls */
if (solver_determenistic_algo(matrixPlay, matrixSolve) == 1)
{
if(row==8 && col==8){
copy_boards(matrixSolve,matrixPlay,9);
}
return true;
}
else
/* if the call return 0 delete the element and continue to check the next number*/
{
matrixPlay[row][col] = 0;
}
}
}
/* if no number is legal then delete the cell */
if (number == 10)
{
matrixPlay[row][col] = 0;
return false;
}
}
else if ((col == 8) && (row == 8) && (solver_is_legalValue(matrixPlay, 8, 8,matrixPlay[8][8])==1))
{
copy_boards(matrixSolve,matrixPlay,9);
return true;
}
}
}
return 0;
}