Technological Thoughts by Jerome Kehrli

I have written a little Sudoku program for which I provide here the source code and Windows pre-built executables. Current version is Sudoku 0.2-beta.

It supports the following features:

• A GUI to display and manipulate a Sudoku board
• A Sudoku generator
• A Sudoku solver
• A Sudoku solving tutorial (quite limited at the moment)

At the moment there are two resolution methods supported, one using human-like resolution techniques and a second using backtracking. The resolution of a solvable Sudoku board takes a few milliseconds only.
A solvable Sudoku board is a Sudoku board than has one and only one solution.

The Sudoku board generator generates solvable Sudoku boards. It usually generates boards between 18 and 22 pre-filled cells. (which is quite better than most generators I could find online).
Currently it generates the best (i.e. most difficult) board it possibly can provided the random initial situation (with all cells filled) of the board.
The problem I'm facing in this current version is that it can take from a few seconds only up to several minutes to generate the board (this is discussed in the algorithms section below).
In addition, the difficulty of the resulting board is not tweakable at the moment. In some cases it generates an extremely difficult board (only solvable with nishio) in a few seconds while some other times it needs two minutes to generate an easy board.

The software is written in C++ on Linux with the help of the wxWidgets GUI library.
It is cross-platform to the extent of the wxWidgets library, i.e. it can be compiled on Windows, OS X, BSD, etc.

A makefile is provided to build it, no configure scripts, i.e. you need to adapt the makefile to your own Linux distribution (or on Windows Mingw, TDM, etc.).
Happily only few adaptations should be required.

I provide pre-built Windows binaries here Sudoku_0.4_Windows_binary.zip.

For all other platforms, the source code is available here sudoku-src-v0.4.tar.gz.

1. User Manual

The software presents a sudoku grid centered in its window.
The buttons on the bottom of the GUI have the following functions:

• Generate : generate a new random Sudoku board.
• Launch ... : launch the Sudoku solving tutorial.
• Solve : solve the Sudoku board using human-like heuristics.
• Solve BT : solve the Sudoku board using backtracking.
• Load Grid : load a previously saved grid.
• Save Grid : save the current grid.
• Reset : reset grid as initially created / generated.
• Clean : clean the grid completely (empty grid).

The user can click on a cell to give its value or set the possibilities for the cell:

• A number given alone will set the value for the cell.
• Several numbers separated by a space will set the possibilities for the cell.

When launching the Sudoku solving tutorial, the Sudoku is solved cell after cell following the human-like solving algorithm presented below.
The values in the cell are displayed in different colors depending on the way the value has been computed:

• Dark blue : the value was the single possibility for the cell.
• Cyan : the value needed to be guessed (Nishio approach) during the resolution process.
• Green : the value of the cell was obtained with advanced possibilities reduction approaches.
• Red : the value needed to be guessed by trying one of the possibilities and solving the board further.
  This happens solely when the board is not solvable as it has been given and several solutions exist for it.
  The color of a guessed cell is initially red and it turns cyan once the solution is confirmed.

2. Building the software from sources

2.1 On Linux

First install wxWidgets 3.0.x and wxWidgets 3.0.x development files using your system package manager

Then you need to adapt the Sudoku makefile system to your setup.

• Adapt file sudoku/[Debug/Release]/objects.mk : give correct libraries names matching your wxWidgets build
• Adapt file sudoku/[Debug/Release]/makefile : give correct path of your wxWidgets libraries
• Adapt file sudoku/[Debug/Release]/subdir.mk : give correct path of your wxWidgets headers

(Note : [Debug/Release] means either "Release" or "Debug")

You can then make the software using

$ cd sudoku/[Debug/Release]
$ make clean && make

2.1 On Windows

Building on windows is slightly more complicated since one needs both mingw and wxWidgets.

A dedicated how-to is available in file sudoku/Win32/HOWTO.txt

3. Algorithms

