Title: A threshold for fractional Sudoku completion
| Speaker: | Peter Dukes |
| Affiliation: | University of Victoria |
| Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: The popular puzzle game Sudoku presents a player with a 9-by-9 grid having some numbers filled in a few of the cells. The player must finish filling in numbers from 1 to 9 so that every row, column, and 3-by-3 box contains each of these numbers exactly once. We can extend Sudoku so that the boxes are $h$-by-$w$, and the overall array is $n$-by-$n$, where $n=hw$. The puzzle is now similar to completing a latin square of order n, except of course that Sudoku has an additional box condition.
Through studying a system of linear equations associated with Sudoku latin squares, we encounter some interesting eigenvalues and eigenvectors. These can be used (with the help of computer) to show that every sufficiently large and sparse Sudoku puzzle has a *fractional* solution. This fractional relaxation permits the player to cut up their symbol allocations into positive fractional pieces, so long as every entry still receives one symbol worth of allocation, and every row, column, and box still has every symbol occurring exactly once.
This is joint work with my MSc student Kate Nimegeers.