# 3-DNF proves the algorithm is in P class

After, reading the link we will take a look at how we recover our solutions to a constrained Sudoku Puzzle.

If we assume that a sudoku puzzle was generated with this procedure we can now create a "semi"-solver. I say "semi" because we need the $$3 \times 3$$ grid $$M_{2,2}$$ already solved for us. Let's assume we have this. As an example I will assume we are provided:

$$\begin{bmatrix} 5 & 9 & 6\\ 1 & 2 & 4\\ 3 & 7 & 8 \end{bmatrix}$$

Now we will flatten it into: $$[5,9,6,1,2,4,3,7,8]$$ and permute as follows:

[8, 5, 9, 6, 1, 2, 4, 3, 7]-----list 1
[7, 8, 5, 9, 6, 1, 2, 4, 3]-----list 2
[3, 7, 8, 5, 9, 6, 1, 2, 4]-----list 3
[4, 3, 7, 8, 5, 9, 6, 1, 2]-----list 4
[2, 4, 3, 7, 8, 5, 9, 6, 1]-----list 5
[1, 2, 4, 3, 7, 8, 5, 9, 6]-----list 6
[6, 1, 2, 4, 3, 7, 8, 5, 9]-----list 7
[9, 6, 1, 2, 4, 3, 7, 8, 5]-----list 8
[5, 9, 6, 1, 2, 4, 3, 7, 8]-----list 9


Now for each list, we will turn them into a $$3 \times 3$$ grid using the same mapping in step 2 above. For example list 1 would get mapped to

$$\begin{bmatrix} 8 & 5 & 9 \\ 6 & 1 & 2 \\ 4 & 3 & 7 \end{bmatrix}$$

Now we position these in the game board the same way we did as step 3 above. For example our layout would be as follows:

**list1**  **list4**  **list7**

**list2**  **list5**  **list8**

**list3**  **list6**  **list9**


In the prior example this would give us the correct solution:

$$M = \begin{bmatrix} 8 & 5 & 9 & 4 & 3 & 7 & 6 & 1 & 2\\ 6 & 1 & 2 & 8 & 5 & 9 & 4 & 3 & 7\\ 4 & 3 & 7 & 6 & 1 & 2 & 8 & 5 & 9\\ 7 & 8 & 5 & 2 & 4 & 3 & 9 & 6 & 1\\ 9 & 6 & 1 & 7 & 8 & 5 & 2 & 4 & 3\\ 2 & 4 & 3 & 9 & 6 & 1 & 7 & 8 & 5\\ 3 & 7 & 8 & 1 & 2 & 4 & 5 & 9 & 6\\ 5 & 9 & 6 & 3 & 7 & 8 & 1 & 2 & 4\\ 1 & 2 & 4 & 5 & 9 & 6 & 3 & 7 & 8\\ \end{bmatrix}$$

Then we have list 9 (our input) will always give you correct solution in quadratic time.

For further illustration, I intend to prove that the algorithm aforementioned is in P class in two ways.

Here, we'll take a look at 3-DNF.

(L1 ∧ L2 ∧ L3) | (L4 ∧ L5 ∧ L6) | (L7 ∧ L8 ∧ L9)

Let L1=list1, L2 = list2,...

**list1**  **list4**  **list7**

**list2**  **list5**  **list8**

**list3**  **list6**  **list9**


Therefore, the algorithm generates grids and recovers correct solutions easily.

Now, lets say I want to check the satsifiability of the algorithm's circular shifts. Here, I generate 3 more grids to show that there is a 3x3 positive 3-satisfying permutes.

l = [8, 5, 9, 6, 1, 2, 4, 3, 7]

[5, 9, 6, 1, 2, 4, 3, 7, 8]-l1
[9, 6, 1, 2, 4, 3, 7, 8, 5]-l2
[6, 1, 2, 4, 3, 7, 8, 5, 9]-l3
[1, 2, 4, 3, 7, 8, 5, 9, 6]-l4
[2, 4, 3, 7, 8, 5, 9, 6, 1]-l5
[4, 3, 7, 8, 5, 9, 6, 1, 2]-l6
[3, 7, 8, 5, 9, 6, 1, 2, 4]-l7
[7, 8, 5, 9, 6, 1, 2, 4, 3]-l8
[8, 5, 9, 6, 1, 2, 4, 3, 7]-l9


x = [5, 9, 6, 1, 2, 4, 3, 7, 8]

[9, 6, 1, 2, 4, 3, 7, 8, 5]-x1
[6, 1, 2, 4, 3, 7, 8, 5, 9]-x2
[1, 2, 4, 3, 7, 8, 5, 9, 6]-x3
[2, 4, 3, 7, 8, 5, 9, 6, 1]-x4
[4, 3, 7, 8, 5, 9, 6, 1, 2]-x5
[3, 7, 8, 5, 9, 6, 1, 2, 4]-x6
[7, 8, 5, 9, 6, 1, 2, 4, 3]-x7
[8, 5, 9, 6, 1, 2, 4, 3, 7]-x8
[5, 9, 6, 1, 2, 4, 3, 7, 8]-x9


y = [9, 6, 1, 2, 4, 3, 7, 8, 5]

[6, 1, 2, 4, 3, 7, 8, 5, 9]-y1
[1, 2, 4, 3, 7, 8, 5, 9, 6]-y2
[2, 4, 3, 7, 8, 5, 9, 6, 1]-y3
[4, 3, 7, 8, 5, 9, 6, 1, 2]-y4
[3, 7, 8, 5, 9, 6, 1, 2, 4]-y5
[7, 8, 5, 9, 6, 1, 2, 4, 3]-y6
[8, 5, 9, 6, 1, 2, 4, 3, 7]-y7
[5, 9, 6, 1, 2, 4, 3, 7, 8]-y8
[9, 6, 1, 2, 4, 3, 7, 8, 5]-y9


Here, I demonstrate that the 3x3 shift meets satisfiability for 9! Sudoku grids generated by the algorithm. At the end of the question I prove that the expression is always meets satisfiability when given the correct inputs.

(l1 ∨ x9 ∨ y8) ∧ (l2 ∨ x1 ∨ y9)

l1 = [5, 9, 6, 1, 2, 4, 3, 7, 8]

x9 = [5, 9, 6, 1, 2, 4, 3, 7, 8]

y8 = [5, 9, 6, 1, 2, 4, 3, 7, 8]

All the listed elements above have their defined variables within these expressions. All the expressions hold true.

(𝑙1∨𝑥9∨𝑦8)∧(𝑙2∨𝑥1∨𝑦9)∧(𝑙3∨𝑥2∨𝑦1)∧(𝑙4∨𝑥3∨𝑦2)∧(𝑙5∨𝑥4∨𝑦3)∧(𝑙6∨𝑥5∨𝑦4)∧(𝑙7∨𝑥6∨𝑦5)∧(𝑙8∨𝑥7∨𝑦6)∧(𝑙9∨𝑥8∨𝑦7)∧(𝑙1∨𝑥9∨𝑦8)∧(𝑙2∨𝑥1∨𝑦9)

Here is a chart showing the 3-satsifiability of the algorithm. Proving that the 3x3 shift overlaps all 9! valid grids that the algorithm can generate

Overall, are these proofs correct that constrained Sudoku is in P class?