3 - Sudoku

Summary

In this chapter, we will explain how to solve a Sudoku puzzle using ideas from algebraic geometry and computer algebra. In fact, we will represent the solutions of a Sudoku as the points in the vanishing locus of a polynomial ideal I in 81 variables, and we will show that the unique solution of a well-posed Sudoku can be read off from the reduced Gröbner basis of I. We should point out, however, that attacking a Sudoku can be regarded as a graph coloring problem, with one color for each of the numbers 1, . . . ,9, and that graph theory provides much more efficient methods for solving Sudoko than do Gröbner bases.

A completed Sudoku is a particular example of what is called a Latin square. A Latin square of order n is an n Ⅹ n square grid whose entries are taken from a set of n different symbols, with each symbol appearing exactly once in each row and each column. For a Sudoku, usually n = 9, and the symbols are the numbers from 1 to 9. In addition to being a Latin square, a completed Sudoku is subject to the condition that each number from 1 to 9 appears exactly once in each of the nine distinguished 3 Ⅹ 3 blocks.