Examination of the heuristic solution and combinatorial properties of Sudoku puzzles and their variants

This work involves the analysis of Sudoku, and its many variants (including Super Sudoku and the Dion Cube), through the use of combinatorial tools and search optimization techniques from applied artificial intelligence. Relationships between the Sudoku-type puzzles and combinatorial structures, such as Latin Squares and Rectangles, and Magic Squares, enable connections to be made between these popular puzzles and real-world applications.

Recent results in this area have been: the determination of the numbers of possible Rudoku grids and corresponding proof; the demonstration that Sudoku puzzles can be solved reliably through problem initialization and the appropriate employment of heuristics that directly exploit features of the problem domain, regardless of rated complexity and number of givens; several properties arising from an investigation into quasi-magic Sudoku grids.

Former research student Sian Jones is continuing to investigate properties of Sudoku and its related Dion Cube, and associated heuristic methods for their solution, expanding on work in her thesis “The use of combinatorial and heuristic-search techniques to solve the Dion Cube and other complex Sudoku-type puzzles”.

For more information, please contact Dr Stephanie Perkins or Prof Paul Roach.