The 17th Tsinghua Logic Colloquium

Some Remarks on the Sudoku Problem

The pleasure induced by solving logic puzzles, of which sudoku is a canonical example, has both sensory and intellectual components. One sees a pattern and makes an inference. And not all inferences are equal. Some are merely a matter of routine; others require deep insight. The discovery of a trick left by the constructor can make one laugh or cry out with elation. But there is also a slower appreciation of the task. Satisfaction accumulates as the grid is gradually filled in, and is frustrated when one gets stuck. Likewise there is epistemic progress. One starts by knowing very little about the puzzle and finishes with a completed grid, in which there is no more uncertainty.

Despite the obviousness of these remarks to anyone familiar with sudoku, philosophers and logicians have little to add. The problem of accounting for mathematical aesthetics has long been appreciated as a failure in the philosophy of mathematics. And the failure of epistemic logic to account for progress in the solving of a puzzle is also well known. (It is one version of the so-called problem of Logical Omniscience.)

I do not have any brilliant proposal to address these difficulties. I will say a bit more about them, before suggesting that a first step is to try to characterise a kind of natural deduction of sudoku, by which I mean a way of describing parts of a puzzle that lends itself to fairly general schemes of inference that more-or-less match or explain the inferences that we make. It’s a modest idea based on the concept of mereological type judgements: the classification of physical regions into types based on the arrangements they contain. I’ll use this to account both for basic sudoku inferences and some ‘theorems’ that are considered by sudoku solvers to be much more advanced.