programming the Sudoku helper - solver

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.
Array 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 GroupSums
These 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:

type
      Tnumber = record
                 nr : byte;
                 org : boolean;
                end;
      TSodoku = array[1..9,1..9] of TNumber;
      
//------comp search data
var board : TSodoku;
    Xboard   : array[1..9,1..9] of word;
    RowSums  : array[1..9] of word;
    ColSums  : array[1..9] of word;
    groupSums: array[1..9] of word;

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
ColumnSums and GroupSums are made in a similar way.
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:

function IJtoGroupNr(i,j : byte) : byte;
//return group Nr of field [i,j]
var x,y : byte;
begin
 x := (i-1) div 3;
 y := (j-1) div 3;
 result := x + 3*y + 1;
end;

procedure MakeHintfields;
//make Xboard array 9*9 of word
//each word has bit set for possible digit
//make Row & column sums
var i,j,group,x,y : byte;
begin
 for j := 1 to 9 do
  for i := 1 to 9 do
   if board[i,j].nr = 0 then Xboard[i,j] := 0  //clear Xboard
   else Xboard[i,j] := 1 shl board[i,j].nr;    //set xboard
//
 for i := 1 to 9 do
  begin
   Rowsums[i] := $3fe;              //init RowSums
   ColSums[i] := $3fe;              //init Columnsums
   GroupSums[i] := $3fe;            //init groupsums
  end;

//make row sums

 for j := 1 to 9 do
  for i := 1 to 9 do RowSums[j] := RowSums[j] xor Xboard[i,j];

//make Column sums

 for i := 1 to 9 do
  for j := 1 to 9 do ColSums[i] := ColSums[i] xor Xboard[i,j];

//make group sums

 for group := 1 to 9 do
  begin
   x := ((group-1) mod 3)*3 + 1;
   y := ((group-1) div 3)*3 + 1; //[x,y] is left top of group
   for j := 0 to 2 do
    for i := 0 to 2 do
     GroupSums[group] := Groupsums[group] xor Xboard[x+i,y+j];
  end;

//combine column-row-group

 for j := 1 to 9 do
  for i := 1 to 9 do
   if board[i,j].nr = 0 then
    Xboard[i,j] := ColSums[i] and Rowsums[j] and GroupSums[IJtoGroupNr(i,j)];
end;


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:

var 
    Pallow : array[1..9] of word;  //for hint reduction
    Psum : array[1..9] of word;
    Xvalue : array[1..9] of word;
    Pmask : array[1..9] of word;


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)
If Pmask[3] = 4 then bit 4 is dropped in Pallow[5].

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
PC(action : byte) is a function that may be called with
    action = 0 : to reset the permutation counter
    action = 1 : to increment the counter
The PC function returns "true" if the operation was succesfull: no overflow and
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:

 
//-------hint reduction by row/column

procedure LoadPfromRow(row : byte);
var i : byte;
begin
 for i := 1 to 9 do
  begin
   xvalue[i] := Xboard[i,row];
   Psum[i] := 0;
  end;
end;

procedure LoadPfromColumn(col : byte);
var j : byte;
begin
 for j := 1 to 9 do
  begin
   xvalue[j] := Xboard[col,j];
   Psum[j] := 0;
  end;
end;

procedure loadPfromGroup(gr : byte);
var i,j,n,x,y : byte;
begin
 x := ((gr-1) mod 3)*3 + 1;  //[x,y] is left top of group
 y := ((gr-1) div 3)*3 + 1;
 for n:= 1 to 9 do
  begin
   i := x+((n-1) mod 3);     //[i,j] is field
   j := y+((n-1) div 3);
   Xvalue[n] := xboard[i,j];
   Psum[n] := 0;
  end;
end;

procedure UpdatePsums;
//or masks into Psum
var n : byte;
begin
 for n := 1 to 9 do PSum[n] := Psum[n] or Pmask[n];
end;

function PC(action : byte) : boolean;
//action-0 : reset, 1: increment
//on exit :
//true: digit 9 incremented properly
//false: digit 1 overflow
var xxx : word;
    digit : byte;      //counter digit
label PCreset,PCincr;
begin
 if action = 0 then digit := 1 else begin
                                     digit := 9; goto PCincr;
                                    end;
 Pallow[1] := $3fe;

PCreset :

 Pmask[digit] := 1;
 if digit > 1 then Pallow[digit] :=
   Pallow[digit-1] and (Pmask[digit-1] xor $3fe);

PCincr :

  xxx := Pallow[digit] and xvalue[digit];
  repeat
   Pmask[digit] := Pmask[digit] shl 1;       //find next mask
  until (Pmask[digit] = $400) or ((Pmask[digit] and xxx) <> 0);
  if Pmask[digit] = $400 then          //not found
   begin
    Pmask[digit] := 0;
    if digit = 1 then
     begin
      result := false; exit;      //exit if digit 1
     end
    else begin
          dec(digit); goto PCIncr;//no mask, digit > 1 = inc previous
         end;
  end //if mask...
  else                            //good mask found
   if digit < 9 then
    begin
     inc(digit); goto PCreset;    //new mask found, reset next
    end
   else result := true;
