Transcript Hints for L0 Sudoku

CS 410
Mastery in Programming
Chapter 10
Hints for Simple Sudoku
Herbert G. Mayer, PSU CS
Status 7/29/2013
1
Syllabus
 Requirements
 Level 0
 Level 0 Algorithm
 Data Structure
 Check Row, Columns
 Check Subsquares
 L0 Sudoku
 Sample
 References
2
Requirements
1. The Sudoku game has a starting board Sstart
2. Sstart must be solvable, leading to a fully populated Sudoku
board Send
3. The situation must be uniquely solvable; i.e. Sstart may not be
open-ended so that multiple solutions Send will be possible;
that would be interesting too, but is ambiguous
4. Send must be reachable without backtracking. I.e. it will not be
necessary to discard an intermediate situation Sinter since it
fails to produce a solution, and then to continue where Sinter
has left off; backtracking is an option to pursue, but is not
required for our assumed unique, deterministic situations
5. If a violating Sstart is encountered, the game cannot be solved
with the programs proposed here; program aborts
3
Level 0
Implement a simple Sudoku solution that uses solely
the requirements for all rows, all columns, and all
subsquares.
Sometimes this leads to a solution, which we name
level0 Sudoku
Other solvable situation are of higher level
Initially we solely focus on level0 start situations Sstart
4
Level 0 Algorithm
Precondition:

Have an initial Sudoku board that is:
 Incomplete, i.e. not all fields are populated
 But has some fields filled in, but in a way to let the game be




uniquely and deterministically solvable
Without contradictions, i.e.:
No row holds the same number more than once
No column holds the same number more than once
No sub-square holds the same number more than once
Initial Steps:

For each empty field, i.e. that has no defined number:
 Set all possible candidate numbers in some data structure
 The list of all candidate numbers for a 3*3 by 3*3 Sudoku is:
