click here to see complete Delphi source code. (HTML format) New in version 2.1 1. Extension to "options reduction" 2. Differentiation between manually- and automatically filled in numbers Introduction This document describes how my SUDOKU helper-solver works. The data structures and algorithms are discussed in detail and the reader will find pieces of the Delphi source code inserted. I have skipped the housekeeping code (such as event handlers) and also I do not show the code of the paint procedures. A few weeks ago, a friend send me a sudoku puzzle with the suggestion it might be interesting to think about a computer program to solve it. For myself, I do not much like to play puzzles. However, I like to write programs. I started to think about strategies and also I decided not to look at existing software. Right now, I have version 2.0 of my SUDOKU helper/solver on the web. And, I have looked around and found many other helpers and solvers. Some with more, some with less options, but also with many common features. After all, there is not much choice as the rules of the puzzle are simple. (why is it, we want to be unique so badly?) Of course I hope users will appreciate (or better : prefer) my program.I started out writing a solver. But shortly, it turned out to be a helper, by showing options, hints and warnings. When development continued, I realized that in most cases a puzzle was solved after a few mouseclicks. At that moment it became a solver as well. Definitions and Codes The board is a square of 9 * 9 fields.9 horizontal fields make a row.9 vertical fields make a column.Also, the board is organized as 9 groups of 3 * 3 fields each.A field on the board is represented by a record with elements: -
nr : the number 0..9 , 0 represents an empty field.
org : "true" if number is part of the original puzzle. board holds the 81 fields with the numbers.For clearity, original numbers are painted in brown. Numbers that are part of the solution are painted in black. In open fields, future numbers may be displayed as options. An open field with options I call a hintfield.To facilitate boolean operations on hintfields, I have choosen a bitwise coding. Each field has a 16 bit variable (word) associated, which has bit i set if number i is an option for that field. Array Xboard holds these words with options for each field.Writing a binary code as [...........], Xboard[3,8] = [0010001010] means, that the field in column 3, row 8, has the options (1,3,7). (remark: rightmost bit zero has another function, as we will see) Values of Xboard are made from arrays RowSums, ColumnSums and GroupSumsThese arrays (of 16 bit words) are also bitwise coded: RowSums[3] has bit 5 set if the number 5 is not yet present in row 3. GroupSums[2] = [001011100] means, that numbers (2,3,4,6) are not present in group 2. Below, you find the definitions of the data types:
How the Hintfields are made The Rowsums values are made in the following way: -
- preset Rowsum[..] to $3fe = [1111111110]
- toggle bit i if number i is present in that row Each bit represents a digit that is still missing in a column or group. Xboard values are made by anding the RowSums, columnSums and Groupsums values.This is obvious, since a number is an option in a field if it is allowed in it's row, column and group. Below you see the source code:
Display of the options in an empty field allready helps quite a lot when solving Sudoku puzzles. Also, by straightforward counting, warnings in case of fields without any option or rows, columns or groups with missing options can be generated. Attention may also be drawn to fields that have just one option, or to rows, columns or groups where an option number is limited to just one field. The user may select to fill these fields automatically. With this level of assistance, the Sudoku helper takes care of the administration modestly participates in logical operations. Reduction of options When a field contains a number, Xboard will have the corresponding bit set, see above code. If board[4,5].nr = 7, than Xboard[4,5] = [0010000000]. Let us write a hint field with options 1,4,5 as (1,4,5). Let us write a field with a number 3 as [3]. So, a row, column or group may be written as (1,4,5)[8][7](5,6)(1,4,6)(5,6)[2][3][9]. We notice the numbers 8,7,2,3,9 and 4 open fields. Looking at the hint fields (1,4,5) (1,4,6) (5,6) (5,6) the options 1 and 4 are only present in two fields. So, these fields can never contain a number 5 or 6 which means that the hint fields may be reduced to (1,4) (1,4) (5,6) (5,6). Of course, there are many more combinations where options may be reduced. Question is, to find an algorithm to catch them all. The solution is to consider a row, column or group of numbers (and options) as a counter. When all permutations of the numbers 1 to 9 are generated, some will "fit" where others will not. "Fit" means, that each number in the permutation is allowed in the field, or, has it's bit present in Xboard. (the first number in the permutation is for field 1, the second for field 2....) Note: a permutation of elements 1,2,3.. is simply a sequence of 1,2 and 3, where each element is used exactly once. So, elements 1,2,3 have 6 permutations: 123,132,213,231,312,321. Look again at the arbitrary row (1,4,5)[8][7](5,6)(1,4,6)(5,6)[2][3][9] Permutation 1,8,7,5,4,6,2,3,9 will fit. A permutation starting with 5 cannot fit: 5,8,7,6,1, and we are stuck, the choice is between 5 and 6 which are illegal because fields 1 and 4 allready contain numbers 5 and 6. Generating all permutions, we register all options of the permutations that fit. These values are then copied back to array Xboard. For a fast execution of the above process, a special type counter is programmed: the "permutation counter". This counter has 9 stages, as it must accomodate 9 numbers. The main difference with a real counter is, that a higher stage may never repeat a number from a previous stage. In the permutation counter, stage 1 is the leftmost number. The counter overflows when stage 1 overflows. Stage 9 is the rightmost number. The permutation counter is succesfully incremented if stage 9 is succesfully incremented. Each stage of the counter has some variables, which are housed in separate arrays. Below you find the definitions of the data associated with the permutation counter:
Xvalue[1..9] is a straight copy of the Xboard values for the row, column or group being examined.Pmask[1..9] forms the counter. Counting is done by a "sliding" 1, so Pmask counts [0000000001] ...[0000000010]...[0000000100]...for 0,1,2.. Overflow means, that Pmask reached the value $400 = [10000000000]. Reset forces [0000000001] , bit zero set, into a Pmask stage. Pallow values inhibit multiple use of a number.Pallow[1] is always $3fe = [1111111110], allowing all numbers. Pallow[i] is made of Pallow[i-1] and Pmask[i-1]: -
Pallow[i] := Pallow[i-1] and (Pmask[i-1] xor $3fe)
Psum holds the results of the permutation counting.After a permutation that "fits", the Pmask values are ored into Psum.At the end, the Psum values are copied back to Xboard which concludes the reduction processs. In the sourcecode below you may notice the following procedures and function: -
- loadPfromRow : a straight copy from row 1..9 in Xboard[] into the Pcounter Xvalues
- loadPfromColumn : the same for a column - loadpfromGroup : the same for a group - UpdatePsums : or the Pmask data into the Psum array values- PC : this function performs operations within the permutation counter - HintReduction : this procedure calls the above to get the job done -
action = 0 : to reset the permutation counter
action = 1 : to increment the counter the counter contains values that "fit". In other cases, the function returns "false". A reset operation resets stage 1. Pmask[1] is set to [...1], which means the zero value. However, the tric is to always have a reset followed by an increment on the same stage. Incrementing a stage means, that the bit in Pmask is left shifted until a value is reached that "fits". For that, the bit must be present in both Xvalue and Pallow. After a stage changes due to an increment, the next higher stage must be reset and the story repeats. Function PC exits when stage 9 has succesfully been updated or when stage 1 overflows. When a stage other than 1 overflows, an increment is applied to the one lower stage. An example: Let stages 8 and 9 of the permutation counter be 8 and 9. Stage 9 receives an increment and overflows This causes an increment of stage 8, which becomes 9. Now stage 9 is reset to zero and subsequently incremented to 8, the first allowed number. PC exits "true" as stage 9 was succesfully incremented. Notice, that the permutation ....89 was changed into ....98. Here is the source code:
Changes in version 2.1 Version 2.1 has a small addition to hint reduction. Consider the board as horizontal groups of 3 digits, called a triple. Triples 1,2,3 make row 1. Triples 1,4,7 make group 1. When an option (say 8) is not present in triples 4 and 7, this 8 will appear in triple 1 as it must be present once in group 1. Therefore, 8 cannot be an option in triples 2 and 3. Also, options not present in triples 2 and 3, cannot be options in triples 4 and 7. This procedure can be repeated for all other triples. Also, columns can be considered as triples. Another change in version 2.1 is the differentiation between manually and automatically filled-in numbers. The last type are painted in gray. All gray numbers following a black (manually filled in) number are removed at once with a backspace command.Gray numbers cannot be overwritten manually. This saves time when solving very difficult puzzles, requiring backtracking. So, each field now is represented by a record indicating: -
- the digit (nr)
- the type of entry (etOrg,etAuto,etManual)
Below, the associated source code is listed:
Time considerations 9 elements have 9! = 362880 permutations. When the reduce button is clicked on an empty board,this number of permutations have to be generated for each row, column and group. For that reason the program displays "please wait..." as this takes a few seconds while actually nothing is achieved. In a real puzzle, about one-third of the numbers is filled in. This leaves 6! = 720 permutations per row, column and group. Also, the lesser number of options contributes to a higher speed. The "please wait.." display is still there, but will hardly be noticed. Limitations My approach so far solves most SUDOKU puzzles by pressing the reduce button 3 to 8 times.A reduction in a column may cause a further reduction in a row the next time and so on. Rows, columns and groups therefore interact in an indirect way. There is no direct analyses or comparison between them. When no (further) reduction is possible and no field shows up with just one option, the user has no other choice then to guess a number (and remember it) and try the reduce button again.However, sudoku puzzles requiring this approach are rare. Even puzzles in the catagory "evil" have been solved by a few mouseclicks. As always, there is room for improvement. Also, the real sudoku-addict will never touch the reduce button anyhow.Below, I present the only puzzle I found, requiring 2 times a user decision. (select text and copy to clipboard, then paste it into the sudoku board by pressing the clipbrd button while the board is empty)SUDOKU - puzzle [1][8][9] x [7] x [6] x [4] [7][3][2][6] x x [9] x x [5][6][4] x x x [2] x [7] x x x [7] x [5][4][6] x x x [6] x [1] x [7] x x x [7] x [4] x [6][3] x x [6] x x x x x [8][7][3] x x x x x [7][5][2][6] [8] x [7] x [6] x [1][4][9] The puzzle below is from the category "very hard". Using all helper-solver options, it was solved in 30 seconds. SUDOKU - puzzle x [4][3] x [8] x [2][5] x [6] x x x x x x x x x x x x x [1] x [9][4] [9] x x x x [4] x [7] x x x x [6] x [8] x x x x[ 1] x [2] x x x x [3] [8][2] x [5] x x x x x x x x x x x x x [5] x [3][4] x [9] x[ 7][1] x This concludes the description of my sudoku helper/solver program. The information presented may be used freely. A link to www.davdata.nl is appreciated. |
||||||||||||