Thursday, 13 August 2009

Sudoku

Whilst checking out the new programming language Scala I suddenly had this strange urge to write a program to solve Sudoku problems. It occurred to me that the solutions to Sudoku could be found fairly easily using a recursive brute force algorithm. Anyway I put the Scala stuff to one side and reverted back to my old favorite Groovy.
Writing the code was fairly simple - the algorithm is rather straighforward...

solve( board )
foreach blank space on the board
for the numbers i = 1 to 9
if i is eligible (meets the row/col criteria)
set the blank space to i
if solve(board) returns true then return true
else
try the next number
if all numbers tried return false
if all spaces tried return true

The funky thing is that given a blank board the program will generate an entire Sudoku number set for you. Alternatively you can place numbers at random places on the board and then get the program to fill in the rest. An interesting thing to try is to attempt to find a pattern on numbers which takes the longest number of iterations to solve. Naturally, if the initial pattern fails the essential Sudoku criteria then no solution will be found by the algorithm and you will end up with the program making something in the order of 9^81 attempts before failing.

You can download my completed version from here.