1, 2, 3, 4, 5, 6, 7, 8, 9
5
Level 0 Algorithm
Step1: Set “changes” to 0
Step2: For every undefined sudoku[row][col] field, i.e. that has candidates in
subset of { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

For any number n found on same “row”, remove n from the candidate list

This is reminiscent of “Sieve if Eratosthenes”

For any number n found on same “column”, remove n from the candidate list, if not
already gone

For any number n found in the same “sub-square”, remove n from the candidate list,
if not already gone

if the candidate list of sudoku[row][col] is down to 1, then


changes++
Set the field sudoku[row][col] to the sole remaining number that is left
Step 3: go to step 1 until “changes” is 0
i.e. we go though all fields sudoku[row][col] repeatedly, as long as we see
changes
Step 4: If all 3*3 by 3*3 fields are set: print success and output the whole board;
else the initial field is not a level 0 solvable situation
6
Data Structure 1
#define
#define
#define
#define
#define
#define
BIG_N ( SMALL_N * SMALL_N )
EOL '\n'
EMPTY 0
NO_CHAR ' '
FALSE 0
TRUE 1
#define
#define
#define
#define
#define
#define
P_BAR
P_LINE
P_PLUS
P_EOL
P_TAB
P_BLANK
printf(
printf(
printf(
printf(
printf(
printf(
"|" )
"-" )
"+" )
"\n" )
"\t" )
" " )
7
Data Structure 2
//
//
//
//
//
//
//
//
//
//
//
//
//
each element of an n*n X n*n sudoku board has the following structure:
"field" has any of the values 0..n*n, with 0 meaning that it is empty.
"option_count" states: how many of n*n numbers could be options.
"can_be[]" is array of n*n+1 bools. Says whether element "i" is option
if can_be[i] is false, number "i" cannot be option any longer.
if option_count ever reaches 1, then we "know" the field value
General data structure layout
0
1
2
3
8
9
+-----+
+-----+
+-----+-----+-----+-----+- ... -+-----+-----+
| NAT |
| NAT |
| DC |
|
|
| ... |
|
|
+-----+
+-----+
+-----+-----+-----+-----+- ... -+-----+-----+
field
option_count can_be[ BIG_N + 1 ]
int
int
bool
8
Data Structure 3
// specific layout for empty field
//
0
1
2
3
8
9
// +-----+
+-----+
+-----+-----+-----+-----+- ... -+-----+-----+
// | 0 |
| 9 |
| DC | T | T | T | ... | T | T |
// +-----+
+-----+
+-----+-----+-----+-----+- ... -+-----+-----+
//
field
option_count can_be[ BIG_N + 1 ]
//
// Specific layout for occupied field 3
//
0
1
2
3
8
9
// +-----+
+-----+
+-----+-----+-----+-----+- ... -+-----+-----+
// | 3 |
| 0 |
| DC | F | F | T | ... | F | F |
// +-----+
+-----+
+-----+-----+-----+-----+- ... -+-----+-----+
//
field
option_count can_be[ BIG_N + 1 ]
//
typedef struct board_tp
{
unsigned field;
// 0 if empty, else one of 1..n*n
unsigned option_count;
// initially, all n*n are options
unsigned can_be[ BIG_N + 1 ]; // if false, number "i" impossible
} struct_board_tp;
9
Data Structure 4
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
////////////
////////////
////////////
G l o b a l
O j e c t s
////////////
////////////
////////////
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
// this is the complete sudoku board, n*n by n*n = BIG_N * BIG_N fields
struct_board_tp sudoku[ BIG_N ][ BIG_N ];
10
Check Rows, Columns
// check all horizontal and vertical lines for empty spaces.
// each empty space initially has BIG_N options
// but for each existing value in that row or col, decrease the option.
// if per chance the options end up just 1, then we can plug in a number.
// return the number of fields changed from empty to a new value
unsigned horiz_vert( row_col_anal_tp row_or_col )
{ // horiz_vert
unsigned changes = 0;
unsigned options = 0;
unsigned field
= 0; // remember the next number to be excluded
for ( int row = 0; row < BIG_N; row++ ) {
for ( int col = 0; col < BIG_N; col++ ) {
if ( SRC.field ) {
// there is a number
ASSERT( ( SRC.option_count == 0 ), "has # + option?" );
}else{
// field is EMPTY. Goal to count down options to 1
ASSERT( ( SRC.option_count ), "0 field must have opt" );
// go thru each field. For # found, exclude # from can_be[]
for ( int i = 0; i < BIG_N; i++ ) {
// continued on next page . . .
11
Check Rows, Columns
// . . . continued from previous page
// go thru each field. For # found, exclude # from can_be[]
for ( int i = 0; i < BIG_N; i++ ) {
if ( row_or_col == row_analysis ) {
field = sudoku[ row ][ i ].field;
}else{
// column analysis
field = sudoku[ i ][ col ].field;
} //end if
if ( field ) {
// we found a field
SRC.can_be[ field ] = FALSE;
} //end if
SRC.option_count = options = count_fields( row, col );
if ( options == 1 ) {
// plug in only 1 of BIG_N numbers
// and set option_count to 0
field = find_1_field( row, col );
FILL();
} //end if
} //end for i
} //end if
} //end for col
} //end for row
return changes;
} //end horiz_vert
12
Check Subsquare
// check all horizontal and vertical lines for empty spaces.
// each empty space initially has BIG_N options
// But for each field value in subsquare, decrease options.
// if per chance the options end up just 1, then we can plug in a number.
// return the number of fields changed from empty to a new value
unsigned subsquare( )
{ // subsquare
unsigned changes = 0;
unsigned options = 0;
unsigned field
= 0;
// remember the next number to be excluded
for ( int row = 0; row < BIG_N; row++ ) {
for ( int col = 0; col < BIG_N; col++ ) {
if ( SRC.field ) { // there is a number
ASSERT( ( SRC.option_count == 0 ), "has # + option?" );
}else{
// field is EMPTY. Goal to count down options to 1
ASSERT( ( SRC.option_count ), "subsquare must have opt" );
// analyze all fields in subsquare, exclude from can_be[]
for ( int i = f( row ); i < ( f( row ) + SMALL_N ); i++ ) {
ASSERT( ( i <= row+SMALL_N ), "wrong i_row in [][]" );
// continue on next page
13
Check Subsquare
// continued from previous page . . .
for ( int i = f( row ); i < ( f( row ) + SMALL_N ); i++ ) {
ASSERT( ( i <= row+SMALL_N ), "wrong i_row in [][]" );
for ( int j = f( col ); j < ( f( col ) + SMALL_N ); j++ ) {
ASSERT( j <= col+SMALL_N, "wrong j_col in [][]" );
field = sudoku[ i ][ j ].field;
if ( field ) {
// we found a non-zero field
SRC.can_be[ field ] = FALSE;
} //end if
SRC.option_count = options = count_fields( row, col );
if ( options == 1 ) {
// plug in only 1 of BIG_N numbers
// and set option_count to 0
field = find_1_field( row, col );
FILL();
} //end if
} //end for j
} //end for i
} //end if
} //end for col
} //end for row
return changes;
} //end subsquare
14
L0 Sudoku
// simplest sudoku strategy by eliminating options for a field
// that would conflict with existing numbers in row, column,
subsquare
unsigned sudoku_level0()
{ //sudoku_level0
unsigned changes;
// count fields filled in
unsigned iterations = 0;
// count times we go around
unsigned errors = 0;
// do final sanity check
do {
changes = 0;
changes = horiz_vert( row_analysis );
changes += horiz_vert( col_analysis );
changes += subsquare();
++iterations;
} while ( changes );
try_single_option();
# ifdef DEBUG
printf( "Iterated level0 %d times.\n", iterations );
errors = sanity_check();
# endif // DEBUG
return changes;
} //end sudoku_level0
15
Sample Input
After setting initial fields sudoku board.
0 1 2 3 4 5 6 7 8
+------+------+------+
| 4
1|
5| 2
| 0
| 6
7| 3
| 8 5 | 1
|
5 3|
7 |
1 | 2
+------+------+------+
|
8 | 2 4 3|
| 3
|
|
9|
1| 4
|
4| 8
|
2| 5
+------+------+------+
| 3
|
6| 9
| 6
|
|
2 | 5
8| 7
|
7 | 9
|
6| 8
+------+------+------+
Statistics initially:
Total # of fields: 81
Fields filled:
31
empty fields:
50
16
Sample Output
Sudoku level 0 sudoku board.
0 1 2 3 4 5 6 7 8
+------+------+------+
| 4 9 1| 6 8 5| 2 7 3| 0
| 6 2 7| 3 9 1| 8 5 4| 1
| 8 5 3| 4 7 2| 6 1 9| 2
+------+------+------+
| 1 8 9| 2 4 3| 7 6 5| 3
| 7 3 2| 5 6 9| 4 8 1| 4
| 5 6 4| 8 1 7| 3 9 2| 5
+------+------+------+
| 3 4 8| 1 5 6| 9 2 7| 6
| 9 1 6| 7 2 4| 5 3 8| 7
| 2 7 5| 9 3 8| 1 4 6| 8
+------+------+------+
Statistics Sudoku level 0
Total # of fields: 81
Fields filled:
81
empty fields:
0
Field was solvable with level 0
17
References
1. Here you may play: http://www.websudoku.com/
2. The rules: http://en.wikipedia.org/wiki/Sudoku
3. History: http://www.sudokucentral.com/what-issudoku
4. C Solution: http://www.daniweb.com/softwaredevelopment/cpp/threads/48788
18