[Math] Sudoku with special properties

algorithmsmatricespuzzlerecreational-mathematicssudoku

Sudoku is a puzzle, with the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also "sudoku-blocks") contains all of the digits from 1 to 9.

Let's define block as a 3×3 sub-grid (not necessarily forming one of the sudoku-blocks, but including them) containing all the digits 1 to 9.

Let's define N as a number of all valid blocks on the grid.

For the usual sudoku puzzle $N=9$.

The maximum theoretically possible $N=49$ (7 blocks per row*7 blocks per column).

I found sudoku puzzle with $N=10$, to prove that puzzles with $N>9$ exist. Here's one:

+-------+-------+-------+
| 3 9 6 | 4 1 5 | 2 7 8 |
| 1 2 5 | 7 3 8 | 4 6 9 |
| 4 7 8 | 2 6 9 | 3 1 5 |
+-------+-------+-------+
| 7 5 9 | 6 4 2 | 8 3 1 |
| 8 4 3 | 5 9 1 | 7 2 6 |
| 2 6 1 | 3 8 7 | 5 9 4 |
+-------+-------+-------+
| 5 3 4 | 9 2 6 | 1 8 7 |
| 6 8 7 | 1 5 3 | 9 4 2 |
| 9 1 2 | 8 7 4 | 6 5 3 |
+-------+-------+-------+

The 10th block is in the top right corner:

5 2 7
8 4 6
9 3 1

And here's another with $N=33$ ($N = 3*7 + 3*7 – 9$)

+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
+-------+-------+-------+
| 2 3 1 | 5 6 4 | 8 9 7 |
| 5 6 4 | 8 9 7 | 2 3 1 |
| 8 9 7 | 2 3 1 | 5 6 4 |
+-------+-------+-------+
| 3 1 2 | 6 4 5 | 9 7 8 |
| 6 4 5 | 9 7 8 | 3 1 2 |
| 9 7 8 | 3 1 2 | 6 4 5 |
+-------+-------+-------+

Questions:

  1. Does sudoku puzzle with N=49 exist? No
  2. If yes, then what is it?
  3. If no, then what's the maximum possible N? Why?

Update. This update is fully based on @Emisor answer and proof.

Assume $N=49$ possible, let's try generating a puzzle:

+-------+--- 
| 1 2 3 | X 
| 4 5 6 | Y 
| 7 8 9 | Z
+-------+---
| A B C | D

The block on the first figure is to be taken as our "starting" one. Since there are no other numbers on the board, having them ordered makes no difference, for now.

Now, for $N=49$ several conditions must be met:

  1. X, Y, Z must be filled with 1, 4, 7
  2. A, B, C must be filled with 1, 2, 3

Since, X cannot be 1 and A cannot be 1, this statements are also true:

  1. Y or Z must be 1
  2. B or C must be 1

That makes block 56Y,89Z,BCD invalid as it must contain two 1, therefore $N=49$ is impossible.

That makes only one question left:

What's the maximum possible $N$? Why?

Best Answer

Proof that $N=49$ is impossible:

+-------+---   1) +-------+      2) +-------+      3) +-------+
| 1 2 3 | X       |(1)2 3 |*1       | 1 2 3 |(7)      | 1 2 3 |(4)
| 4 5 6 | Y       |(4)5 6 |*4       | 4 5 6 | 1       |(4)5 6 | 7
| 7 8 9 | Z       |(7)8 9 |*7       |(7)8 9 | 4       | 7 8 9 | 1
+-------+---      +-------+         +-------+         +-------+ 
| A B C | D       | A B C | D       | A*B*C |*D       | A*B*C |*D

The block on the first figure is to be taken as our "starting" one. Since there are no other numbers on the board, having them ordered makes no difference, for now. Now, there are 3 different ways to fill tiles XYZ with 1 4 and 7, but they all fail. Since:

Case 1: Obviously, there's 3 collisions.

Case 2: BCD must contain 237 on any order. However, 7 can't be on B or C because it collides with our original grid. And it can't be on D either, because it's on the same row as the recently added one.

Case 3: Similar to before, except with 4.

That means there's no way to have those 2 blocks (23X,56Y,89Z and 56Y,89Z,BCD) successfully.

Therefore, $N=49$ is impossible.

Related Question