0
$\begingroup$

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

enter image description here

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Okay, I was just going to build upon a new questions after reading through reductibility and etc on Wikipedia. And, I'm building upon the same subject on every new question. I'll accept your answer while I formulate a new question as I'm getting more clarification step by step(both reading and asking) $\endgroup$ – Travis Wells Apr 24 at 19:29
  • $\begingroup$ @TravisWells, Cool! I'd suggest finding a good textbook or an online course on algorithms or complexity theory. Wikipedia isn't a great resource. Don't expect it to be something you can learn in one sitting. Have fun -- it's a beautiful subject! $\endgroup$ – D.W. Apr 24 at 19:34
  • $\begingroup$ I'm in the process of formulating a question about NM-3sat. Which is basically no mixed instances. (eg. L1 or x9 or y8) and (l2 or x1 or y1) No negations unless all variables are negated. I was wondering if it would be possible to reduce DNF to NM-3sat showing that constrained puzzles can be just as hard to solve. $\endgroup$ – Travis Wells Apr 24 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.