3.2.2. Encoding Sudoku with Propositional Variables

So what is a Sudoku puzzle? You will be given a partially complete nine 3 X 3 sub-grids. Each 3 X 3 sub-grid here will be called as a block. Some of the cells here, so each cell will be either filled or it might be blank, so some of the cells here are already filled and that is why it is a partially complete collection of 3 X 3 sub grids, rest of the cells are incomplete here.

A Sudoku puzzle consists of a 9x9 grid divided into nine 3x3 sub-grids, or blocks. Each cell in the grid can either be filled with a number from 1 to 9 or remain blank. The goal is to fill in the blank cells so that every row, column, and block contains every number from 1 to 9 exactly once. This structure makes Sudoku an interesting problem for algorithmic solutions, including those based on propositional logic.

Imagine a classroom where each student must choose a unique number from 1 to 9 to sit in 9 different rows. Each row represents a different subject, and each number must only appear once in every row and column, equivalent to the requirements of a Sudoku. If a student already occupies a seat (for instance, the number 6 in row 5), no other student can claim that number in the same row.

So, I introduce a propositional variable p(i, j, n). This propositional variable p(i, j, n) will be true provided n is assigned to the cell number i, j.

To convert a Sudoku problem into a logical format, we define a propositional variable for each cell. Here, p(i, j, n) represents the proposition that the number n is placed in the cell located at row i and column j. For example, if we assign the value '1' to cell (1,1), then p(1,1,1) is true; if cell (5,1) is filled with the number '6', then p(5,1,6) is true. This setup allows us to track which values are assigned to each cell.

Think of these propositional variables like a giant checkbox system where each checkbox (propositional variable) corresponds to a specific number being placed in a specific cell on the Sudoku board. If you check the box for p(1,1,3), it means you have decided to put the number 3 in the very first cell. If no other number can go there, all other related boxes will remain unchecked.

The solution for the Sudoku puzzle has to satisfy three conditions, namely, each of the values 1 to 9 should occur exactly once in each of the rows. Each of the values 1 to 9 should occur exactly once in each of the columns and each 3 X 3 sub-grid after filling all the empty cells should have all the numbers 1 to 9, of course exactly once.

The fundamental constraints of Sudoku can be represented in propositional logic using the variables defined earlier. Each row, column, and block must include the numbers 1 to 9 exactly once, meaning that for any given row i and number n, at least one of the cells in that row must be filled with n. The same logic applies to the columns and blocks. This helps in forming a logical statement about the arrangement of numbers on the board.

Imagine scheduling students for classes where each student (the numbers 1-9) must appear in every class (rows) but only once. You can think of it as creating unique schedules where no student can occupy the same spot in any subject, similar to how Sudoku requires every number to occupy its unique position in rows, columns, and blocks.

Finally, we also need to ensure that our solution for the Sudoku puzzle should assign only unique values to each cell. It should not happen that a solution says that a particular cell should take the value say 8 and simultaneously the same cell should take value 7 that should not happen.

When constructing the logical expression for the Sudoku puzzle, we must add a layer of constraints to ensure that any specific cell cannot take on more than one value simultaneously. This is accomplished using another propositional expression stating that if a cell (i, j) has a value n, it cannot also have values n’. This helps to maintain the uniqueness and validity of each cell's assignment.

Think about a packed lunch where you can’t place two different sandwiches in the same lunchbox (cell). If you decide to put a turkey sandwich (value 8) in your box, you can’t also put a peanut butter sandwich (value 7) in there—it’s simply not allowed. This ensures that each box only contains one sandwich, just like how each cell in Sudoku must only contain one number.

--