Rising Stars – Sudoku

Are your Sudoku strategies suboptimal?

Much scientific research is directed towards areas of immediate and obvious practical benefit, or else startlingly abstract and beautiful ideas at the very limits of human comprehension. Sometimes, however, the most interesting work is that which provides a novel way of looking at everyday phenomena, whether as a useful test of general principles or simply motivated by the joy of finding things out.

A final-year Computer Scientist, Lyle Entwistle told us that he’d always been interested in games and puzzles; when a project on algorithmic approaches to Sudoku was included on the department’s dissertation list it seemed an obvious choice. The presentation focussed on two aspects of his project, namely solving Sudoku puzzles and estimating their difficulty (Lyle also built a puzzle generator, but time constraints prevented its inclusion in the talk). Both tasks highlighted the usefulness of Sudoku for testing a range of computational and mathematical techniques.

The rules of Sudoku are deceptively simple: a 9×9 grid is divided into nine smaller 3×3 squares, and the aim is to fill the grid with the numbers one through nine such that each appears once and only once in every column, row and square. In practice they can be extremely difficult so the programme had to include a variety of techniques for attacking the puzzle. The initial approaches emulate human strategies, checking the possible values for each cell to remove contradictions and narrow down the possibilities.

If these attempts are exhausted and the puzzle remains incomplete then the second stage is to employ a ‘path consistency’ attack, considering possible working combinations for cells within a square. These are sufficient to solve any normal Sudoku, but if all else fails there’s one final level of techniques, culminating in a brute force attack on any cells remaining from especially diabolical set-ups.

The flip-side of the solver is a model for estimating how long a human would take to solve the puzzle. The raw data was provided by a popular Sudoku website which lists the average solve time for each problem. The solver generated the easiest solution method and this was then matched with the times from the website. Crucially, Lyle included details such as the distance between compared cells and the number of times a method had been employed in his analysis in addition to the basic moves employed.

The project had initially been inspired by a paper which had proposed a model for the time taken to solve Sudoku, but by using multiple linear regression on his data and including the additional properties Lyle was able to produce a model which outperformed it.

We wish Lyle all the best for the coming year as he works towards an M.Sc. in Advanced Computing at Imperial College London.

Leave a Reply