3.2.2. Encoding Sudoku with Propositional Variables

Try these first

1. 1.

   Define the SAT problem in your own words.

   Hint

   Focus on what it means for a formula to be 'true'.

2. 2.

   What does it mean for a proposition to be satisfiable?

   Hint

   Think of it as finding at least 1 condition for truth.

3. 3.

   What does the SAT problem determine?

   • Whether a given proposition can be true.
   • Whether a proposition can never be true.
   • Only the truth value of variables.

   Hint

   Think about the essence of logical expressions.

4. 4.

   True or False: A tautology is sometimes false.

   • True
   • False

   Hint

   Recall the definition of tautology.

5. 5.

   Given a non-CNF formula, derive its CNF equivalent by step-wise application of logic laws.

   Hint

   Divide and conquer the formula step by step.

6. 6.

   Construct a logical expression to represent that no two adjacent cells in a Sudoku can hold the same number.

   Hint

   Consider all pairs of adjacent cells when formulating your expressions.