# Sodoku Puzzles and Propositional Logic

I am currently reading about how to solve Sudoku puzzles using propositional logic. More specific, they use the compound statement $\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p(i,j,n)$, where $p(i,j,n)$ is the proposition that is true when the number $n$ is in the cell in the $ith$ row and $jth$ column, to denote that every row contains every number. I know that this is what the entire compound statement implies, but I am trying to read each individual statement together. Taking one single case, does $\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p(i,j,n)$ say that in the first row, the number one will be found in the first column, or second column, or third column, etc?

-
I think you're correct. –  Tunococ Jan 28 '13 at 13:49

The formula says "for every allowed value of the row $i$ and the value $n$, there is at least one column $j$ for which the $(i,j)$ location of the grid is filled with the value $n$".

The translation of Sudoko to propositional logic does not make the problem fundamentally easier. Any logic problem can be rewritten as a Sudoku, too, and solving either type of problem in general is computationally difficult (NP-complete).

does $\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p(i,j,n)$ say that in the first row, the number one will be found in the first column, or second column, or third column, etc?

No, the formula saying that is $\bigvee_{j=1}^{9}~p(1,j,1)$ which is the $i=1$,$n=1$ specialization of the first formula. The disjunction indexed by $j$ unpacks to "p(1,1,1) OR p(1,2,1) OR p(1,3,1) OR ... p(1,9,1)".

-
So, is what we have both said essentially the same, yours being more general? –  Mack Feb 2 '13 at 16:15
I added some more to directly answer the question. –  zyx Feb 2 '13 at 20:20

Although expressible as propositional logic, for practical solutions, it is computationally more effective to view Sudoku as a Constraint Satisfaction Problem. See Chapter 6 of Russell and Norvig: Artificial Intelligence - A Modern Approach, for example.

-