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 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 ManualThe 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).
- A number given alone will set the value for the cell.
- Several numbers separated by a space will set the possibilities for the cell.
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 LinuxFirst 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
2.1 On WindowsBuilding on windows is slightly more complicated since one needs both mingw and wxWidgets. A dedicated how-to is available in file
3. AlgorithmsSudoku 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,
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 solverThe 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:
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
solvePossibleCellsfrom the previous algorithm to speed up the resolution of each branch of solutions. The pseudo-code is as follows:
3.3 Board generatorThe 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.
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 :-)