Rules of the game
A Sudoku is a number puzzle where the player is given a grid of 9 cells times 9 cells in which some cells contain a number between 1 and 9. The goal is to place one number between 1 and 9 in each remaining cell, while ensure the following rules are satisfied:
- Every row must contain all numbers between 1 and 9.
- Every column must contain all numbers between 1 and 9.
- All blocks of 3×3 cells that decompose the grid in 9 equal parts must contain all the numbers between 1 and 9.
Simplifying the game
If you want to take the challenge of modelling the rules in propositional logic without additional clues, stop reading here. Otherwise, consider first what you would like to model as a logical proposition, that is, a statement that can be true or false. Let us consider a single Sudoku grid where all numbers are fixed, but unknown. What statement can be true or false about the Sudoku grid?
In order to find how to model the game in propositional logic, one way is to simplify the problem. For instance, one may focus on the first rule only. However, this does not make the problem significantly simpler, as each rule is pretty much equal in complexity. Another approach is to reduce the size of it. What if the grid is smaller? To keep the same logic for the rules, we could reduce the grid to a 4 by 4 matrix. Then the rules are:
- Every row must contain all numbers between 1 and 4.
- Every column must contain all numbers between 1 and 4.
- All blocks of 2×2 cells that decompose the grid in 4 equal parts must contain all the numbers between 1 and 4.
Unfortunately, even though the game is now much simpler, the formalisation of the game in propositional logic does not seem easier. Let us simplify it even more. What if we consider a simple 2 by 2 grid with only the 2 rules:
- Each row must contain all numbers between 1 and 2.
- Each column must contain all numbers between 1 and 2.
This may seem silly, since the game is now stupidly trivial. However, what can we say about a 2 by 2 grid that can be either true or false?
We may need to simplify things even more: consider a mini Sudoku that consists of a single cell and that must satisfy the following rules:
- Each row must contain the number between 1 and 1.
- Each column must contain the number between 1 and 1.
- Each block of 1 by 1 cell that decompose the grid into 1 equal part must contain the number between 1 and 1.
Now, what can we say that can be either true or false about this 1 by 1 Sudoku?
If you still do not see what to do, consider the statement S1: the single cell of the 1 by 1 grid contains the number 1. Now, what could we say about the 2 by 2 grid?