Page 54 - Discrete Mathematics and Its Applications

1.3 Propositional Equivalences 33

To encode a Sudoku puzzle, let p(i, j, n) denote the proposition that is true when the number
n is in the cell in the ith row and jth column. There are 9 × 9 × 9 = 729 such propositions, as
i, j, and n all range from 1 to 9. For example, for the puzzle in Figure 1, the number 6 is given
as the value in the fifth row and first column. Hence, we see that p(5, 1, 6) is true, but p(5,j, 6)
is false for j = 2, 3,..., 9.
Given a particular Sudoku puzzle, we begin by encoding each of the given values. Then,
we construct compound propositions that assert that every row contains every number, every
column contains every number, every 3 × 3 block contains every number, and each cell contains
no more than one number. It follows, as the reader should verify, that the Sudoku puzzle is solved
by finding an assignment of truth values to the 729 propositions p(i, j, n) with i, j, and n each
ranging from 1 to 9 that makes the conjunction of all these compound propositions true. After
listing these assertions, we will explain how to construct the assertion that every row contains
every integer from 1 to 9.We will leave the construction of the other assertions that every column
contains every number and each of the nine 3 × 3 blocks contains every number to the exercises.

For each cell with a given value, we assert p(i, j, n) when the cell in row i and column
j has the given value n.
We assert that every row contains every number:

9 9 9

p(i, j, n)
i=1 n=1 j=1

We assert that every column contains every number:

9 9 9

p(i, j, n)
j=1 n=1 i=1

We assert that each of the nine 3 × 3 blocks contains every number:
It is tricky setting up the
two inner indices so that 2 2 9 3 3
all nine cells in each p(3r + i, 3s + j, n)
square block are
examined. r=0 s=0 n=1 i=1 j=1

To assert that no cell contains more than one number, we take the conjunction over all

values of n, n , i, and j where each variable ranges from 1 to 9 and n = n of p(i, j, n) →

¬p(i, j, n ).
We now explain how to construct the assertion that every row contains every number.
9
First, to assert that row i contains the number n, we form p(i, j, n). To assert that
j=1
row i contains all n numbers, we form the conjunction of these disjunctions over all nine
9 9
possible values of n, giving us p(i, j, n). Finally, to assert that every row contains
n=1 j=1
9 9
every number, we take the conjunction of p(i, j, n) over all nine rows. This gives
n=1 j=1
9 9 9
us i=1 n=1 j=1 p(i, j, n). (Exercises 65 and 66 ask for explanations of the assertions that
every column contains every number and that each of the nine 3 × 3 blocks contains every
number.)
Given a particular Sudoku puzzle, to solve this puzzle we can find a solution to the satisfia-
bility problems that asks for a set of truth values for the 729 variables p(i, j, n) that makes the
conjunction of all the listed assertions true.