Will this algorithm always solve a constrained sudoku puzzle in quadratic time?

Question

Constrained Puzzle Generation:

Let us say a sudoku puzzle is generated with the following procedure:

1. Gather a sequence input of 9 unique numbers in the range $[1 .. 9]$. Call it $S$.
2. Map $S$ to a $3 \times 3$ grid $G$ as follows: $$G_{i,j} = \begin{cases} S_{j} & i = 0\\ S_{j + 3} & i = 1\\ S_{j + 6} & i = 2 \end{cases}$$
3. Let's now call $M$ the sudoku board contained of 9 smaller $3 \times 3$ grids. (For instance $G$ will be one of these grids in the board). Define it as follows:

$$M_{i,j} = \text{shift}(G, i + 3 j)$$

Where $\text{shift}(G, 1)$ is defined as:

• Move $G_{0,0}$ to $G_{0,1}$
• Move $G_{0,1}$ to $G_{0,2}$
• Move $G_{0,2}$ to $G_{1,0}$
• Move $G_{1,0}$ to $G_{1,1}$
• Move $G_{1,1}$ to $G_{1,2}$
• Move $G_{1,2}$ to $G_{2,0}$
• Move $G_{2,0}$ to $G_{2,1}$
• Move $G_{2,1}$ to $G_{2,2}$
• Move $G_{2,2}$ to $G_{0,0}$

Then define $\text{shift}(G, n) = \text{shift}(\text{shift}(G, n-1), 1)$. Basically a "shift" is moving everything one cell to the right when possible or else move it down to the leftmost position in the next row.

4. Now, for all present entries in a difficult puzzle (let's say world's hardest puzzle) we make the entries in $M$ present in the final output.

---

Example

1. Let's say our input is $S = [8,5,9,6,1,2,4,3,7]$.
2. We map $S$ to $G$ and get:

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

3. Now we can produce $M$ with the shifts which would look like the following:

$$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}$$

4. Now map this onto the present entries in a difficult puzzle like this one. We get the final grid:

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

---

Semi-Solver

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.

Question

Will this algorithm always solve the given puzzle if we assume the puzzle input was created with these constraints?

Answer 1

Let me start from correctness check, will this method always generate grids abiding sudoku rules?
In fact yes, your shift operator is simply circulant matrix, scattering boxes. Since circulant matrix always abide rules by row and column but not by box, you use permutation (scattering scheme), which now abide all rules, it will produce a subset of possible grids, let us call it $G$.

Now mapping $G_i$ entries to some mask (here given sudoku) is bijective, since you promise to give puzzles generated that way, and those are deterministic.
There are only $9!$ grids generated that way, as far as go either way it will always work. Please note there are 6 670 903 752 021 072 936 960 grids computed by Bertram Felgenhauer and Frazer Jarvis.

Your mapping allow to recover solution if you give 9 unique numbers from grid.

Any other puzzle provided as input will simply fail.