Entries tagged [backtracking]
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.