A Sudoku board consists of a 9 by 9 grid of "cells", in which each column, row, and "block" (one of nine 3X3 subgrids that tile the board) has each of the numbers 1 through 9 exactly once. A Sudoku "puzzle" is a partially filled-in board, and a "fair" puzzle is one that can be completed in exactly one way. While seemingly just a recreational curiosity, it turns out there is deep mathematics hiding in Sudoku. Questions that have led to interesting directions include:

- How many distinct puzzles are there?
- How can one randomly generate an (interesting) puzzle?
- How can one estimate the hardness of a puzzle?
- How can one computationally solve puzzles?
- What is the smallest number of cells in a fair puzzle?

We discuss some of these questions and the open problems they have led to.

свернуть