Question

Show how the solution of a given4x4Sudoku puzzle can be found by solving a satisfiability problem.

Short answer

Suppose that p(i,j,n) indicates the cell in row i and column j and also has a value of n.The solution of a given 4x4 Sudoku puzzle can be found by the following way.

$$\begin{gathered} {{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)} \\ {{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)} \\ {{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{r}\mathbf{=}\mathbf{0}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{s}\mathbf{=}\mathbf{0}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{2}\mathbf{r}\mathbf{+}\mathbf{i}\mathbf{,}\mathbf{2}\mathbf{s}\mathbf{+}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)} \\ \mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{\to }\mathbf{\neg }\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{\text{'}}\mathbf{)} \end{gathered}$$

Step-by-step solution

Definition of  Sudoku puzzle    

A 4x4Sudoku puzzle includes four rows, four columns, and four boxes.

To Find the solution of a given 4x4 Sudoku puzzle.

Let p(i,j,n) be the cell in row in row i and column j and also has a value of n.

Each row must contain every number between 1 and 4.

That means there are four rows and four columns.

${{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)}$

Hence, each block contains every number1 between and4 .

${{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{r}\mathbf{=}\mathbf{0}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{s}\mathbf{=}\mathbf{0}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{2}\mathbf{r}\mathbf{+}\mathbf{i}\mathbf{,}\mathbf{2}\mathbf{s}\mathbf{+}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)}$

Therefore, no cells include more than one number.

$\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{\to }\mathbf{\neg }\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{\text{'}}\mathbf{)}$

Hence, the solution of a given 4X4 Sudoku puzzle can be create by solving a satisfiability problem.

$$\begin{gathered} {{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)} \\ {{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)} \end{gathered}$$

${{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{r}\mathbf{=}\mathbf{0}}{{\mathbf{\wedge }}^{\mathbf{4}}}_{\mathbf{s}\mathbf{=}\mathbf{0}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{n}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}{{\mathbf{\vee }}^{\mathbf{4}}}_{\mathbf{j}\mathbf{=}\mathbf{1}}\mathbf{P}\mathbf{(}\mathbf{2}\mathbf{r}\mathbf{+}\mathbf{i}\mathbf{,}\mathbf{2}\mathbf{s}\mathbf{+}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)}$

$\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{\to }\mathbf{\neg }\mathbf{P}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{n}\mathbf{\text{'}}\mathbf{)}$