Sudoku

Sudoku puzzles are fun to solve, but cost me a lot of time. I am not a fast sudoku solver. But still, every day the NRC confronts me with a sudoku, to be more precise, a windoku.

To spare time, I decided to create a sudoku solver, knowing that there are very many solvers around, also in the public domain. Using an existing solver would be cheating so I had to write one myself.

To make a difference I wrote the thing in Fortran thus refreshing my knowledge of array syntax, subarrays and pointers. (By the way, using Fortran led to a small but significant improvement in findent).

To my surprise, the solver was very easy to write and small in size: the kernel itself takes 20 lines of uncomplicated code. Of course, more code was needed for I/O and checking the validity of the content of a cell.

The program, using a brute force approach, is hardly optimised, but it still solves even the most difficult sudoku's in a fraction of a second.

Download

The code is available as a tar ball.

Compiling and usage

Make sure you have a Fortran compiler available, for example gfortran. Download the tar ball and enter the following commands:

 tar xf sudoku-solver-fortran.tar.gz
 cd sudoku-solver-fortran
 make fsudoku

Then, run the solver by:

 ./fsudoku < std4.txt

A number of test cases is available as *.txt files. The file fsudoku.f90 starts with a description of the input format.

Back in time ...

Just for fun, I created also a Fortran-66 variety of the program:

  make fsudoku66
  ./fsudoku66 < std4.txt

Solving sudoku's on your screen

Included in the tar ball is some software that enables one to solve sudoku's presented on the web using the script wsudoku-solver. After installation, the script should be available in the games-section. To use it, open a web page with a sudoku puzzle, activate the script by clicking the icon and follow the instructions.

The program is able to solve any easy interpretable sudoku presented on your screen, for example, the sudoku's generated by gnome-sudoku, but not the sudoku's of ksudoku.

The program works as follows:

• locate the sudoku on the screen
• read the numbers by using tesseract, trained to recognise digits (that is why the tarball is so large)
• call fsudoku
• if requested, fill in the sudoku

Installation:

 tar xf sudoku-solver-fortran.tar.gz
 cd sudoku-solver-fortran
 # See the file README for prerequisites.
 # I am not sure all prerequisites are mentioned. To be sure, run
 # the script in a terminal and observe the error messages.
 make
 sudo make install

If the program's icon is not visible under games, try to install in /usr, in stead of /usr/local by adapting the Makefile.

Sudoku's on the web

Below you find a list of some of the sudoku web sites. I observed that some websites are using an unreasonable amount of CPU power while presenting the puzzle. This could be caused by strange programming techniques, but it could also be that my PC takes part in bitcoin mining or something like that.