Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I think you're correct. –  Tunococ Jan 28 '13 at 13:49
add comment

2 Answers

up vote 2 down vote accepted

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)".

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

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.