Sudoku solving and generation form an interesting set of problems in the field of algorithmic. I am presenting here the big picture of the algorithms as they are implemented in my Sudoku program as pseudo-code.

3 different algorithms are implemented for now :

• 3.1 Human-like methods solver : more a tutorial that attempts to mimic the human approach when solving a sudoku
• 3.3 Backtracking solver : a purely algorithmical approach using simple backtracking (nothing smart here)
• 3.3 Board generator : the algorithm used to generate a feasible board,

The board generation algorithm is where I have most issues for now. I am able to generate hard to very hard boards ... but it takes SOOOOO much time (up to several minutes for hardest grids).
My algorithm is pretty naive for now and I assume there are some more robust approaches to generate Sudoku grids ... Any suggestion would be welcome :-)

3.1 Human-like methods solver

The Human-like methods solver implements a subset of the usual Sudoku solving techniques that are usable by a human being.

The pseudo-code is as follows:

procedure solveSinglePossibilities
    for each cell of the board do
        if cell has no value set then
            for each possible value (1..9) do
                if value is single possibility according to row, column or square then
                    set value on cell
                end if
                check whether any other value is possible 
                        by checking each with row, column and square
                if no other value is possible then
                    set value on cell
                end if
            end for
        end if
    end for
end procedure  

procedure solvePossiblities
    for each row, column and square of the board do
        for each cell of the row, column or square do
            if there are n other cells that have the same n possibilities (or fewer) then
                discard these possibilities from all other cells
            end if
        end for
    end for
end procedure  

procedure solveSquarePossiblities
    for each row, column and square of the board do
        for each cell of the row, column or square do
            if there are n other cells that have the same n possibilities (or fewer) then
                for each number of these possibilities do
                    if all cells containing number are in same square
                        discard number from all other cells of square 
                    end if
                end for    
            end if
        end for
    end for
end procedure 

procedure solvePossibleCells
    for each cell of the board do
        reset all possibilities
    end for
    
    while changes are made on cells by the calls below do
    
        -- this sets the cells for which a single value
        -- is the only possibility
        call solveSinglePossibilities                
                                                     
        -- Compute cell possibilities 
        for each cell of the board do
            for each possible value (1..9) do
                if value is possible according to row, column or square then
                    add value to cell possibilities
                end if
            end for    
        end for           
        
        while changes are made on cell possibilities by the calls below do            
        
            -- in each element (row, column, square) identify group   
            -- of possibilities and discard them from the other cells
            call solvePossiblities                   
            
            -- if all possibilities of a value in a row or in a column   
            -- are in same square, value can be discarded from other
            -- cells in square.
            call solveSquarePossiblities
        end while
        
        for each cell of the board do
            if cell has only one possibility left then
                set value as that single possibility
            end if
        end for           
        
    end while    
end procedure  

procedure solveUsingGuess  
    set = any one of the remaining cells with fewest possibilities
    while such a cell is found do
    
        -- Make a guess for this cell   
        set cell value = any one if its possibilities       
        
        -- Try to solve using that guess 
        call solvePossibleCells                        

        -- If the call above made sure the board cannot be           
        -- solved using that guess   
        if board is unsolvable then                    
            reset cell value                        
        else if board is solved then 
            -- Fix guess   
            fix cell value -- set cell value definitely
        else
            call solveUsingGuess recursively
        end if
    end while
end procedure  

procedure solve
    -- solve using human-like techniques
    call solvePossibleCells   
    -- if grid is not completed, make guesses (nishio)
    call solveUsingGuess                 
    -- with these guesses, solve the remaining cells
    call solvePossibleCells              
end procedure    

3.2 Backtracking solver

Unlike the previous one, which finds one solution, the backtracking solver find all solutions of the Sudoku board.
It is an essential piece of the board generation algorithm since it is used to ensure the generated board has one and only one solution.

The backtracking solver uses the method solvePossibleCells from the previous algorithm to speed up the resolution of each branch of solutions.

