Project Abstract

Latin squares, and by their extension, sudoku, are popular puzzles that can be played recreationally and studied mathematically. There are different strategies for solving these which can be used by human solvers or by algorithmic automatic solvers. In this project, we experiment with algorithmic Latin square and sudoku solvers that use different methods of solving, such as constraint satisfaction and branching. Latin squares can have different dimensions and their solutions can satisfy different constraints. Our focus is on pandiagonal Latin squares of size 17×17 and queendiagonal sudoku of size 13×13, whose solutions satisfy the queens constraint. The goal is to try to make progress towards optimising the solvers to find solutions to these, contributing towards the overarching goal of enumerating these solutions.The experimentation in the project had the goal of finding optimal parameters to pass into the solvers such that solutions for 17×17 Latin squares and 13×13 sudokus were found and studied. From experimenting, it was observed which of the solvers performs better with which parameters, and why, where possible. Queens and pandiagonal solutions obtained by the experimentation were studied further for trends, patterns, symmetry, and other noteworthy information. This information was used to more strategically choose the input parameters for the solvers and to help solve the open questions regarding these puzzles. The main findings were the optimised parameter combinations for the solvers, that the look-ahead solver was the most effective, and that the order in which partial squares are arranged has no effect on solver efficiency. The minimum amount of lines needed to solve a partial square was reduced from the initial 5, to 3.5, and the time improved.

Keywords: Algorithms, Theoretical Computer Science, Optimisation

 Conference Details

Session: Poster Session B at Poster Stand 131

Location: Sir Stanley Clarke Auditorium at Wednesday 8th 09:00 – 12:30

Markers: Oliver Kullmann, Mark Jones

Course: MSci Computer Science, 3rd Year

Future Plans: I’m continuing studies