Description

Sudoku is one of many puzzles that require filling in missing entries in some form of grid in order to satisfy some constraints. Sudoku puzzles themselves can be of different sizes, based on an \(m \times m\) grid of \(m \times m\) squares so that the puzzle presents as a matrix with \(m^2\) rows and \(m^2\) columns, Common values of \(m\) are 2, 3 and 4 with \(m=3\) being the most familiar form of puzzle. Larger values of \(m\) are possible. The puzzle is provided with some entries in the matrix pre-filled and the solver must fill in the blank entries. The constraints for a solution are that each row and each column of the matrix, and each of the \(m \times m\) squares making up the grid, must contain each of the natural numbers \(1,\dots,m^2\) (exactly once).

Such puzzles are often solved for entertainment purely by logical deduction or by a combination of trial and error and logical deduction. However, they can also sometimes be solved computationally by brute force using so-called "back-tracking" algorithms, In a more mathematical approach, a puzzle can be reformulated as an optimisation problem for a mathematical function that measures the extent to which a configuration of entries in the grid departs from being a solution to the puzzle. This opens the door to some form of stochastic optimisation or constraint programming. In particular, there is a relatively straightforward way to apply Markov Chain Monte Carlo simulation, a tool that also plays an important computational role in probabilistic modelling and Bayesian statistics.

As well as the problem of how to solve such puzzles, there are interesting mathematical aspects to designing puzzles: making sure that a solution exists is easy if one constructs a puzzle by starting from a complete solution and removing numbers from some cells in the grid. Being sure that the solution is then unique is not so easy, especially if back-tracking is not a feasible approach. There are also other interesting related mathematical questions.

The goal in this project is to explore the mathematical and computational aspects of such puzzles. Because this is a mathematics module, it will be important to engage with the mathematics as well as with computation if you want to do well. There is plenty of scope for students to go in different directions: exploring different kinds of stochastic or other optimisation methods, different approaches to designing puzzles, mathematical representations of the structure of puzzles, puzzles other than Sudoku with similar structure.

Meetings will be as a group during the first term. During the second term, meetings will usually be individual with the supervisor and may sometimes take place online if the supervisor is away from Durham.

Prerequisites

• Probability I (MATH 1597) or equivalent
• An interest in computation and some experience of programming, for example Programming I (MATH 1587) or Data Science and Statistical Computing (MATH 2687)

Corequisites

None

Initial reading

• The Wikipedia entry on "Sudoku" and references therein.
• The Wikipedia entry on "Mathematics of Sudoku" and references therein.