by Jerome Kehrli
Posted on Tuesday Aug 30, 2016 at 09:02AM in Computer Science
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
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 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 :-)