3-DNF proves the algorithm is in P class

Question

To understand fully, please read link

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?

Answer 1

As I already explained earlier, any algorithm on a 9x9 input takes constant time. Thus it is in P. This is not very interesting or useful.

When people talk about Sudoku being NP-hard, they don't actually mean Sudoku, they are referring to a generalization on a grid of arbitrary size. Your question doesn't prove that this generalized problem is in P.

General comment: It looks like you're immersed in details, but haven't got a solid grasp on the fundamentals/basics yet. I encourage you to spend some more time learning about the definition of languages, decision problems, P, NP, NP-complete, NP-hard, and reductions before trying to take your Sudoku "project" any further. As it stands some of your statements appear to reflect a misunderstanding of basic concepts, and so you're spending time on things that are a dead end or reflect some basic misconceptions. (For instance, an algorithm can't be in P, and a proof can't be in; a problem can be.) I hope you'll take this as aimed to help you learn, rather than an attempt to criticize you personally or tear you down.