diff options
author | Dave Chapman <dave@dchapman.com> | 2006-04-01 18:38:34 +0000 |
---|---|---|
committer | Dave Chapman <dave@dchapman.com> | 2006-04-01 18:38:34 +0000 |
commit | 0f619c65bab2465ffa84eb64cc62fe56506121f8 (patch) | |
tree | f8a9387673b1f6f7764620cbf10978e3b05d26f4 /apps/plugins/sudoku/generator.c | |
parent | 9fad701934a784e110edbff5556e21efe9c059d9 (diff) | |
download | rockbox-0f619c65bab2465ffa84eb64cc62fe56506121f8.tar.gz rockbox-0f619c65bab2465ffa84eb64cc62fe56506121f8.zip |
Move Sudoku plugin into its own subdirectory and add a random game generator.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@9407 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'apps/plugins/sudoku/generator.c')
-rw-r--r-- | apps/plugins/sudoku/generator.c | 1097 |
1 files changed, 1097 insertions, 0 deletions
diff --git a/apps/plugins/sudoku/generator.c b/apps/plugins/sudoku/generator.c new file mode 100644 index 0000000000..d43e970ab8 --- /dev/null +++ b/apps/plugins/sudoku/generator.c | |||
@@ -0,0 +1,1097 @@ | |||
1 | /* sudoku.c - sudoku game | ||
2 | * | ||
3 | * Writing a fun Su-Do-Ku game has turned out to be a difficult exercise. | ||
4 | * The biggest difficulty is keeping the game fun - and this means allowing | ||
5 | * the user to make mistakes. The game is not much fun if it prevents the | ||
6 | * user from making moves, or if it informs them of an incorrect move. | ||
7 | * With movement constraints, the 'game' is little more than an automated | ||
8 | * solver (and no fun at all). | ||
9 | * | ||
10 | * Another challenge is generating good puzzles that are entertaining to | ||
11 | * solve. It is certainly true that there is an art to creating good | ||
12 | * Su-Do-Ku puzzles, and that good hand generated puzzles are more | ||
13 | * entertaining than many computer generated puzzles - I just hope that | ||
14 | * the algorithm implemented here provides fun puzzles. It is an area | ||
15 | * that needs work. The puzzle classification is very simple, and could | ||
16 | * also do with work. Finally, understanding the automatically generated | ||
17 | * hints is sometimes more work than solving the puzzle - a better, and | ||
18 | * more human friendly, mechanism is needed. | ||
19 | * | ||
20 | * Comments, suggestions, and contributions are always welcome - send email | ||
21 | * to: mike 'at' laurasia.com.au. Note that this code assumes a single | ||
22 | * threaded process, makes extensive use of global variables, and has | ||
23 | * not been written to be reused in other applications. The code makes no | ||
24 | * use of dynamic memory allocation, and hence, requires no heap. It should | ||
25 | * also run with minimal stack space. | ||
26 | * | ||
27 | * This code and accompanying files have been placed into the public domain | ||
28 | * by Michael Kennett, July 2005. It is provided without any warranty | ||
29 | * whatsoever, and in no event shall Michael Kennett be liable for | ||
30 | * any damages of any kind, however caused, arising from this software. | ||
31 | */ | ||
32 | |||
33 | #include "plugin.h" | ||
34 | |||
35 | #include "sudoku.h" | ||
36 | #include "templates.h" | ||
37 | |||
38 | extern struct plugin_api* rb; | ||
39 | |||
40 | #define assert(x) | ||
41 | |||
42 | /* Common state encoding in a 32-bit integer: | ||
43 | * bits 0-6 index | ||
44 | * 7-15 state [bit high signals digits not possible] | ||
45 | * 16-19 digit | ||
46 | * 20 fixed [set if digit initially fixed] | ||
47 | * 21 choice [set if solver chose this digit] | ||
48 | * 22 ignore [set if ignored by reapply()] | ||
49 | * 23 unused | ||
50 | * 24-26 hint | ||
51 | * 27-31 unused | ||
52 | */ | ||
53 | #define INDEX_MASK 0x0000007f | ||
54 | #define GET_INDEX(val) (INDEX_MASK&(val)) | ||
55 | #define SET_INDEX(val) (val) | ||
56 | |||
57 | #define STATE_MASK 0x0000ff80 | ||
58 | #define STATE_SHIFT (7-1) /* digits 1..9 */ | ||
59 | #define DIGIT_STATE(digit) (1<<(STATE_SHIFT+(digit))) | ||
60 | |||
61 | #define DIGIT_MASK 0x000f0000 | ||
62 | #define DIGIT_SHIFT 16 | ||
63 | #define GET_DIGIT(val) (((val)&DIGIT_MASK)>>(DIGIT_SHIFT)) | ||
64 | #define SET_DIGIT(val) ((val)<<(DIGIT_SHIFT)) | ||
65 | |||
66 | #define FIXED 0x00100000 | ||
67 | #define CHOICE 0x00200000 | ||
68 | #define IGNORED 0x00400000 | ||
69 | |||
70 | /* Hint codes (c.f. singles(), pairs(), findmoves()) */ | ||
71 | #define HINT_ROW 0x01000000 | ||
72 | #define HINT_COLUMN 0x02000000 | ||
73 | #define HINT_BLOCK 0x04000000 | ||
74 | |||
75 | /* For a general board it may be necessary to do backtracking (i.e. to | ||
76 | * rewind the board to an earlier state), and make choices during the | ||
77 | * solution process. This can be implemented naturally using recursion, | ||
78 | * but it is more efficient to maintain a single board. | ||
79 | */ | ||
80 | static int board[ 81 ]; | ||
81 | |||
82 | /* Addressing board elements: linear array 0..80 */ | ||
83 | #define ROW(idx) ((idx)/9) | ||
84 | #define COLUMN(idx) ((idx)%9) | ||
85 | #define BLOCK(idx) (3*(ROW(idx)/3)+(COLUMN(idx)/3)) | ||
86 | #define INDEX(row,col) (9*(row)+(col)) | ||
87 | |||
88 | /* Blocks indexed 0..9 */ | ||
89 | #define IDX_BLOCK(row,col) (3*((row)/3)+((col)/3)) | ||
90 | #define TOP_LEFT(block) (INDEX(block/3,block%3)) | ||
91 | |||
92 | /* Board state */ | ||
93 | #define STATE(idx) ((board[idx])&STATE_MASK) | ||
94 | #define DIGIT(idx) (GET_DIGIT(board[idx])) | ||
95 | #define HINT(idx) ((board[idx])&HINT_MASK) | ||
96 | #define IS_EMPTY(idx) (0 == DIGIT(idx)) | ||
97 | #define DISALLOWED(idx,digit) ((board[idx])&DIGIT_STATE(digit)) | ||
98 | #define IS_FIXED(idx) (board[idx]&FIXED) | ||
99 | |||
100 | /* Record move history, and maintain a counter for the current | ||
101 | * move number. Concessions are made for the user interface, and | ||
102 | * allow digit 0 to indicate clearing a square. The move history | ||
103 | * is used to support 'undo's for the user interface, and hence | ||
104 | * is larger than required - there is sufficient space to solve | ||
105 | * the puzzle, undo every move, and then redo the puzzle - and | ||
106 | * if the user requires more space, then the full history will be | ||
107 | * lost. | ||
108 | */ | ||
109 | static int idx_history; | ||
110 | static int history[ 3 * 81 ]; | ||
111 | |||
112 | /* Possible moves for a given board (c.f. fillmoves()). | ||
113 | * Also used by choice() when the deterministic solver has failed, | ||
114 | * and for calculating user hints. The number of hints is stored | ||
115 | * in num_hints, or -1 if no hints calculated. The number of hints | ||
116 | * requested by the user since their last move is stored in req_hints; | ||
117 | * if the user keeps requesting hints, start giving more information. | ||
118 | * Finally, record the last hint issued to the user; attempt to give | ||
119 | * different hints each time. | ||
120 | */ | ||
121 | static int idx_possible; | ||
122 | static int possible[ 81 ]; | ||
123 | |||
124 | static int pass; /* count # passes of deterministic solver */ | ||
125 | |||
126 | /* Support for template file */ | ||
127 | static int tmplt[ 81 ]; /* Template indices */ | ||
128 | static int len_tmplt; /* Number of template indices */ | ||
129 | |||
130 | /* Reset global state */ | ||
131 | static | ||
132 | void | ||
133 | reset( void ) | ||
134 | { | ||
135 | rb->memset( board, 0x00, sizeof( board ) ); | ||
136 | rb->memset( history, 0x00, sizeof( history ) ); | ||
137 | idx_history = 0; | ||
138 | pass = 0; | ||
139 | } | ||
140 | |||
141 | /* Management of the move history - compression */ | ||
142 | static | ||
143 | void | ||
144 | compress( int limit ) | ||
145 | { | ||
146 | int i, j; | ||
147 | for( i = j = 0 ; i < idx_history && j < limit ; ++i ) | ||
148 | if( !( history[ i ] & IGNORED ) ) | ||
149 | history[ j++ ] = history[ i ]; | ||
150 | for( ; i < idx_history ; ++i ) | ||
151 | history[ j++ ] = history[ i ]; | ||
152 | idx_history = j; | ||
153 | } | ||
154 | |||
155 | /* Management of the move history - adding a move */ | ||
156 | static | ||
157 | void | ||
158 | add_move( int idx, int digit, int choice ) | ||
159 | { | ||
160 | int i; | ||
161 | |||
162 | if( sizeof( history ) / sizeof( int ) == idx_history ) | ||
163 | compress( 81 ); | ||
164 | |||
165 | /* Never ignore the last move */ | ||
166 | history[ idx_history++ ] = SET_INDEX( idx ) | SET_DIGIT( digit ) | choice; | ||
167 | |||
168 | /* Ignore all previous references to idx */ | ||
169 | for( i = idx_history - 2 ; 0 <= i ; --i ) | ||
170 | if( GET_INDEX( history[ i ] ) == idx ) | ||
171 | { | ||
172 | history[ i ] |= IGNORED; | ||
173 | break; | ||
174 | } | ||
175 | } | ||
176 | |||
177 | /* Iteration over rows/columns/blocks handled by specialised code. | ||
178 | * Each function returns a block index - call must manage element/idx. | ||
179 | */ | ||
180 | static | ||
181 | int | ||
182 | idx_row( int el, int idx ) /* Index within a row */ | ||
183 | { | ||
184 | return INDEX( el, idx ); | ||
185 | } | ||
186 | |||
187 | static | ||
188 | int | ||
189 | idx_column( int el, int idx ) /* Index within a column */ | ||
190 | { | ||
191 | return INDEX( idx, el ); | ||
192 | } | ||
193 | |||
194 | static | ||
195 | int | ||
196 | idx_block( int el, int idx ) /* Index within a block */ | ||
197 | { | ||
198 | return INDEX( 3 * ( el / 3 ) + idx / 3, 3 * ( el % 3 ) + idx % 3 ); | ||
199 | } | ||
200 | |||
201 | /* Update board state after setting a digit (clearing not handled) | ||
202 | */ | ||
203 | static | ||
204 | void | ||
205 | update( int idx ) | ||
206 | { | ||
207 | const int row = ROW( idx ); | ||
208 | const int col = COLUMN( idx ); | ||
209 | const int block = IDX_BLOCK( row, col ); | ||
210 | const int mask = DIGIT_STATE( DIGIT( idx ) ); | ||
211 | int i; | ||
212 | |||
213 | board[ idx ] |= STATE_MASK; /* filled - no choice possible */ | ||
214 | |||
215 | /* Digit cannot appear in row, column or block */ | ||
216 | for( i = 0 ; i < 9 ; ++i ) | ||
217 | { | ||
218 | board[ idx_row( row, i ) ] |= mask; | ||
219 | board[ idx_column( col, i ) ] |= mask; | ||
220 | board[ idx_block( block, i ) ] |= mask; | ||
221 | } | ||
222 | } | ||
223 | |||
224 | /* Refresh board state, given move history. Note that this can yield | ||
225 | * an incorrect state if the user has made errors - return -1 if an | ||
226 | * incorrect state is generated; else return 0 for a correct state. | ||
227 | */ | ||
228 | static | ||
229 | int | ||
230 | reapply( void ) | ||
231 | { | ||
232 | int digit, idx, j; | ||
233 | int allok = 0; | ||
234 | rb->memset( board, 0x00, sizeof( board ) ); | ||
235 | for( j = 0 ; j < idx_history ; ++j ) | ||
236 | if( !( history[ j ] & IGNORED ) && 0 != GET_DIGIT( history[ j ] ) ) | ||
237 | { | ||
238 | idx = GET_INDEX( history[ j ] ); | ||
239 | digit = GET_DIGIT( history[ j ] ); | ||
240 | if( !IS_EMPTY( idx ) || DISALLOWED( idx, digit ) ) | ||
241 | allok = -1; | ||
242 | board[ idx ] = SET_DIGIT( digit ); | ||
243 | if( history[ j ] & FIXED ) | ||
244 | board[ idx ] |= FIXED; | ||
245 | update( idx ); | ||
246 | } | ||
247 | return allok; | ||
248 | } | ||
249 | |||
250 | /* Clear moves, leaving fixed squares | ||
251 | */ | ||
252 | static | ||
253 | void | ||
254 | clear_moves( void ) | ||
255 | { | ||
256 | for( idx_history = 0 ; history[ idx_history ] & FIXED ; ++idx_history ) | ||
257 | ; | ||
258 | reapply( ); | ||
259 | } | ||
260 | |||
261 | static int digits[ 9 ]; /* # digits expressed in element square */ | ||
262 | static int counts[ 9 ]; /* Count of digits (c.f. count_set_digits()) */ | ||
263 | |||
264 | /* Count # set bits (within STATE_MASK) */ | ||
265 | static | ||
266 | int | ||
267 | numset( int mask ) | ||
268 | { | ||
269 | int i, n = 0; | ||
270 | for( i = STATE_SHIFT + 1 ; i <= STATE_SHIFT + 9 ; ++i ) | ||
271 | if( mask & (1<<i) ) | ||
272 | ++n; | ||
273 | else | ||
274 | ++counts[ i - STATE_SHIFT - 1 ]; | ||
275 | return n; | ||
276 | } | ||
277 | |||
278 | static | ||
279 | void | ||
280 | count_set_digits( int el, int (*idx_fn)( int, int ) ) | ||
281 | { | ||
282 | int i; | ||
283 | rb->memset( counts, 0x00, sizeof( counts ) ); | ||
284 | for( i = 0 ; i < 9 ; ++i ) | ||
285 | digits[ i ] = numset( board[ (*idx_fn)( el, i ) ] ); | ||
286 | } | ||
287 | |||
288 | /* Fill square with given digit, and update state. | ||
289 | * Returns 0 on success, else -1 on error (i.e. invalid fill) | ||
290 | */ | ||
291 | static | ||
292 | int | ||
293 | fill( int idx, int digit ) | ||
294 | { | ||
295 | assert( 0 != digit ); | ||
296 | |||
297 | if( !IS_EMPTY( idx ) ) | ||
298 | return ( DIGIT( idx ) == digit ) ? 0 : -1; | ||
299 | |||
300 | if( DISALLOWED( idx, digit ) ) | ||
301 | return -1; | ||
302 | |||
303 | board[ idx ] = SET_DIGIT( digit ); | ||
304 | update( idx ); | ||
305 | add_move( idx, digit, 0 ); | ||
306 | |||
307 | return 0; | ||
308 | } | ||
309 | |||
310 | /* Find all squares with a single digit allowed -- do not mutate board */ | ||
311 | static | ||
312 | void | ||
313 | singles( int el, int (*idx_fn)( int, int ), int hintcode ) | ||
314 | { | ||
315 | int i, j, idx; | ||
316 | |||
317 | count_set_digits( el, idx_fn ); | ||
318 | |||
319 | for( i = 0 ; i < 9 ; ++i ) | ||
320 | { | ||
321 | if( 1 == counts[ i ] ) | ||
322 | { | ||
323 | /* Digit 'i+1' appears just once in the element */ | ||
324 | for( j = 0 ; j < 9 ; ++j ) | ||
325 | { | ||
326 | idx = (*idx_fn)( el, j ); | ||
327 | if( !DISALLOWED( idx, i + 1 ) && idx_possible < 81 ) | ||
328 | possible[ idx_possible++ ] = SET_INDEX( idx ) | ||
329 | | SET_DIGIT( i + 1 ) | ||
330 | | hintcode; | ||
331 | } | ||
332 | } | ||
333 | if( 8 == digits[ i ] ) | ||
334 | { | ||
335 | /* 8 digits are masked at this position - just one remaining */ | ||
336 | idx = (*idx_fn)( el, i ); | ||
337 | for( j = 1 ; j <= 9 ; ++j ) | ||
338 | if( 0 == ( STATE( idx ) & DIGIT_STATE( j ) ) && idx_possible < 81 ) | ||
339 | possible[ idx_possible++ ] = SET_INDEX( idx ) | ||
340 | | SET_DIGIT( j ) | ||
341 | | hintcode; | ||
342 | } | ||
343 | } | ||
344 | } | ||
345 | |||
346 | /* Given the board state, find all possible 'moves' (i.e. squares with just | ||
347 | * a single digit). | ||
348 | * | ||
349 | * Returns the number of (deterministic) moves (and fills the moves array), | ||
350 | * or 0 if no moves are possible. This function does not mutate the board | ||
351 | * state, and hence, can return the same move multiple times (with | ||
352 | * different hints). | ||
353 | */ | ||
354 | static | ||
355 | int | ||
356 | findmoves( void ) | ||
357 | { | ||
358 | int i; | ||
359 | |||
360 | idx_possible = 0; | ||
361 | for( i = 0 ; i < 9 ; ++i ) | ||
362 | { | ||
363 | singles( i, idx_row, HINT_ROW ); | ||
364 | singles( i, idx_column, HINT_COLUMN ); | ||
365 | singles( i, idx_block, HINT_BLOCK ); | ||
366 | } | ||
367 | return idx_possible; | ||
368 | } | ||
369 | |||
370 | /* Strategies for refining the board state | ||
371 | * - 'pairs' if there are two unfilled squares in a given row/column/ | ||
372 | * block with the same state, and just two possibilities, | ||
373 | * then all other unfilled squares in the row/column/block | ||
374 | * CANNOT be either of these digits. | ||
375 | * - 'block' if the unknown squares in a block all appear in the same | ||
376 | * row or column, then all unknown squares outside the block | ||
377 | * and in the same row/column cannot be any of the unknown | ||
378 | * squares in the block. | ||
379 | * - 'common' if all possible locations for a digit in a block appear | ||
380 | * in a row or column, then that digit cannot appear outside | ||
381 | * the block in the same row or column. | ||
382 | * - 'position2' if the positions of 2 unknown digits in a block match | ||
383 | * identically in precisely 2 positions, then those 2 positions | ||
384 | * can only contain the 2 unknown digits. | ||
385 | * | ||
386 | * Recall that each state bit uses a 1 to prevent a digit from | ||
387 | * filling that square. | ||
388 | */ | ||
389 | |||
390 | static | ||
391 | void | ||
392 | pairs( int el, int (*idx_fn)( int, int ) ) | ||
393 | { | ||
394 | int i, j, k, mask, idx; | ||
395 | for( i = 0 ; i < 8 ; ++i ) | ||
396 | if( 7 == digits[ i ] ) /* 2 digits unknown */ | ||
397 | for( j = i + 1 ; j < 9 ; ++j ) | ||
398 | { | ||
399 | idx = (*idx_fn)( el, i ); | ||
400 | if( STATE( idx ) == STATE( (*idx_fn)( el, j ) ) ) | ||
401 | { | ||
402 | /* Found a row/column pair - mask other entries */ | ||
403 | mask = STATE_MASK ^ (STATE_MASK & board[ idx ] ); | ||
404 | for( k = 0 ; k < i ; ++k ) | ||
405 | board[ (*idx_fn)( el, k ) ] |= mask; | ||
406 | for( k = i + 1 ; k < j ; ++k ) | ||
407 | board[ (*idx_fn)( el, k ) ] |= mask; | ||
408 | for( k = j + 1 ; k < 9 ; ++k ) | ||
409 | board[ (*idx_fn)( el, k ) ] |= mask; | ||
410 | digits[ j ] = -1; /* now processed */ | ||
411 | } | ||
412 | } | ||
413 | } | ||
414 | |||
415 | /* Worker: mask elements outside block */ | ||
416 | static | ||
417 | void | ||
418 | exmask( int mask, int block, int el, int (*idx_fn)( int, int ) ) | ||
419 | { | ||
420 | int i, idx; | ||
421 | |||
422 | for( i = 0 ; i < 9 ; ++i ) | ||
423 | { | ||
424 | idx = (*idx_fn)( el, i ); | ||
425 | if( block != BLOCK( idx ) && IS_EMPTY( idx ) ) | ||
426 | board[ idx ] |= mask; | ||
427 | } | ||
428 | } | ||
429 | |||
430 | /* Worker for block() */ | ||
431 | static | ||
432 | void | ||
433 | exblock( int block, int el, int (*idx_fn)( int, int ) ) | ||
434 | { | ||
435 | int i, idx, mask; | ||
436 | |||
437 | /* By assumption, all unknown squares in the block appear in the | ||
438 | * same row/column, so to construct a mask for these squares, it | ||
439 | * is sufficient to invert the mask for the known squares in the | ||
440 | * block. | ||
441 | */ | ||
442 | mask = 0; | ||
443 | for( i = 0 ; i < 9 ; ++i ) | ||
444 | { | ||
445 | idx = idx_block( block, i ); | ||
446 | if( !IS_EMPTY( idx ) ) | ||
447 | mask |= DIGIT_STATE( DIGIT( idx ) ); | ||
448 | } | ||
449 | exmask( mask ^ STATE_MASK, block, el, idx_fn ); | ||
450 | } | ||
451 | |||
452 | static | ||
453 | void | ||
454 | block( int el ) | ||
455 | { | ||
456 | int i, idx = 0, row, col; | ||
457 | |||
458 | /* Find first unknown square */ | ||
459 | for( i = 0 ; i < 9 && !IS_EMPTY( idx = idx_block( el, i ) ) ; ++i ) | ||
460 | ; | ||
461 | if( i < 9 ) | ||
462 | { | ||
463 | assert( IS_EMPTY( idx ) ); | ||
464 | row = ROW( idx ); | ||
465 | col = COLUMN( idx ); | ||
466 | for( ++i ; i < 9 ; ++i ) | ||
467 | { | ||
468 | idx = idx_block( el, i ); | ||
469 | if( IS_EMPTY( idx ) ) | ||
470 | { | ||
471 | if( ROW( idx ) != row ) | ||
472 | row = -1; | ||
473 | if( COLUMN( idx ) != col ) | ||
474 | col = -1; | ||
475 | } | ||
476 | } | ||
477 | if( 0 <= row ) | ||
478 | exblock( el, row, idx_row ); | ||
479 | if( 0 <= col ) | ||
480 | exblock( el, col, idx_column ); | ||
481 | } | ||
482 | } | ||
483 | |||
484 | static | ||
485 | void | ||
486 | common( int el ) | ||
487 | { | ||
488 | int i, idx, row, col, digit, mask; | ||
489 | |||
490 | for( digit = 1 ; digit <= 9 ; ++digit ) | ||
491 | { | ||
492 | mask = DIGIT_STATE( digit ); | ||
493 | row = col = -1; /* Value '9' indicates invalid */ | ||
494 | for( i = 0 ; i < 9 ; ++i ) | ||
495 | { | ||
496 | /* Digit possible? */ | ||
497 | idx = idx_block( el, i ); | ||
498 | if( IS_EMPTY( idx ) && 0 == ( board[ idx ] & mask ) ) | ||
499 | { | ||
500 | if( row < 0 ) | ||
501 | row = ROW( idx ); | ||
502 | else | ||
503 | if( row != ROW( idx ) ) | ||
504 | row = 9; /* Digit appears in multiple rows */ | ||
505 | if( col < 0 ) | ||
506 | col = COLUMN( idx ); | ||
507 | else | ||
508 | if( col != COLUMN( idx ) ) | ||
509 | col = 9; /* Digit appears in multiple columns */ | ||
510 | } | ||
511 | } | ||
512 | if( -1 != row && row < 9 ) | ||
513 | exmask( mask, el, row, idx_row ); | ||
514 | if( -1 != col && col < 9 ) | ||
515 | exmask( mask, el, col, idx_column ); | ||
516 | } | ||
517 | } | ||
518 | |||
519 | /* Encoding of positions of a digit (c.f. position2()) - abuse DIGIT_STATE */ | ||
520 | static int posn_digit[ 10 ]; | ||
521 | |||
522 | static | ||
523 | void | ||
524 | position2( int el ) | ||
525 | { | ||
526 | int digit, digit2, i, mask, mask2, posn, count, idx; | ||
527 | |||
528 | /* Calculate positions of each digit within block */ | ||
529 | for( digit = 1 ; digit <= 9 ; ++digit ) | ||
530 | { | ||
531 | mask = DIGIT_STATE( digit ); | ||
532 | posn_digit[ digit ] = count = posn = 0; | ||
533 | for( i = 0 ; i < 9 ; ++i ) | ||
534 | if( 0 == ( mask & board[ idx_block( el, i ) ] ) ) | ||
535 | { | ||
536 | ++count; | ||
537 | posn |= DIGIT_STATE( i ); | ||
538 | } | ||
539 | if( 2 == count ) | ||
540 | posn_digit[ digit ] = posn; | ||
541 | } | ||
542 | /* Find pairs of matching positions, and mask */ | ||
543 | for( digit = 1 ; digit < 9 ; ++digit ) | ||
544 | if( 0 != posn_digit[ digit ] ) | ||
545 | for( digit2 = digit + 1 ; digit2 <= 9 ; ++digit2 ) | ||
546 | if( posn_digit[ digit ] == posn_digit[ digit2 ] ) | ||
547 | { | ||
548 | mask = STATE_MASK | ||
549 | ^ ( DIGIT_STATE( digit ) | DIGIT_STATE( digit2 ) ); | ||
550 | mask2 = DIGIT_STATE( digit ); | ||
551 | for( i = 0 ; i < 9 ; ++i ) | ||
552 | { | ||
553 | idx = idx_block( el, i ); | ||
554 | if( 0 == ( mask2 & board[ idx ] ) ) | ||
555 | { | ||
556 | assert( 0 == (DIGIT_STATE(digit2) & board[idx]) ); | ||
557 | board[ idx ] |= mask; | ||
558 | } | ||
559 | } | ||
560 | posn_digit[ digit ] = posn_digit[ digit2 ] = 0; | ||
561 | break; | ||
562 | } | ||
563 | } | ||
564 | |||
565 | /* Find some moves for the board; starts with a simple approach (finding | ||
566 | * singles), and if no moves found, starts using more involved strategies | ||
567 | * until a move is found. The more advanced strategies can mask states | ||
568 | * in the board, making this an efficient mechanism, but difficult for | ||
569 | * a human to understand. | ||
570 | */ | ||
571 | static | ||
572 | int | ||
573 | allmoves( void ) | ||
574 | { | ||
575 | int i, n; | ||
576 | |||
577 | n = findmoves( ); | ||
578 | if( 0 < n ) | ||
579 | return n; | ||
580 | |||
581 | for( i = 0 ; i < 9 ; ++i ) | ||
582 | { | ||
583 | count_set_digits( i, idx_row ); | ||
584 | pairs( i, idx_row ); | ||
585 | |||
586 | count_set_digits( i, idx_column ); | ||
587 | pairs( i, idx_column ); | ||
588 | |||
589 | count_set_digits( i, idx_block ); | ||
590 | pairs( i, idx_block ); | ||
591 | } | ||
592 | n = findmoves( ); | ||
593 | if( 0 < n ) | ||
594 | return n; | ||
595 | |||
596 | for( i = 0 ; i < 9 ; ++i ) | ||
597 | { | ||
598 | block( i ); | ||
599 | common( i ); | ||
600 | position2( i ); | ||
601 | } | ||
602 | return findmoves( ); | ||
603 | } | ||
604 | |||
605 | /* Helper: sort based on index */ | ||
606 | static | ||
607 | int | ||
608 | cmpindex( const void * a, const void * b ) | ||
609 | { | ||
610 | return GET_INDEX( *((const int *)b) ) - GET_INDEX( *((const int *)a) ); | ||
611 | } | ||
612 | |||
613 | /* Return number of hints. The hints mechanism should attempt to find | ||
614 | * 'easy' moves first, and if none are possible, then try for more | ||
615 | * cryptic moves. | ||
616 | */ | ||
617 | int | ||
618 | findhints( void ) | ||
619 | { | ||
620 | int i, n, mutated = 0; | ||
621 | |||
622 | n = findmoves( ); | ||
623 | if( n < 2 ) | ||
624 | { | ||
625 | /* Each call to pairs() can mutate the board state, making the | ||
626 | * hints very, very cryptic... so later undo the mutations. | ||
627 | */ | ||
628 | for( i = 0 ; i < 9 ; ++i ) | ||
629 | { | ||
630 | count_set_digits( i, idx_row ); | ||
631 | pairs( i, idx_row ); | ||
632 | |||
633 | count_set_digits( i, idx_column ); | ||
634 | pairs( i, idx_column ); | ||
635 | |||
636 | count_set_digits( i, idx_block ); | ||
637 | pairs( i, idx_block ); | ||
638 | } | ||
639 | mutated = 1; | ||
640 | n = findmoves( ); | ||
641 | } | ||
642 | if( n < 2 ) | ||
643 | { | ||
644 | for( i = 0 ; i < 9 ; ++i ) | ||
645 | { | ||
646 | block( i ); | ||
647 | common( i ); | ||
648 | } | ||
649 | mutated = 1; | ||
650 | n = findmoves( ); | ||
651 | } | ||
652 | |||
653 | /* Sort the possible moves, and allow just one hint per square */ | ||
654 | if( 0 < n ) | ||
655 | { | ||
656 | int i, j; | ||
657 | |||
658 | rb->qsort( possible, n, sizeof( int ), cmpindex ); | ||
659 | for( i = 0, j = 1 ; j < n ; ++j ) | ||
660 | { | ||
661 | if( GET_INDEX( possible[ i ] ) == GET_INDEX( possible[ j ] ) ) | ||
662 | { | ||
663 | /* Let the user make mistakes - do not assume the | ||
664 | * board is in a consistent state. | ||
665 | */ | ||
666 | if( GET_DIGIT( possible[i] ) == GET_DIGIT( possible[j] ) ) | ||
667 | possible[ i ] |= possible[ j ]; | ||
668 | } | ||
669 | else | ||
670 | i = j; | ||
671 | } | ||
672 | n = i + 1; | ||
673 | } | ||
674 | |||
675 | /* Undo any mutations of the board state */ | ||
676 | if( mutated ) | ||
677 | reapply( ); | ||
678 | |||
679 | return n; | ||
680 | } | ||
681 | |||
682 | /* Deterministic solver; return 0 on success, else -1 on error. | ||
683 | */ | ||
684 | static | ||
685 | int | ||
686 | deterministic( void ) | ||
687 | { | ||
688 | int i, n; | ||
689 | |||
690 | n = allmoves( ); | ||
691 | while( 0 < n ) | ||
692 | { | ||
693 | ++pass; | ||
694 | for( i = 0 ; i < n ; ++i ) | ||
695 | if( -1 == fill( GET_INDEX( possible[ i ] ), | ||
696 | GET_DIGIT( possible[ i ] ) ) ) | ||
697 | return -1; | ||
698 | n = allmoves( ); | ||
699 | } | ||
700 | return 0; | ||
701 | } | ||
702 | |||
703 | /* Return index of square for choice. | ||
704 | * | ||
705 | * If no choice is possible (i.e. board solved or inconsistent), | ||
706 | * return -1. | ||
707 | * | ||
708 | * The current implementation finds a square with the minimum | ||
709 | * number of unknown digits (i.e. maximum # masked digits). | ||
710 | */ | ||
711 | static | ||
712 | int | ||
713 | cmp( const void * e1, const void * e2 ) | ||
714 | { | ||
715 | return GET_DIGIT( *(const int *)e2 ) - GET_DIGIT( *(const int *)e1 ); | ||
716 | } | ||
717 | |||
718 | static | ||
719 | int | ||
720 | choice( void ) | ||
721 | { | ||
722 | int i, n; | ||
723 | for( n = i = 0 ; i < 81 ; ++i ) | ||
724 | if( IS_EMPTY( i ) ) | ||
725 | { | ||
726 | possible[ n ] = SET_INDEX( i ) | SET_DIGIT( numset( board[ i ] ) ); | ||
727 | |||
728 | /* Inconsistency if square unknown, but nothing possible */ | ||
729 | if( 9 == GET_DIGIT( possible[ n ] ) ) | ||
730 | return -2; | ||
731 | ++n; | ||
732 | } | ||
733 | |||
734 | if( 0 == n ) | ||
735 | return -1; /* All squares known */ | ||
736 | |||
737 | rb->qsort( possible, n, sizeof( possible[ 0 ] ), cmp ); | ||
738 | return GET_INDEX( possible[ 0 ] ); | ||
739 | } | ||
740 | |||
741 | /* Choose a digit for the given square. | ||
742 | * The starting digit is passed as a parameter. | ||
743 | * Returns -1 if no choice possible. | ||
744 | */ | ||
745 | static | ||
746 | int | ||
747 | choose( int idx, int digit ) | ||
748 | { | ||
749 | for( ; digit <= 9 ; ++digit ) | ||
750 | if( !DISALLOWED( idx, digit ) ) | ||
751 | { | ||
752 | board[ idx ] = SET_DIGIT( digit ); | ||
753 | update( idx ); | ||
754 | add_move( idx, digit, CHOICE ); | ||
755 | return digit; | ||
756 | } | ||
757 | |||
758 | return -1; | ||
759 | } | ||
760 | |||
761 | /* Backtrack to a previous choice point, and attempt to reseed | ||
762 | * the search. Return -1 if no further choice possible, or | ||
763 | * the index of the changed square. | ||
764 | * | ||
765 | * Assumes that the move history and board are valid. | ||
766 | */ | ||
767 | static | ||
768 | int | ||
769 | backtrack( void ) | ||
770 | { | ||
771 | int digit, idx; | ||
772 | |||
773 | for( ; 0 <= --idx_history ; ) | ||
774 | if( history[ idx_history ] & CHOICE ) | ||
775 | { | ||
776 | /* Remember the last choice, and advance */ | ||
777 | idx = GET_INDEX( history[ idx_history ] ); | ||
778 | digit = GET_DIGIT( history[ idx_history ] ) + 1; | ||
779 | reapply( ); | ||
780 | if( -1 != choose( idx, digit ) ) | ||
781 | return idx; | ||
782 | } | ||
783 | |||
784 | return -1; | ||
785 | } | ||
786 | |||
787 | /* Attempt to solve 'board'; return 0 on success else -1 on error. | ||
788 | * | ||
789 | * The solution process attempts to fill-in deterministically as | ||
790 | * much of the board as possible. Once that is no longer possible, | ||
791 | * need to choose a square to fill in. | ||
792 | */ | ||
793 | static | ||
794 | int | ||
795 | solve( void ) | ||
796 | { | ||
797 | int idx; | ||
798 | |||
799 | while( 1 ) | ||
800 | { | ||
801 | if( 0 == deterministic( ) ) | ||
802 | { | ||
803 | /* Solved, make a new choice, or rewind a previous choice */ | ||
804 | idx = choice( ); | ||
805 | if( -1 == idx ) | ||
806 | return 0; | ||
807 | else | ||
808 | if( ( idx < 0 || -1 == choose( idx, 1 ) ) && -1 == backtrack( ) ) | ||
809 | return -1; | ||
810 | } | ||
811 | else /* rewind to a previous choice */ | ||
812 | if( -1 == backtrack( ) ) | ||
813 | return -1; | ||
814 | } | ||
815 | return -1; | ||
816 | } | ||
817 | |||
818 | static | ||
819 | int | ||
820 | init_template( int template ) | ||
821 | { | ||
822 | int i, row, col; | ||
823 | int mask; | ||
824 | |||
825 | reset( ); | ||
826 | len_tmplt = 0; | ||
827 | |||
828 | /* Consume grid - allow leading spaces and comments at end */ | ||
829 | for( row = 0 ; row < 9 ; ++row ) | ||
830 | { | ||
831 | mask=0x100; | ||
832 | for( col = 0 ; col < 9 ; ++col ) | ||
833 | { | ||
834 | if (templates[template][row] & mask) | ||
835 | tmplt[ len_tmplt++ ] = INDEX( row, col ); | ||
836 | mask /= 2; | ||
837 | } | ||
838 | } | ||
839 | |||
840 | /* Construct move history for a template */ | ||
841 | idx_history = 0; | ||
842 | for( i = 0 ; i < 81 ; ++i ) | ||
843 | if( 0 != DIGIT( i ) ) | ||
844 | history[ idx_history++ ] = i | (DIGIT( i )<<8); | ||
845 | |||
846 | /* Finally, markup all of these moves as 'fixed' */ | ||
847 | for( i = 0 ; i < idx_history ; ++i ) | ||
848 | history[ i ] |= FIXED; | ||
849 | |||
850 | return 0; | ||
851 | } | ||
852 | |||
853 | /* Classify a SuDoKu, given its solution. | ||
854 | * | ||
855 | * The classification is based on the average number of possible moves | ||
856 | * for each pass of the deterministic solver - it is a rather simplistic | ||
857 | * measure, but gives reasonable results. Note also that the classification | ||
858 | * is based on the first solution found (but does handle the pathological | ||
859 | * case of multiple solutions). Note that the average moves per pass | ||
860 | * depends just on the number of squares initially set... this simplifies | ||
861 | * the statistics collection immensely, requiring just the number of passes | ||
862 | * to be counted. | ||
863 | * | ||
864 | * Return 0 on error, else a string classification. | ||
865 | */ | ||
866 | |||
867 | static | ||
868 | char * | ||
869 | classify( void ) | ||
870 | { | ||
871 | int i, score; | ||
872 | |||
873 | pass = 0; | ||
874 | clear_moves( ); | ||
875 | if( -1 == solve( ) ) | ||
876 | return 0; | ||
877 | |||
878 | score = 81; | ||
879 | for( i = 0 ; i < 81 ; ++i ) | ||
880 | if( IS_FIXED( i ) ) | ||
881 | --score; | ||
882 | |||
883 | assert( 81 == idx_history ); | ||
884 | |||
885 | for( i = 0 ; i < 81 ; ++i ) | ||
886 | if( history[ i ] & CHOICE ) | ||
887 | score -= 5; | ||
888 | |||
889 | if( 15 * pass < score ) | ||
890 | return "very easy"; | ||
891 | else | ||
892 | if( 11 * pass < score ) | ||
893 | return "easy"; | ||
894 | else | ||
895 | if( 7 * pass < score ) | ||
896 | return "medium"; | ||
897 | else | ||
898 | if( 4 * pass < score ) | ||
899 | return "hard"; | ||
900 | else | ||
901 | return "fiendish"; | ||
902 | } | ||
903 | |||
904 | /* exchange disjoint, identical length blocks of data */ | ||
905 | static | ||
906 | void | ||
907 | exchange( int * a, int * b, int len ) | ||
908 | { | ||
909 | int i, tmp; | ||
910 | for( i = 0 ; i < len ; ++i ) | ||
911 | { | ||
912 | tmp = a[ i ]; | ||
913 | a[ i ] = b[ i ]; | ||
914 | b[ i ] = tmp; | ||
915 | } | ||
916 | } | ||
917 | |||
918 | /* rotate left */ | ||
919 | static | ||
920 | void | ||
921 | rotate1_left( int * a, int len ) | ||
922 | { | ||
923 | int i, tmp; | ||
924 | tmp = a[ 0 ]; | ||
925 | for( i = 1 ; i < len ; ++i ) | ||
926 | a[ i - 1 ] = a[ i ]; | ||
927 | a[ len - 1 ] = tmp; | ||
928 | } | ||
929 | |||
930 | /* rotate right */ | ||
931 | static | ||
932 | void | ||
933 | rotate1_right( int * a, int len ) | ||
934 | { | ||
935 | int i, tmp; | ||
936 | tmp = a[ len - 1 ]; | ||
937 | for( i = len - 1 ; 0 < i ; --i ) | ||
938 | a[ i ] = a[ i - 1 ]; | ||
939 | a[ 0 ] = tmp; | ||
940 | } | ||
941 | |||
942 | /* Generalised left rotation - there is a naturally recursive | ||
943 | * solution that is best implementation using iteration. | ||
944 | * Note that it is not necessary to do repeated unit rotations. | ||
945 | * | ||
946 | * This function is analogous to 'cutting' a 'pack of cards'. | ||
947 | * | ||
948 | * On entry: 0 < idx < len | ||
949 | */ | ||
950 | static | ||
951 | void | ||
952 | rotate( int * a, int len, int idx ) | ||
953 | { | ||
954 | int xdi = len - idx; | ||
955 | int delta = idx - xdi; | ||
956 | |||
957 | while( 0 != delta && 0 != idx ) | ||
958 | { | ||
959 | if( delta < 0 ) | ||
960 | { | ||
961 | if( 1 == idx ) | ||
962 | { | ||
963 | rotate1_left( a, len ); | ||
964 | idx = 0; | ||
965 | } | ||
966 | else | ||
967 | { | ||
968 | exchange( a, a + xdi, idx ); | ||
969 | len = xdi; | ||
970 | } | ||
971 | } | ||
972 | else /* 0 < delta */ | ||
973 | { | ||
974 | if( 1 == xdi ) | ||
975 | { | ||
976 | rotate1_right( a, len ); | ||
977 | idx = 0; | ||
978 | } | ||
979 | else | ||
980 | { | ||
981 | exchange( a, a + idx, xdi ); | ||
982 | a += xdi; | ||
983 | len = idx; | ||
984 | idx -= xdi; | ||
985 | } | ||
986 | } | ||
987 | xdi = len - idx; | ||
988 | delta = idx - xdi; | ||
989 | } | ||
990 | if( 0 < idx ) | ||
991 | exchange( a, a + idx, idx ); | ||
992 | } | ||
993 | |||
994 | /* Shuffle an array of integers */ | ||
995 | static | ||
996 | void | ||
997 | shuffle( int * a, int len ) | ||
998 | { | ||
999 | int i, j, tmp; | ||
1000 | |||
1001 | i = len; | ||
1002 | while( 1 <= i ) | ||
1003 | { | ||
1004 | j = rb->rand( ) % i; | ||
1005 | tmp = a[ --i ]; | ||
1006 | a[ i ] = a[ j ]; | ||
1007 | a[ j ] = tmp; | ||
1008 | } | ||
1009 | } | ||
1010 | |||
1011 | /* Generate a SuDoKu puzzle | ||
1012 | * | ||
1013 | * The generation process selects a random template, and then attempts | ||
1014 | * to fill in the exposed squares to generate a board. The order of the | ||
1015 | * digits and of filling in the exposed squares are random. | ||
1016 | */ | ||
1017 | |||
1018 | /* Select random template; sets tmplt, len_tmplt */ | ||
1019 | static | ||
1020 | void | ||
1021 | select_template( void ) | ||
1022 | { | ||
1023 | int i = rb->rand( ) % NUM_TEMPLATES; | ||
1024 | init_template( i ); | ||
1025 | } | ||
1026 | |||
1027 | |||
1028 | static | ||
1029 | void | ||
1030 | generate( void ) | ||
1031 | { | ||
1032 | static int digits[ 9 ]; | ||
1033 | |||
1034 | int i; | ||
1035 | |||
1036 | start: | ||
1037 | for( i = 0 ; i < 9 ; ++i ) | ||
1038 | digits[ i ] = i + 1; | ||
1039 | |||
1040 | rotate( digits, 9, 1 + rb->rand( ) % 8 ); | ||
1041 | shuffle( digits, 9 ); | ||
1042 | select_template( ); | ||
1043 | |||
1044 | rotate( tmplt, len_tmplt, 1 + rb->rand( ) % ( len_tmplt - 1 ) ); | ||
1045 | shuffle( tmplt, len_tmplt ); | ||
1046 | |||
1047 | reset( ); /* construct a new board */ | ||
1048 | |||
1049 | for( i = 0 ; i < len_tmplt ; ++i ) | ||
1050 | fill( tmplt[ i ], digits[ i % 9 ] ); | ||
1051 | |||
1052 | if( 0 != solve( ) || idx_history < 81 ) | ||
1053 | goto start; | ||
1054 | |||
1055 | for( i = 0 ; i < len_tmplt ; ++i ) | ||
1056 | board[ tmplt[ i ] ] |= FIXED; | ||
1057 | |||
1058 | /* Construct fixed squares */ | ||
1059 | for( idx_history = i = 0 ; i < 81 ; ++i ) | ||
1060 | if( IS_FIXED( i ) ) | ||
1061 | history[ idx_history++ ] = SET_INDEX( i ) | ||
1062 | | SET_DIGIT( DIGIT( i ) ) | ||
1063 | | FIXED; | ||
1064 | clear_moves( ); | ||
1065 | |||
1066 | if( 0 != solve( ) || idx_history < 81 ) | ||
1067 | goto start; | ||
1068 | if( -1 != backtrack( ) && 0 == solve( ) ) | ||
1069 | goto start; | ||
1070 | |||
1071 | clear_moves( ); | ||
1072 | } | ||
1073 | |||
1074 | bool sudoku_generate_board(struct sudoku_state_t* state, char** difficulty) | ||
1075 | { | ||
1076 | int r,c,i; | ||
1077 | |||
1078 | rb->srand(*rb->current_tick); | ||
1079 | |||
1080 | generate(); | ||
1081 | |||
1082 | i=0; | ||
1083 | for (r=0;r<9;r++) { | ||
1084 | for (c=0;c<9;c++) { | ||
1085 | if( IS_EMPTY( i ) ) | ||
1086 | state->startboard[r][c]='0'; | ||
1087 | else | ||
1088 | state->startboard[r][c]='0'+GET_DIGIT( board[ i ] ); | ||
1089 | |||
1090 | state->currentboard[r][c]=state->startboard[r][c]; | ||
1091 | i++; | ||
1092 | } | ||
1093 | } | ||
1094 | |||
1095 | *difficulty = classify( ); | ||
1096 | return true; | ||
1097 | } | ||