1 /* sudoku.c - sudoku game
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).
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.
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.
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.
36 #include "templates.h"
37 #include "generator.h"
41 /* Common state encoding in a 32-bit integer:
43 * 7-15 state [bit high signals digits not possible]
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()]
52 #define INDEX_MASK 0x0000007f
53 #define GET_INDEX(val) (INDEX_MASK&(val))
54 #define SET_INDEX(val) (val)
56 #define STATE_MASK 0x0000ff80
57 #define STATE_SHIFT (7-1) /* digits 1..9 */
58 #define DIGIT_STATE(digit) BIT_N(STATE_SHIFT+(digit))
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))
65 #define FIXED 0x00100000
66 #define CHOICE 0x00200000
67 #define IGNORED 0x00400000
69 /* Hint codes (c.f. singles(), pairs(), findmoves()) */
70 #define HINT_ROW 0x01000000
71 #define HINT_COLUMN 0x02000000
72 #define HINT_BLOCK 0x04000000
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.
79 static int board
[ 81 ];
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))
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))
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)
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
108 static int idx_history
;
109 static int history
[ 3 * 81 ];
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.
120 static int idx_possible
;
121 static int possible
[ 81 ];
123 static int pass
; /* count # passes of deterministic solver */
125 /* Support for template file */
126 static int tmplt
[ 81 ]; /* Template indices */
127 static int len_tmplt
; /* Number of template indices */
129 /* Reset global state */
134 rb
->memset( board
, 0x00, sizeof( board
) );
135 rb
->memset( history
, 0x00, sizeof( history
) );
140 /* Management of the move history - compression */
143 compress( int limit
)
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
];
154 /* Management of the move history - adding a move */
157 add_move( int idx
, int digit
, int choice
)
161 if( sizeof( history
) / sizeof( int ) == idx_history
)
164 /* Never ignore the last move */
165 history
[ idx_history
++ ] = SET_INDEX( idx
) | SET_DIGIT( digit
) | choice
;
167 /* Ignore all previous references to idx */
168 for( i
= idx_history
- 2 ; 0 <= i
; --i
)
169 if( GET_INDEX( history
[ i
] ) == idx
)
171 history
[ i
] |= IGNORED
;
176 /* Iteration over rows/columns/blocks handled by specialised code.
177 * Each function returns a block index - call must manage element/idx.
181 idx_row( int el
, int idx
) /* Index within a row */
183 return INDEX( el
, idx
);
188 idx_column( int el
, int idx
) /* Index within a column */
190 return INDEX( idx
, el
);
195 idx_block( int el
, int idx
) /* Index within a block */
197 return INDEX( 3 * ( el
/ 3 ) + idx
/ 3, 3 * ( el
% 3 ) + idx
% 3 );
200 /* Update board state after setting a digit (clearing not handled)
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
) );
212 board
[ idx
] |= STATE_MASK
; /* filled - no choice possible */
214 /* Digit cannot appear in row, column or block */
215 for( i
= 0 ; i
< 9 ; ++i
)
217 board
[ idx_row( row
, i
) ] |= mask
;
218 board
[ idx_column( col
, i
) ] |= mask
;
219 board
[ idx_block( block
, i
) ] |= mask
;
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.
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
] ) )
237 idx
= GET_INDEX( history
[ j
] );
238 digit
= GET_DIGIT( history
[ j
] );
239 if( !IS_EMPTY( idx
) || DISALLOWED( idx
, digit
) )
241 board
[ idx
] = SET_DIGIT( digit
);
242 if( history
[ j
] & FIXED
)
243 board
[ idx
] |= FIXED
;
249 /* Clear moves, leaving fixed squares
255 for( idx_history
= 0 ; history
[ idx_history
] & FIXED
; ++idx_history
)
260 static int digits
[ 9 ]; /* # digits expressed in element square */
261 static int counts
[ 9 ]; /* Count of digits (c.f. count_set_digits()) */
263 /* Count # set bits (within STATE_MASK) */
269 for( i
= STATE_SHIFT
+ 1 ; i
<= STATE_SHIFT
+ 9 ; ++i
)
270 if( mask
& BIT_N(i
) )
273 ++counts
[ i
- STATE_SHIFT
- 1 ];
279 count_set_digits( int el
, int (*idx_fn
)( int, int ) )
282 rb
->memset( counts
, 0x00, sizeof( counts
) );
283 for( i
= 0 ; i
< 9 ; ++i
)
284 digits
[ i
] = numset( board
[ (*idx_fn
)( el
, i
) ] );
287 /* Fill square with given digit, and update state.
288 * Returns 0 on success, else -1 on error (i.e. invalid fill)
292 fill( int idx
, int digit
)
294 assert( 0 != digit
);
296 if( !IS_EMPTY( idx
) )
297 return ( DIGIT( idx
) == digit
) ? 0 : -1;
299 if( DISALLOWED( idx
, digit
) )
302 board
[ idx
] = SET_DIGIT( digit
);
304 add_move( idx
, digit
, 0 );
309 /* Find all squares with a single digit allowed -- do not mutate board */
312 singles( int el
, int (*idx_fn
)( int, int ), int hintcode
)
316 count_set_digits( el
, idx_fn
);
318 for( i
= 0 ; i
< 9 ; ++i
)
320 if( 1 == counts
[ i
] )
322 /* Digit 'i+1' appears just once in the element */
323 for( j
= 0 ; j
< 9 ; ++j
)
325 idx
= (*idx_fn
)( el
, j
);
326 if( !DISALLOWED( idx
, i
+ 1 ) && idx_possible
< 81 )
327 possible
[ idx_possible
++ ] = SET_INDEX( idx
)
332 if( 8 == digits
[ i
] )
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
)
345 /* Given the board state, find all possible 'moves' (i.e. squares with just
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
362 for( i
= 0 ; i
< 9 ; ++i
)
364 singles( i
, idx_row
, HINT_ROW
);
365 singles( i
, idx_column
, HINT_COLUMN
);
366 singles( i
, idx_block
, HINT_BLOCK
);
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.
387 * Recall that each state bit uses a 1 to prevent a digit from
388 * filling that square.
393 pairs( int el
, int (*idx_fn
)( int, int ) )
395 int i
, j
, k
, mask
, idx
;
399 for( i
= 0 ; i
< 8 ; ++i
)
400 if( 7 == digits
[ i
] ) /* 2 digits unknown */
401 for( j
= i
+ 1 ; j
< 9 ; ++j
)
403 idx
= (*idx_fn
)( el
, i
);
404 if( STATE( idx
) == STATE( (*idx_fn
)( el
, j
) ) )
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 */
419 /* Worker: mask elements outside block */
422 exmask( int mask
, int block
, int el
, int (*idx_fn
)( int, int ) )
428 for( i
= 0 ; i
< 9 ; ++i
)
430 idx
= (*idx_fn
)( el
, i
);
431 if( block
!= BLOCK( idx
) && IS_EMPTY( idx
) )
432 board
[ idx
] |= mask
;
436 /* Worker for block() */
439 exblock( int block
, int el
, int (*idx_fn
)( int, int ) )
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
451 for( i
= 0 ; i
< 9 ; ++i
)
453 idx
= idx_block( block
, i
);
454 if( !IS_EMPTY( idx
) )
455 mask
|= DIGIT_STATE( DIGIT( idx
) );
457 exmask( mask
^ STATE_MASK
, block
, el
, idx_fn
);
464 int i
, idx
= 0, row
, col
;
468 /* Find first unknown square */
469 for( i
= 0 ; i
< 9 && !IS_EMPTY( idx
= idx_block( el
, i
) ) ; ++i
)
473 assert( IS_EMPTY( idx
) );
476 for( ++i
; i
< 9 ; ++i
)
478 idx
= idx_block( el
, i
);
479 if( IS_EMPTY( idx
) )
481 if( ROW( idx
) != row
)
483 if( COLUMN( idx
) != col
)
488 exblock( el
, row
, idx_row
);
490 exblock( el
, col
, idx_column
);
498 int i
, idx
, row
, col
, digit
, mask
;
502 for( digit
= 1 ; digit
<= 9 ; ++digit
)
504 mask
= DIGIT_STATE( digit
);
505 row
= col
= -1; /* Value '9' indicates invalid */
506 for( i
= 0 ; i
< 9 ; ++i
)
508 /* Digit possible? */
509 idx
= idx_block( el
, i
);
510 if( IS_EMPTY( idx
) && 0 == ( board
[ idx
] & mask
) )
515 if( row
!= ROW( idx
) )
516 row
= 9; /* Digit appears in multiple rows */
520 if( col
!= COLUMN( idx
) )
521 col
= 9; /* Digit appears in multiple columns */
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
);
531 /* Encoding of positions of a digit (c.f. position2()) - abuse DIGIT_STATE */
532 static int posn_digit
[ 10 ];
538 int digit
, digit2
, i
, mask
, mask2
, posn
, count
, idx
;
542 /* Calculate positions of each digit within block */
543 for( digit
= 1 ; digit
<= 9 ; ++digit
)
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
) ] ) )
551 posn
|= DIGIT_STATE( i
);
554 posn_digit
[ digit
] = posn
;
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
] )
563 ^ ( DIGIT_STATE( digit
) | DIGIT_STATE( digit2
) );
564 mask2
= DIGIT_STATE( digit
);
565 for( i
= 0 ; i
< 9 ; ++i
)
567 idx
= idx_block( el
, i
);
568 if( 0 == ( mask2
& board
[ idx
] ) )
570 assert( 0 == (DIGIT_STATE(digit2
) & board
[idx
]) );
571 board
[ idx
] |= mask
;
574 posn_digit
[ digit
] = posn_digit
[ digit2
] = 0;
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.
597 for( i
= 0 ; i
< 9 ; ++i
)
599 count_set_digits( i
, idx_row
);
602 count_set_digits( i
, idx_column
);
603 pairs( i
, idx_column
);
605 count_set_digits( i
, idx_block
);
606 pairs( i
, idx_block
);
612 for( i
= 0 ; i
< 9 ; ++i
)
621 /* Helper: sort based on index */
622 #if 0 /* unused function */
625 cmpindex( const void * a
, const void * b
)
627 return GET_INDEX( *((const int *)b
) ) - GET_INDEX( *((const int *)a
) );
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
637 int i
, n
, mutated
= 0;
644 /* Each call to pairs() can mutate the board state, making the
645 * hints very, very cryptic... so later undo the mutations.
647 for( i
= 0 ; i
< 9 ; ++i
)
649 count_set_digits( i
, idx_row
);
652 count_set_digits( i
, idx_column
);
653 pairs( i
, idx_column
);
655 count_set_digits( i
, idx_block
);
656 pairs( i
, idx_block
);
663 for( i
= 0 ; i
< 9 ; ++i
)
672 /* Sort the possible moves, and allow just one hint per square */
677 rb
->qsort( possible
, n
, sizeof( int ), cmpindex
);
678 for( i
= 0, j
= 1 ; j
< n
; ++j
)
680 if( GET_INDEX( possible
[ i
] ) == GET_INDEX( possible
[ j
] ) )
682 /* Let the user make mistakes - do not assume the
683 * board is in a consistent state.
685 if( GET_DIGIT( possible
[i
] ) == GET_DIGIT( possible
[j
] ) )
686 possible
[ i
] |= possible
[ j
];
694 /* Undo any mutations of the board state */
700 #endif /* unused function */
702 /* Deterministic solver; return 0 on success, else -1 on error.
706 deterministic( void )
716 for( i
= 0 ; i
< n
; ++i
)
717 if( -1 == fill( GET_INDEX( possible
[ i
] ),
718 GET_DIGIT( possible
[ i
] ) ) )
725 /* Return index of square for choice.
727 * If no choice is possible (i.e. board solved or inconsistent),
730 * The current implementation finds a square with the minimum
731 * number of unknown digits (i.e. maximum # masked digits).
735 cmp( const void * e1
, const void * e2
)
737 return GET_DIGIT( *(const int *)e2
) - GET_DIGIT( *(const int *)e1
);
748 for( n
= i
= 0 ; i
< 81 ; ++i
)
751 possible
[ n
] = SET_INDEX( i
) | SET_DIGIT( numset( board
[ i
] ) );
753 /* Inconsistency if square unknown, but nothing possible */
754 if( 9 == GET_DIGIT( possible
[ n
] ) )
760 return -1; /* All squares known */
762 rb
->qsort( possible
, n
, sizeof( possible
[ 0 ] ), cmp
);
763 return GET_INDEX( possible
[ 0 ] );
766 /* Choose a digit for the given square.
767 * The starting digit is passed as a parameter.
768 * Returns -1 if no choice possible.
772 choose( int idx
, int digit
)
776 for( ; digit
<= 9 ; ++digit
)
777 if( !DISALLOWED( idx
, digit
) )
779 board
[ idx
] = SET_DIGIT( digit
);
781 add_move( idx
, digit
, CHOICE
);
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.
792 * Assumes that the move history and board are valid.
802 for( ; 0 <= --idx_history
; )
803 if( history
[ idx_history
] & CHOICE
)
805 /* Remember the last choice, and advance */
806 idx
= GET_INDEX( history
[ idx_history
] );
807 digit
= GET_DIGIT( history
[ idx_history
] ) + 1;
809 if( -1 != choose( idx
, digit
) )
816 /* Attempt to solve 'board'; return 0 on success else -1 on error.
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.
832 if( 0 == deterministic( ) )
834 /* Solved, make a new choice, or rewind a previous choice */
839 if( ( idx
< 0 || -1 == choose( idx
, 1 ) ) && -1 == backtrack( ) )
842 else /* rewind to a previous choice */
843 if( -1 == backtrack( ) )
851 init_template( int template )
859 /* Consume grid - allow leading spaces and comments at end */
860 for( row
= 0 ; row
< 9 ; ++row
)
863 for( col
= 0 ; col
< 9 ; ++col
)
865 if (templates
[template][row
] & mask
)
866 tmplt
[ len_tmplt
++ ] = INDEX( row
, col
);
871 /* Construct move history for a template */
873 for( i
= 0 ; i
< 81 ; ++i
)
874 if( 0 != DIGIT( i
) )
875 history
[ idx_history
++ ] = i
| (DIGIT( i
)<<8);
877 /* Finally, markup all of these moves as 'fixed' */
878 for( i
= 0 ; i
< idx_history
; ++i
)
879 history
[ i
] |= FIXED
;
884 /* Classify a SuDoKu, given its solution.
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
895 * Return 0 on error, else a string classification.
912 for( i
= 0 ; i
< 81 ; ++i
)
916 assert( 81 == idx_history
);
918 for( i
= 0 ; i
< 81 ; ++i
)
919 if( history
[ i
] & CHOICE
)
922 if( 15 * pass
< score
)
925 if( 11 * pass
< score
)
928 if( 7 * pass
< score
)
931 if( 4 * pass
< score
)
937 /* exchange disjoint, identical length blocks of data */
940 exchange( int * a
, int * b
, int len
)
943 for( i
= 0 ; i
< len
; ++i
)
954 rotate1_left( int * a
, int len
)
958 for( i
= 1 ; i
< len
; ++i
)
966 rotate1_right( int * a
, int len
)
970 for( i
= len
- 1 ; 0 < i
; --i
)
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.
979 * This function is analogous to 'cutting' a 'pack of cards'.
981 * On entry: 0 < idx < len
985 rotate( int * a
, int len
, int idx
)
988 int delta
= idx
- xdi
;
990 while( 0 != delta
&& 0 != idx
)
996 rotate1_left( a
, len
);
1001 exchange( a
, a
+ xdi
, idx
);
1005 else /* 0 < delta */
1009 rotate1_right( a
, len
);
1014 exchange( a
, a
+ idx
, xdi
);
1024 exchange( a
, a
+ idx
, idx
);
1027 /* Shuffle an array of integers */
1030 shuffle( int * a
, int len
)
1037 j
= rb
->rand( ) % i
;
1044 /* Generate a SuDoKu puzzle
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.
1051 /* Select random template; sets tmplt, len_tmplt */
1054 select_template( void )
1056 int i
= rb
->rand( ) % NUM_TEMPLATES
;
1060 static bool check_buttons(void)
1062 int button
= rb
->button_get(false);
1063 return (button
&& (!(button
& BUTTON_REL
)) && (!(button
& BUTTON_REPEAT
)));
1070 static int digits
[ 9 ];
1075 /* Allow the user to abort generation by pressing any button */
1076 if (check_buttons())
1079 for( i
= 0 ; i
< 9 ; ++i
)
1080 digits
[ i
] = i
+ 1;
1082 rotate( digits
, 9, 1 + rb
->rand( ) % 8 );
1083 shuffle( digits
, 9 );
1086 rotate( tmplt
, len_tmplt
, 1 + rb
->rand( ) % ( len_tmplt
- 1 ) );
1087 shuffle( tmplt
, len_tmplt
);
1089 reset( ); /* construct a new board */
1091 for( i
= 0 ; i
< len_tmplt
; ++i
)
1092 fill( tmplt
[ i
], digits
[ i
% 9 ] );
1094 /* Allow the user to abort generation by pressing any button */
1095 if (check_buttons())
1100 if( 0 != solve( ) || idx_history
< 81 )
1103 /* Allow the user to abort generation by pressing any button */
1104 if (check_buttons())
1109 for( i
= 0 ; i
< len_tmplt
; ++i
)
1110 board
[ tmplt
[ i
] ] |= FIXED
;
1112 /* Construct fixed squares */
1113 for( idx_history
= i
= 0 ; i
< 81 ; ++i
)
1115 history
[ idx_history
++ ] = SET_INDEX( i
)
1116 | SET_DIGIT( DIGIT( i
) )
1120 if( 0 != solve( ) || idx_history
< 81 )
1122 if( -1 != backtrack( ) && 0 == solve( ) )
1130 bool sudoku_generate_board(struct sudoku_state_t
* state
, char** difficulty
)
1134 rb
->srand(*rb
->current_tick
);
1136 rb
->button_clear_queue();
1139 /* User has aborted with a button press */
1147 state
->startboard
[r
][c
]='0';
1149 state
->startboard
[r
][c
]='0'+GET_DIGIT( board
[ i
] );
1151 state
->currentboard
[r
][c
]=state
->startboard
[r
][c
];
1156 *difficulty
= classify( );
1160 bool sudoku_solve_board(struct sudoku_state_t
* state
)
1169 if( state
->startboard
[r
][c
]!='0' )
1171 fill( i
, state
->startboard
[r
][c
] - '0' );
1177 ret
= ( 0 == solve( ) && 81 == idx_history
);
1183 state
->currentboard
[r
][c
]='0'+GET_DIGIT( board
[ i
] );