## Sudoku Laboratoy

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 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:

proceduresolveSinglePossibilitiesfor eachcellof theboarddoifcell has no value setthenfor eachpossible value (1..9)doifvalue is single possibility according to row, column or squarethenset value on cellend ifcheck whether any other value is possible by checking each with row, column and squareifno other value is possiblethenset value on cellend ifend forend ifend forend procedureproceduresolvePossiblitiesfor eachrow, column and squareof theboarddofor eachcellof therow, column or squaredoifthere are n other cells that have the same n possibilities (or fewer)thendiscard these possibilities from all other cellsend ifend forend forend procedureproceduresolveSquarePossiblitiesfor eachrow, column and squareof theboarddofor eachcellof therow, column or squaredoifthere are n other cells that have the same n possibilities (or fewer)thenfor eachnumberof thesepossibilitiesdoifall cells containing number are in same square discard number from all other cells of squareend ifend forend ifend forend forend procedureproceduresolvePossibleCellsfor eachcellof theboarddoreset all possibilitiesend forwhilechanges are made on cells by the calls belowdo-- this sets the cells for which a single value -- is the only possibilitycallsolveSinglePossibilities-- Compute cell possibilitiesfor eachcellof theboarddofor eachpossible value (1..9)doifvalue is possible according to row, column or squarethenadd value to cell possibilitiesend ifend forend forwhilechanges are made on cell possibilities by the calls belowdo-- in each element (row, column, square) identify group -- of possibilities and discard them from the other cellscallsolvePossiblities-- 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.callsolveSquarePossiblitiesend whilefor eachcellof theboarddoifcell has only one possibility leftthenset value as that single possibilityend ifend forend whileend procedureproceduresolveUsingGuessset= any one of the remaining cells with fewest possibilitieswhilesuch a cell is founddo-- Make a guess for this cellsetcell value = any one if its possibilities -- Try to solve using that guesscallsolvePossibleCells-- If the call above made sure the board cannot be -- solved using that guessifboard is unsolvablethenreset cell valueelse ifboard is solvedthen-- Fix guess fix cell value -- set cell value definitelyelsecallsolveUsingGuessrecursivelyend ifend whileend procedureproceduresolve -- solve using human-like techniquescallsolvePossibleCells-- if grid is not completed, make guesses (nishio)callsolveUsingGuess-- with these guesses, solve the remaining cellscallsolvePossibleCellsend 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

from the
previous algorithm to speed up the resolution of each branch of solutions.
*solvePossibleCells*

The pseudo-code is as follows:

procedurefindSolutionsInternalifcurrent board is solvedthenadd a copy of current board to solutionsend ifsetcell = any remaining cell without a valuefor eachpossibility for that celldosetcell value = that possibilitycallfindSolutionsInternalrecursively reset cell valueend forend procedureprocedurefindSolutionssetsolutions = instantiate set of solution to be returned -- set cell values that can be set with human-like approachcallsolvePossibleCells-- solve remaining cells with backtrackingcallfindSolutionsInternalwith solutions and current boardreturnsolutionsend 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:

procedurenewRandomGridsetgrid = 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 valuesreturngridend procedureprocedureperformPossibleRemovesfor eachcellof thegrid board having a valuedosetsavedValue = value in that cell reset cell valueifgrid boardis notsolvablethen-- Using backtracking solversetcell value = savedValueend ifend forreturnnumber of additional cells than could be removedend procedureprocedureremoveValuessetgrid = copy of original given as argumentfor eachcellof thegrid boarddoreset all valuesend for-- Add a value back for each numberfor eachpossible value (1..9)thenpick up randomly one cell of original board containing value assign value to corresponding cell in grid boardend for-- Add more values until board is solvablewhilegrid boardis notsolvabledo-- 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 possibilitiessetcell = pick up randomly one of most undefined cells assign value from corresponding cell in original boardend while-- See if there is any more values than can be removedcallperformPossibleRemovesend procedure-- This is the one that takes a huge amount of timeproceduretryReaddingValuessetbetterFound =truewhilebetterFounddosetbetterFound =falsefor eachcellof thegrid board without a valuedosetcell value = back to former value -- former value is cell from original gridcallperformPossibleRemovesifmore than two values could be removedthensetbetterFound =truebreakelsereset cell valueend ifend forend whileend procedureproceduregenerateGrid -- Create new random solved gridsetoriginal =callnewRandomGrid-- Remove cell values as long as board remains solvablesetgrid =callremoveValueswith 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) generatorcalltryReaddingValueswith gridreturngridend 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 :-)

Tags: algorithms backtracking c++ laboratory programming sudoku