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