-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsudoku_functions.h
626 lines (509 loc) · 20.1 KB
/
sudoku_functions.h
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
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
#ifndef HEADERFILE_H
#define HEADERFILE_H
#include <iostream>
#include <ctime>
#include <cstdlib>
#endif
using namespace std;
//generates the board
int board_generation(int board[9][9])
{
//initialize random seed for rand function below
srand(time(0));
//nested for loop iterates over all spaces in board...
for (int i = 0; i < 9; i ++)
{
for (int j = 0; j < 9; j++)
{
//...and generates a random number for them, between 1 & 9
board[i][j] = (rand() % 9) + 1;
}
}
return board[9][9];
}
//function to print board to console
void display_board(int board[9][9])
{
cout << "___________________________" << endl;
//nested for loop to print board
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << "[" << board[i][j] << "]";
//if j is equal to 8, end the line
if (j == 8)
{
cout << "\n" << endl;
cout << "---------------------------\n";
}
}
}
cout << "___________________________" << endl;
}
//FUNCTIONS FOR THE REMOVAL OF INVALID NUMBERS
//function to remove all numbers which are invalid by row
void remove_row_invalids(int board[9][9], int control_list[9])
{
int numlist[9];
//for loop to create a number list of 1-9 (control list exists as we are gonna need to copy it a few times)
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
//nested for loop to parse through all cells
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
//for all indices of the num list
for (int k = 0; k < 9; k++)
{
//if (when) a number of the control list is found to be in cell i, j
if (board[i][j] == numlist[k])
{
//remove the number in cell i, j from the number list
numlist[k] = 0;
//break out of k loop / numlist loop
break;
}
//if at the final index of k and still no match has been found
if (k == 8 && (board[i][j] != numlist[k]))
{
//else if cell at i, j was not found (because i, j is a duplicate number), set its' value to zero
board[i][j] = 0;
}
}
//if we are at the last index of the row, and after we have checked cell i, j=8
if (j == 8)
{
//reset the numlist to be equal to the control list for the next row
for (int k = 0; k < 9; k++)
{
numlist[k] = control_list[k];
}
}
}
}
}
//function to remove all numbers which are invald by column
void remove_column_invalids(int board[9][9], int control_list[9])
{
int numlist[9];
//for loop to create a number list of 1-9 (control list exists as we are gonna need to copy it a few times)
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
//nested for loop to parse through all cells
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
//for all indices of the num list
for (int k = 0; k < 9; k++)
{
//if (when) a number of the control list is found to be in cell j, i
if (board[j][i] == numlist[k])
{
//remove the number in cell j, i from the number list
numlist[k] = 0;
//break out of k loop / numlist loop
break;
}
//if at the final index of k and still no match has been found
if (k == 8 && (board[j][i] != numlist[k]))
{
//else if cell at j, i was not found (because j, i is a duplicate number), set its' value to zero
board[j][i] = 0;
}
}
//if we are at the last index of the row, and after we have checked cell j=8, i
if (j == 8)
{
//reset the numlist to be equal to the control list for the next row
for (int k = 0; k < 9; k++)
{
numlist[k] = control_list[k];
}
}
}
}
}
//remove block (3x3) invalids
void remove_block_invalids(int board[9][9], int control_list[9])
{
//initialization of numlist to copy control list
int numlist[9];
//for loop to create a number list of 1-9 (control list exists as we are gonna need to copy it a few times)
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
// declaration of ints to keep track of the cells we are working with, relevant further down
int i = 0;
int j = 0;
//for each row of 3x3 blocks
for (int blockrow = 0; blockrow < 3; blockrow++)
{
//and each block column index therein (effectivelly each 3x3 block)
for (int blockcolumn = 0; blockcolumn < 3; blockcolumn++)
{
//and for each row within the 3x3 block
for (int row = 0; row < 3; row++)
{
//and for each cell (column index) of the 3 cell row
for (int cell = 0; cell < 3; cell++)
{
//initialize i and j to be equivalent to cell coordinates
i = row + (blockrow*3);
j = cell + (blockcolumn*3);
//for loop to parse through all values of our numlist
for (int index = 0; index < 9; index++)
{
//if we found a match between the number in our block, and the numlist at our index value
if (board[i][j] == numlist[index])
{
//remove that number from the numlist
numlist[index] = 0;
//and break out of this loop
break;
}
//if we are the final index of the list and still no match has been found
if (index == 8 && (board[i][j] != numlist[index]))
{
//remove the invalid index from the board
board[i][j] = 0;
}
}
}
//once we have gone through the 3x3 rows and columns of the list, refresh numlist
if (row == 2)
{
for (int k = 0; k < 9; k++)
{
numlist[k] = control_list[k];
}
}
}
}
}
}
//function to remove invalid board cells
int remove_invalids(int board[9][9])
{
//initialization of control list (list of valid numbers) we will be making copies of this list and removing any numbers which we cannot use.
int control_list[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
remove_row_invalids(board, control_list);
remove_column_invalids(board, control_list);
remove_block_invalids(board, control_list);
return board[9][9];
}
//PLAYER SOLVING FUNCTIONS (functions for the actual game, as opposed to board generation)
//TODO
//remove "Invalid Move" cout statements on final iteration
//? change validate functions' subfunctions to return bools rather than ints?
///////////////////////
//validates a row (generally after move, or in backtracking algorithm... which is as of 8/13/21 TODO)
int validate_row(int board[9][9], int control_list[9])
{
//creation of a list of numbers 1-9
int numlist[9];
//for loop copying control list to numlist
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
//for all rows (i)
for (int i = 0; i < 9; i++)
{
//and all column indices (cells) of rows (j)
for (int j = 0; j < 9; j++)
{
//check all numbers 1-9 of numlist
for (int k = 0; k < 9; k++)
{
//if (when) a number of the control list is found to be in cell j, i
if (board[i][j] == numlist[k])
{
//remove the number in cell i, j from the number list
numlist[k] = 0;
//break out of k loop / numlist loop
break;
}
//if at the final index of k and still no match has been found
if (k == 8 && (board[i][j] != numlist[k]))
{
//print notice of invalidity and location
cout << "Invalid Row" << endl;
cout << "i: " << i << " j: " << j << endl;
//return failure
return -1;
}
}
}
}
return 0;
}
//validates a column (generally after move, or in backtracking algorithm... which is as of 8/13/21 TODO)
int validate_column(int board[9][9], int control_list[9])
{
//creation of a list of numbers 1-9
int numlist[9];
//for loop copying control list to numlist
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
//for all rows (i)
for (int i = 0; i < 9; i++)
{
//and all column indices (cells) of rows (j)
for (int j = 0; j < 9; j++)
{
//check all numbers 1-9 of numlist
for (int k = 0; k < 9; k++)
{
//if (when) a number of the control list is found to be in cell j, i
if (board[j][i] == numlist[k])
{
//remove the number in cell j, i from the number list
numlist[k] = 0;
//break out of k loop / numlist loop
break;
}
//if at the final index of k and still no match has been found
if (k == 8 && (board[j][i] != numlist[k]))
{
//print notice of invalidity and location
cout << "Invalid Column" << endl;
cout << "i: " << i << " j: " << j << endl;
//return failure
return -1;
}
}
}
}
//if we reach the end of this program, return success
return 0;
}
//validate block (3x3)
//BUGS? If any validation bugs exist, check here for errors. Shouldn't be, but functionality in this piece was copied over from invalidate_blocks, and so prepare for anything missed.
int validate_block(int board[9][9], int control_list[9])
{
//initialization of numlist to copy control list
int numlist[9];
//for loop to create a number list of 1-9 (control list exists as we are gonna need to copy it a few times)
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
// declaration of ints to keep track of the cells we are working with, relevant further down
int i = 0;
int j = 0;
//for each row of 3x3 blocks
for (int blockrow = 0; blockrow < 3; blockrow++)
{
//and each block column index therein (effectivelly each 3x3 block)
for (int blockcolumn = 0; blockcolumn < 3; blockcolumn++)
{
//and for each row within the 3x3 block
for (int row = 0; row < 3; row++)
{
//and for each cell (column index) of the 3 cell row
for (int cell = 0; cell < 3; cell++)
{
//initialize i and j to be equivalent to cell coordinates
i = row + (blockrow*3);
j = cell + (blockcolumn*3);
//for loop to parse through all values of our numlist
for (int index = 0; index < 9; index++)
{
//if we found a match between the number in our block, and the numlist at our index value
if (board[i][j] == numlist[index])
{
//remove that number from the numlist
numlist[index] = 0;
//and break out of this loop
break;
}
//if we are the final index of the list and still no match has been found
if (index == 8 && (board[i][j] != numlist[index]))
{
//print invalidity and location
cout << "Invalid Block" << endl;
cout << "i: " << i << " j: " << j << endl;
//return failure
return -1;
}
}
}
//once we have gone through the 3x3 rows and columns of the list, refresh numlist
if (row == 2)
{
for (int k = 0; k < 9; k++)
{
numlist[k] = control_list[k];
}
}
}
}
}
//if we reach the end of this program, return success
return 0;
}
//cleans the board from an invalid board, to a valid one
//TODO Fix clean / validate
int clean(int board[9][9])
{
//print statement
cout << "cleaning..." << endl;
//initialization of numlist to copy control list
int numlist[9];
//initialization of a control list
int control_list[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//for loop to create a number list of 1-9 (control list exists as we are gonna need to copy it a few times)
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
//initialize random seend
srand(time(0));
//for all rows
for (int i = 0; i < 9; i++)
{
//and for all colum indices therein
for (int j = 0; j < 9; j++)
{
//if the cell is filled
if (board[i][j] != 0)
{
//run a 1/3 chance to remove the number (just remove enough nums until the board is viable)
if (rand() % 2 == 0)
{
board[i][j] = 0;
}
}
}
}
//return the "cleaned" board
return board[9][9];
}
//validates a board
//!!! NOTE: Validate as a function is only supposed to be used in the backtracking algorithm. For board preparation remove_invalids is sufficient. In layman's terms, don't call this in main, only in the backtracking function
bool validate(int board[9][9])
{
//initialization of a control list
int control_list[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//initialization of int to hold the sum of validate_row. It will either be zero, -1, -2, or -3, as it sums the value of failed returns.
int zero_or_fail = 0;
//add the return values of validate row, validate column and validate block to zero or fail
zero_or_fail += validate_row(board, control_list);
zero_or_fail += validate_column(board, control_list);
zero_or_fail += validate_block(board, control_list);
//TODO fix the validate function
//everything below here will not run--- the validate_row, column, and block functions will only return zero so the if statement always happens
//validate needs to remove all invalids, and then we need to backtrack and attempt to solve (which will work once in a fucking blue moon, and then clean the board until its a valid board)
//if all three validate columns returned 0
if (zero_or_fail == 0)
{
//return true, indicating program success
return true;
}
//else return failure
/*cout << "Failed. Value exceeded 0. Value: " << zero_or_fail << endl;
return false;*/
//if invalid, clean the board
//Note: cleaning the board once in board generation or main is sufficient, we can toss out the program otherwise
//board[9][9] = clean(board);
//return false
return false;
}
//BACKTRACKING function(s)
//TODO create a condition in backtrack where program recognizes that no possible valid number exists, and terminates the program as a result
//Algorithm:
//for all cells of the board
// if a board cell is empty, generate a number for it
// and ensure it is valid
// if it's valid,
// continue
// else
// go back to the last certain index
// and generate a different a new number for it
// if you reach a point at which there are no valid options and you have exhausted all possibilities
// return failure
// if you have solved the board completely, and...
// if the board is valid
// return success
//
//////////////////
//TODO backtracking needs to be re-structured into a tree-like format, per standard backtracking algorithm implementations
//solves board by backtracking (used to take randomly generated possible sudoku board and check validity)
//takes as arguments the board, and the indexes we are working with
int backtrack(int board[9][9], int i, int j)
{
//initialization of a control list of valid sudoku numbers, needed for refreshing the numlist
int control_list[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//declaration of a numlist
int numlist[9];
//declaration of two void ints to be the indeces of the last uncertain number
int last_uncertain_i;
int last_uncertain_j;
//which contains the same data as the control list
for (int i = 0; i < 9; i++)
{
numlist[i] = control_list[i];
}
//for all rows
for (int i = 0; i < 9; i++)
{
//and all column indices therein
for (int j = 0; j < 9; j++)
{
//if the board at these indices is void
if (board[i][j] == 0)
{
//for all k indicies of the numlist
for (int k = 0; k < 9; /*no step we will step manually on invalid board*/)
{
//set the board equal to numlist a k index
board[i][j] = numlist[k];
//if the board is invalid
if (!validate(board))
{
//increment k and proceed to the next number
k++;
//if passed final index of k and the board remains invalid
if (k == 9)
{
//return to the last uncertain indices (in a tree like structure, we would return to a given root)
i = last_uncertain_i;
j = last_uncertain_j;
//CONSIDER:
//removing the steps of i and j and setting them manually would allows us to reverse-traverse the list if we find an invalid index. If we are 4 cells in and we find a space that is cannot be made valid, we can go back to pre-established cells.
//doing this would let us take the index currently in the filled cell, remove all numbers up to and including it from the numlist, and then try for the remainders. If we try all numbers of that cell and the next cells and there remains invalidity, we go back.
}
}
}
}
}
}
}
//conceals board spaces from valid board
//TODO
//???? What if i just concealed all duplicates and then solved for that?
int conceal_spaces(int board[9][9])
{
return 0;
}
//player guesses number
//TODO
int player_guess(int board[9][9], int guess_num)
{
//keep char list of coordinates, defines a list f values. When user types in "A", "A", program will traverse list, and find "A" as 0 index both times, and adjust block 0, 0 accordingly.
char coordinate_list[9] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
//TODO changes a number on the board to the guessed number
//the validates the number
//validate(board)
return 0;
}