sudoku.c - randomcrap - random crap programs of varying quality
(HTM) git clone git://git.codemadness.org/randomcrap
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
sudoku.c (3035B)
---
1 /* sudoku solver / hinter */
2 #include <stdio.h>
3 #include <string.h>
4
5 static unsigned char field[9][9];
6 static unsigned int state[9][9];
7 static int mode = 's'; /* solve */
8
9 void
10 readin(void)
11 {
12 int c, x, y;
13
14 for (x = 0, y = 0; (c = getchar()) != EOF;) {
15 if (c == '.')
16 c = '0';
17 if (!(c >= '0' && c <= '9') || x > 9 || y > 9)
18 continue;
19
20 field[y][x] = c - '0';
21 state[y][x] = c == '0' ? ~0 : (1 << (field[y][x] - 1));
22 if (++x >= 9) {
23 x = 0;
24 if (++y >= 9)
25 break;
26 }
27 }
28 }
29
30 void
31 show(void)
32 {
33 int x, y;
34
35 for (y = 0; y < 9; y++) {
36 if (y && (y % 3) == 0)
37 puts("---+---+---");
38 for (x = 0; x < 9; x++) {
39 if (x && (x % 3) == 0)
40 putchar('|');
41 putchar(field[y][x] ? field[y][x] + '0' : '.');
42 }
43 putchar('\n');
44 }
45 }
46
47 void
48 updatestates(void)
49 {
50 int x, y, z, x2, y2;
51
52 for (y = 0; y < 9; y++) {
53 for (x = 0; x < 9; x++) {
54 if (field[y][x])
55 continue;
56 for (z = 0; z < 9; z++) {
57 if (field[y][z])
58 state[y][x] &= ~(1 << (field[y][z] - 1));
59 if (field[z][x])
60 state[y][x] &= ~(1 << (field[z][x] - 1));
61
62 x2 = x - (x % 3) + (z / 3);
63 y2 = y - (y % 3) + (z % 3);
64 if (field[y2][x2])
65 state[y][x] &= ~(1 << (field[y2][x2] - 1));
66 }
67 }
68 }
69 }
70
71 int
72 countpos(unsigned int state)
73 {
74 int p = 0, z;
75
76 for (z = 0; z < 9; z++) {
77 if (state & (1 << z))
78 p++;
79 }
80 return p;
81 }
82
83 void
84 hint(void)
85 {
86 int x, y;
87
88 for (y = 0; y < 9; y++) {
89 for (x = 0; x < 9; x++) {
90 if (field[y][x])
91 continue;
92 /* show when one possibility left */
93 if (countpos(state[y][x]) == 1)
94 printf("(%d, %d)\n", x + 1, y + 1);
95 }
96 }
97 }
98
99 int
100 fillin(int x, int y)
101 {
102 unsigned int s;
103 int n, pos, x2, y2, z;
104
105 for (z = 0, s = ~0; z < 9; z++) {
106 if (y != z)
107 s &= ~state[z][x];
108 }
109 if (countpos(s) == 1)
110 goto fill;
111
112 for (z = 0, s = ~0; z < 9; z++) {
113 if (x != z)
114 s &= ~state[y][z];
115 }
116 if (countpos(s) == 1)
117 goto fill;
118
119 for (z = 0, s = ~0; z < 9; z++) {
120 x2 = x - (x % 3) + (z / 3);
121 y2 = y - (y % 3) + (z % 3);
122 if (x != x2 || y != y2)
123 s &= ~state[y2][x2];
124 }
125 if (countpos(s) == 1)
126 goto fill;
127
128 /* fill in if one possibility */
129 s = state[y][x];
130
131 fill:
132 for (pos = 0, z = 0; z < 9 && pos <= 1; z++) {
133 if (s & (1 << z)) {
134 pos++;
135 n = z;
136 }
137 }
138 if (pos == 1) {
139 /* hint mode */
140 if (mode == 'h') {
141 #if 1
142 if ((x + y) & 1)
143 printf("on column: %d\n", x + 1);
144 else
145 printf("on row: %d\n", y + 1);
146 #else
147 printf("on %d, %d\n", x + 1, y + 1);
148 // printf("on %d, %d = %d\n", x + 1, y + 1, n + 1);
149 #endif
150 return 0; /* non-dirty */
151 }
152 field[y][x] = n + 1;
153 state[y][x] = 1 << n;
154 }
155 return pos == 1;
156 }
157
158 /* human-like solving (no recursive brute-forcing) */
159 void
160 solve(void)
161 {
162 int changed = 1, x, y;
163
164 while (changed) {
165 changed = 0;
166 for (y = 0; y < 9; y++) {
167 for (x = 0; x < 9; x++) {
168 if (!field[y][x] && fillin(x, y)) {
169 updatestates();
170 changed = 1;
171 }
172 }
173 }
174 }
175 }
176
177 int
178 main(int argc, char *argv[])
179 {
180 readin();
181 updatestates();
182
183 if (argc == 2 && !strcmp(argv[1], "-h"))
184 mode = 'h'; /* hint */
185 solve();
186 show();
187
188 return 0;
189 }