Grid Games

Latin square completion

The latin square is a game where the player needs to fill a \(n \times n\) grid with integers between 1 and \(n\), each occuring exactly once in each row and each column. Determining whether a latin square has a solution, given a list of cells already filled, is NP-complete [1].

Generalised Sudoku completion

Sudoku is a game where the player needs to fill a \(9 \times 9\) grid with integers between 1 and \(9\), each occuring exactly once in each row and each column. Furthermore, th grid is divided in 9 \(3 \times 3\) square yielding the additional constraint that all the number inside a square must be distinct. Generalised Sudoku is the same game with a grid of \(k^2 \times k^2\), numbers going from 1 to \(k^2\) and \(k^2\) squares of size \(k \times k\) instead. Determining whether a generalised Sudoku grid has a solution, given a list of cells already filled, is NP-complete [2].

---

[1] Charles J. Colbourn, The complexity of completing partial Latin squares, Discrete Applied Mathematics, Volume 8, Issue 1, 1984, Pages 25-30.

[2] Complexity and completeness of finding another solution and its application to puzzles T. Yato and T. Seta, IEICE Trans. Fundam. Electron., E86-A (5) (2003), pp. 1052-1060.