end;

procedure HintReduction;
//use Xboard values and reduce per row,column
var i,j,n,gf,x,y : byte;
    s : string;
begin
 s := 'please wait';
 msg(msgInfo,s);
 for n := 1 to 9 do           //rows
  begin
   loadPfromRow(n);                   //if reset OK
   if PC(0) then
    begin
     UpdatePsums;
     while PC(1) do UpdatePsums;      //if incr OK
    end;
   for i := 1 to 9 do xboard[i,n] := Psum[i];//store results
  end;//for n
//

 for n := 1 to 9 do           //columns
  begin
   loadPfromcolumn(n);
   if PC(0) then
    begin
     UpdatePsums;
     while PC(1) do UpdatePsums;      //if incr OK
    end;
   for i := 1 to 9 do xboard[n,i] := Psum[i];//store results
  end;//for

 for n := 1 to 9 do           //groups
  begin
   loadPfromgroup(n);
   if PC(0) then                      //if reset OK
    begin
     UpdatePsums;
     while PC(1) do UpdatePsums;      //if incr OK
    end;
   x := ((n-1) mod 3)*3 + 1;
   y := ((n-1) div 3)*3 + 1;  //[I,J] of field
   for gf:= 1 to 9 do
    begin                     //for group fields 1..9
     i := x+((gf-1) mod 3);
     j := y+((gf-1) div 3);
     xboard[i,j] := Psum[gf];
    end; 
  end;//for n
//
  s := '';
  msg(msgInfo,s);
//  
 showHintFields;
 if hintflag then
  begin
   AnalyzeHints;
   ReportHintData;
  end;
end;


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 data type declarations are listed:

type  TentryType = (etOrg,etAuto,etManual);//way number was added
      TNumber3 = record
                  nr : byte;
                  et : TentryType;
                 end;
      Tsudoku3 = array[1..9,1..9] of Tnumber3;//puzzle board
var   board : TSudoku3; 
      triple : array[1..3,1..9] of word;   //for hintreduction2


Below, the associated source code is listed:

 
//------------hint reduction2

procedure loadTriplesHor;
//i:column  j:row  sum: or of 3 cons. fields in row
var i,j,x,n : byte;
    sum : word;
begin
 for j := 1 to 9 do       //all columns
  for i := 1 to 3 do      //all 3 triples
   begin
    x := (i-1)*3 + 1;
    sum := 0;
    for n := 0 to 2 do sum := sum or Xboard[x+n,j];
    triple[i,j] := sum;
   end;
end;

procedure loadtriplesvert;
//reflect row/column to use same chech later
var i,j,y,n : byte;
    sum : word;
begin
 for i := 1 to 9 do
  for j := 1 to 3 do
   begin
    y := (j-1)*3 + 1;
    sum := 0;
    for n := 0 to 2 do sum := sum or Xboard[i,y+n];
    triple[j,i] := sum;
   end;
end;

procedure CheckTriples;
var block, i,j,y,n : byte;
    a,b,c : word;
begin
 for block := 1 to 3 do
  begin
   y := (block-1)*3 + 1;
   for j := 1 to 3 do
    for i := 1 to 3 do
     begin
      a := 0; b := 0;
      for n := 1 to 3 do
       begin
        if n <> i then a := a or triple[n,y+j-1];
        if n <> j then b := b or triple[i,y+n-1];
       end;
      c := a and b;
      for n := 1 to 3 do
       begin
        if n <> i then triple[n,y+j-1] := triple[n,y+j-1] and c;
        if n <> j then triple[i,y+n-1] := triple[i,y+n-1] and c;
       end;
     end;
  end;
end;

procedure reduceRowsbyTriples;
var i,j,x : byte;
begin
 for j := 1 to 9 do
  for i := 1 to 9 do
   begin
    x := (i-1) div 3 + 1;
    Xboard[i,j] := Xboard[i,j] and triple[x,j]
   end;
end;

procedure reduceColumnsbyTriples;
var i,j,x : byte;
begin
 for j := 1 to 9 do
  begin
   x := (j-1) div 3 + 1;
   for i := 1 to 9 do Xboard[i,j] := Xboard[i,j] and triple[x,i];
  end; 
end;

procedure Hintreduction2;
//sum options in triples, hor. vert.
//compare groups vs row, column
//select triple in group:
//options not present in row outside group,
//are cancelled in other triples in group
var s : string;
begin
 loadTriplesHor;
 CheckTriples;
 reduceRowsbyTriples;
 loadtriplesvert;
 CheckTriples;
 reduceColumnsbyTriples;
end;


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.