3

I have started reading Rosen's Discrete Mathematics and I have reached the topic of propositional satisfiability and it's application in solving Sudoku.

Solving such puzzles consists of solving the following assertions:

  • Every row contains every number
  • Every column contains every number
  • Every 9 x 9 block contains every number
  • And then taking a conjunctions of the values so obtained.

The book has solved the predicate function for the first case as:

$$ \land_{i=1}^9 \land_{n=1}^9 \lor_{j=1}^9 \ \ p(i,j,n) $$

The explanation will be something like:

[cell(1,1) contains 1 or cell(1,2) contains 1 or ...] and [cell(1,1) contains 2 or cell(1,2) contains 2 or ...] for all 9 rows.

I came up with my a different solution:

$$ \land_{i=1}^9 \land_{j=1}^9 \lor_{n=1}^9 \ \ p(i,j,n) $$

thinking along the lines:

[cell(1,1) contains 1 or cell(1,1) contains 2 or ...] and [cell(1,2) contains 1 or cell(1,2) contains 2 or ...] for all 9 rows.

When I think about this, both of the formulas appear to be the same -- going through all the columns and validating that every row contain every number.

Are these the same really? Or am I missing out on something?

Tushar Tyagi
  • 155

1 Answers1

2

No your formulas are not the same. Your formula does not say "Every row contains every number" but rather it only states that each cell needs to contain some number between $0$ and $9$. To make it more specifik:

In your formula if cell(1,1) contain 1 then the first part of the conjunction is true, however then if cell (1,2) also contain 1 then the second part of the concjunction is also true. We could continue like this untill all cells in row $1$ contain the number $1$.

This is avoided in the books formula, since for the first part of the conjunction to be true $1$ has to appear in cell(1,1), cell(1,2),..., cell(1,8) or cell(1,9) i.e. $1$ has to appear in row 1. Then to make the secon part of the conjunction true $2$ has to appear in cell(1,1), cell(1,2),...,cell(1,8) or cell(1,9) i.e. $2$ has to appear in row 1. And so on, for each number, thus each number appears in row $1$.

Ove Ahlman
  • 4,329