The pseudo-code is as follows:

procedure findSolutionsInternal
    if current board is solved then
        add a copy of current board to solutions
    end if
    
    set cell = any remaining cell without a value
    
    for each possibility for that cell do
        set cell value = that possibility 
        call findSolutionsInternal recursively
        reset cell value
    end for
end procedure  

procedure findSolutions
    set solutions = instantiate set of solution to be returned
    
    -- set cell values that can be set with human-like approach
    call solvePossibleCells                                        
    
    -- solve remaining cells with backtracking
    call findSolutionsInternal with solutions and current board    
    return solutions
end procedure  

3.3 Board generator

The board generation algorithm is the trickiest part. I tried several things (most methods supporting them are still available in the codebase) ... and got rid of most of them.
The thing is that either I generate only easy boards with down to 22 pre-filled cells in a few milliseconds, or I try to generate difficult boards having only between 18 to 22 pre-filled cells. (I have never successfully generated a board with only 17 pre-filled values even though such boards exist).

In the later case, the duration of the algorithm runs from a few seconds up to several minutes with the following results, in average out of 10 runs:

• Only 1 really difficult board requiring very advanced resolution techniques or even nishio.
• Between 1 and 2 medium to tricky grids requiring a thorough work on possibilities to solve them.
• Between 7 and 8 easy to medium grids requiring only a careful analysis of possibilities for each cell.

I haven't found a way yet to come up with a smarter approach enabling the software to generate more difficult boards and, more importantly, in a quicker time.

Anyway, this is what I have implemented currently, in pseudo-code:

procedure newRandomGrid
    set grid = DEFAULT_GRID -- always starting with the same
    
    perform random permutations between rows in same square groups
    perform random permutations between columns in same square groups
    
    perform random permutations between groups of rows matching squares
    perform random permutations between groups of columns matching squares
    
    -- Map every value to a new random value and swap these values
    -- for every cell
    remap values
    
    return grid    
end procedure

procedure performPossibleRemoves
    for each cell of the grid board having a value do
        set savedValue = value in that cell
        reset cell value
        if grid board is not solvable then-- Using backtracking solver
            set cell value = savedValue
        end if
    end for
    return number of additional cells than could be removed
end procedure

procedure removeValues
    set grid = copy of original given as argument
    
    for each cell of the grid board do
        reset all values
    end for
    
    -- Add a value back for each number
    for each possible value (1..9) then
        pick up randomly one cell of original board containing value
        assign value to corresponding cell in grid board
    end for
    
    -- Add more values until board is solvable
    while grid board is not solvable do -- Using backtracking solver
    
        -- This is key in the process. We add values back to the empty grid by choosing
        -- first the cells of grid board with highest number of possibilities
        set cell = pick up randomly one of most undefined cells
        assign value from corresponding cell in original board
    end while
    
    -- See if there is any more values than can be removed
    call performPossibleRemoves
    
end procedure

-- This is the one that takes a huge amount of time
procedure tryReaddingValues
    set betterFound = true
    while betterFound do
        set betterFound = false
        for each cell of the grid board without a value do
            set cell value = back to former value -- former value is cell from original grid
            
            call performPossibleRemoves
            
            if more than two values could be removed then
                set betterFound = true
                break
            else
                reset cell value
            end if
            
        end for        
    end while
end procedure

procedure generateGrid
    -- Create new random solved grid
    set original = call newRandomGrid   
    
    -- Remove cell values as long as board remains solvable
    set grid = call removeValues with original
    
    -- see if adding back a value enables to remove more
    -- Note: this is the very slow step. One can simply get rid of it
    -- to get a quick but less efficient (i.e. easier boards) generator 
    call tryReaddingValues with grid
    
    return grid
end procedure

Regarding this algorithm, I'm slowly getting out of ideas for new techniques to experiment that would enable the software to generate a difficult grid in far less time.
Again, Any idea / suggestion would be really welcome :-)