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
|
/*
* This code is released under the GNU General Public License. See COPYING for
* details. Copyright 2005 P. Jordan, C. Lewis, J. Spray
* jcspray@icculus.org
*/
//#include "GNUDoku.H"
#include "sudoku.H"
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <map>
namespace sudoku
{
int Sudoku::blank(char visited[], int blanks)
{
for(int i = 0; i < blanks / 2; ++i) {
int index1 = rand() % 81;
int index2 = 80 - index1;
while(visited[index1] == 0 || visited[index2] == 0) {
index1 = rand() % 81;
index2 = 80 - index1;
}
visited[index1] = 0;
visited[index2] = 0;
}
return 0;
}
// this is only used for debugging these days
int Sudoku::pint(const Sudoku::attempt stack[], const char visited[])
{
char grid[81] = { 0 };
const char top[] = " A B C D E F G H I \n";
const char across[] = " +---+---+---#---+---+---#---+---+---+\n";
const char boss[] = " +===+===+===#===+===+===#===+===+===+\n";
const char lines[] = "%d | %c | %c | %c # %c | %c | %c # %c | %c | %c | \n";
memset(grid, ' ', sizeof(grid));
for(int i = 0; i < 81; ++i)
{
if(stack[i].index >= 0 && visited[stack[i].index])
grid[stack[i].index] = '1' + stack[i].value;
}
printf(top);
printf(across);
for(int i = 0; i < 9; ++i) {
printf(lines, i + 1,
grid[i * 9], grid[i*9+1], grid[i*9+2],
grid[i*9+3], grid[i*9+4], grid[i*9+5],
grid[i*9+6], grid[i*9+7], grid[i*9+8]);
printf(i % 3 == 2 ? boss : across);
}
return 0;
}
int Sudoku::solve( attempt stack[], int top, flags* flags, char visited[])
{
int index = 0;
do
{
while(visited[index] == 1)
++index;
stack[top].tries = 0;
stack[top].index = index;
stack[top].row = index / 9;
stack[top].col = index % 9;
stack[top].box = (stack[top].row / 3) * 3 + (stack[top].col / 3);
stack[top].value = rand() % 9;
while(1)
{
for( ; stack[top].tries < 9; stack[top].value++, stack[top].tries++)
{
if(stack[top].value == 9)
stack[top].value = 0;
if(flags->row[stack[top].row][stack[top].value]) /*Arse.*/
continue;
if(flags->col[stack[top].col][stack[top].value]) /*Arse.*/
continue;
if(flags->box[stack[top].box][stack[top].value]) /*Arse.*/
continue;
break;
}
if(stack[top].tries < 9)
break;
--top;
/* printf("Moving down stack: %d\n", top); */
flags->row[stack[top].row][stack[top].value] = 0;
flags->col[stack[top].col][stack[top].value] = 0;
flags->box[stack[top].box][stack[top].value] = 0;
visited[stack[top].index] = 0;
++stack[top].value;
++stack[top].tries;
index = stack[top].index;
}
flags->row[stack[top].row][stack[top].value] = 1;
flags->col[stack[top].col][stack[top].value] = 1;
flags->box[stack[top].box][stack[top].value] = 1;
visited[stack[top].index] = 1;
++top;
/* printf("Moving up stack: %d\n", top); */
} while(top < 81);
return 0;
}
}
|
