The New Sudoku Players' Forum

[999_Springs]

jpf, coloin's latest puzzle is what he thinks is the smallest 18-clue, not the smallest puzzle with any number of clues. mauricio's puzzle isn't an 18-clue

[JPF]

thanks, it's clear now.

JPF

[JPF]

The smallest minimal puzzle: Mauricio's puzzle is proved to be the smallest

In April 2021 I asked here for the smallest valid minimal puzzle in minlex form. The best known one is Mauricio's (2007):

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.1...3.7..25.6..8..367.4.19


Code: Select all

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


At that time some cases were settled: Serg showed that one of the patterns I asked about is contained in the maximal invalid pattern P123, and coloin explored band 3 with bands 1 and 2 fixed as in Mauricio's puzzle (7 valid fillings, about 2 million puzzles reduced with gridchecker), without finding anything smaller.

An exhaustive computation, described below, indicates that no valid puzzle (minimal or not) has a smaller minlex form. I would be glad if someone could check it independently.

1) The cases
In a minlex form, reading the cells in order, each new digit is the smallest one not used before (the first clue is a 1, the first different digit is a 2, and so on).
A smaller puzzle S agrees with Mauricio's puzzle M up to some cell p where M has a digit, and has there either an empty cell or a smaller digit.
- 25 cases with an empty cell: one for each of the 25 clues of M ("." is smaller than any digit).
- 15 cases with a smaller digit. At a clue of M, a smaller digit is possible only if it has already appeared before (minlex rule) and if it does not conflict with an earlier clue of M in the same row, column or box. Only 9 clues of M allow one:

Code: Select all

cell   M   smaller digits possible
r5c8   4   1
r6c5   4   1
r7c8   7   2, 5, 6
r8c3   5   4
r8c5   6   1
r8c8   8   1, 3
r9c3   6   4
r9c4   7   1, 2, 4, 5
r9c9   9   5


that is 1+1+3+1+1+2+1+4+1 = 15 cases.
Total: 25 + 15 = 40 cases, 3 in band 1, 11 in band 2 and 26 in band 3.

2) The method
For a case p and a solution grid G, call "extended puzzle" the puzzle made of the beginning of S (the clues of M before p, and the smaller digit at p if any) and of all the cells of G after p.
If S were valid with solution G, the extended puzzle would contain all the clues of S and have the same solution, so it would be valid too.
So it is enough to show that, in every case and for every grid G compatible with the beginning of S, the extended puzzle has more than one solution.

3) Band 1 (3 cases: the 3 clues of M in band 1, r2c9, r3c6 and r3c9, each replaced by an empty cell; no smaller digit is possible there)
- Empty cell at r2c9: rows 1 and 2 would be empty, and two empty rows in a band can be swapped.
- Empty cell at r3c6 or r3c9: a check of all 56 x 6^6 = 2612736 band fillings with first row 123456789 (enough, since renaming the digits does not matter here) shows that, with bands 2 and 3 fully given, the band always has another filling with the same column contents and the same values at its clues.

4) Bands 2 and 3 (37 cases: in band 2, 9 clues of M give 9 empty-cell cases, plus 2 smaller-digit cases at r5c8 and r6c5, i.e. 11 cases; in band 3, 13 clues give 13 empty-cell cases, plus the other 13 smaller-digit cases, i.e. 26 cases)
If band 1 is M's band 1, its solution must be one of 24 band fillings (e.g. 123456789/456789231/789231564).
For these 24 bands, all 24 x 35386368 = 849272832 band 2 fillings (and the band 3 fillings when needed) were checked: no extended puzzle has a unique solution.

5) Checks
Two independent programs (different solvers and enumerations) give the same numbers of tests in every case and no unique puzzle; both find Mauricio's puzzle itself when its own digits are imposed.

If this is confirmed, MIN25 in coloin's MinMaxExercise table could get its "***".

Computations were done with the help of Claude (AI).

JPF

[marek stefanik]

I did my own search on various grid sizes in January and I also found Mauricio's puzzle to be the smallest.

My search goes cell by cell and it keeps the ED fillings which are resolvable with the lexicographically minimal givens and can be completed into a full grid.

The top 3 rows (2 for box height of 2) have 1 ED filling that the search starts from. It seems that the top band always follows the pattern of givens and only has 1 ED filling but I haven't proven that.

The search could be improved. The most valid fillings at once are usually in the second band where most columns are still empty. Imagine the point where r5c1 is getting filled. Firstly, it will always be resolvable since the added cell will be a single in the row, so I don't have to check. Secondly, c12 aren't distinguished yet, so the search tries either column as c1, but since r5c12 can both be empty, the branches then converge. This causes exponential blow-up wrt. the box width and it's the reason why I can't check one of the 10x10s.

The search gets way tougher for larger grid sizes, though. It found Mauricio's puzzle in about 8 seconds, but finding the 12x12 below took almost an hour.

Code: Select all

+-------+-------+-------+-------+
| . . . | . . . | . . . | . . . |
| . . . | . . . | . . . | . . 1 |
| . . . | . . . | . . 1 | . . 2 |
| . . . | . . 1 | . . 2 | . . 3 |
+-------+-------+-------+-------+
| . . 1 | . . 2 | . . 3 | . . 4 |
| . . 2 | . . . | . . 4 | . . 5 |
| . . 3 | . . 4 | . . . | 6 7 . |
| . 4 . | . 3 5 | . 6 7 | . . 8 |
+-------+-------+-------+-------+
| . . 4 | . 2 . | . 3 . | . . . |
| . 1 9 | . 4 3 | . . 6 | 5 A 7 |
| . 2 B | . A 7 | . 5 . | . 3 9 |
| . 3 C | . 5 . | A . 9 | . B . |
+-------+-------+-------+-------+

[JPF]

Hi marek,

Thank you for your independent search, which confirms Mauricio's puzzle as the smallest one.

Here is another method, with a full proof for 12x12 (including the top band).

Results
- 9x9: Mauricio's puzzle is found and proved smallest in 0.12 s (2 cores, Xeon 2.1 GHz):

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.1...3.7..25.6..8..367.4.19
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . 1 |
| . . . | . . 1 | . . 2 |
+-------+-------+-------+
| . . 1 | . . 2 | . . 3 |
| . . 2 | . . . | . 4 . |
| . . 3 | . 4 5 | . . 6 |
+-------+-------+-------+
| . 1 . | . . 3 | . 7 . |
| . 2 5 | . 6 . | . 8 . |
| . 3 6 | 7 . 4 | . 1 9 |
+-------+-------+-------+

- 12x12 (boxes 4 rows x 3 columns): your puzzle is found again, identical, and proved smallest without assuming the top band:

Code: Select all

.......................1........1..2.....1..2..3..1..2..3..4..2.....4..5..3..4...67..4..35.67..8..4.2..3.....19.43..65A7.2B.A7.5..39.3C.5.A.9.B.
+-------+-------+-------+-------+
| . . . | . . . | . . . | . . . |
| . . . | . . . | . . . | . . 1 |
| . . . | . . . | . . 1 | . . 2 |
| . . . | . . 1 | . . 2 | . . 3 |
+-------+-------+-------+-------+
| . . 1 | . . 2 | . . 3 | . . 4 |
| . . 2 | . . . | . . 4 | . . 5 |
| . . 3 | . . 4 | . . . | 6 7 . |
| . 4 . | . 3 5 | . 6 7 | . . 8 |
+-------+-------+-------+-------+
| . . 4 | . 2 . | . 3 . | . . . |
| . 1 9 | . 4 3 | . . 6 | 5 A 7 |
| . 2 B | . A 7 | . 5 . | . 3 9 |
| . 3 C | . 5 . | A . 9 | . B . |
+-------+-------+-------+-------+

Total time about 31 minutes on 2 cores. Starting, as you did, from the top 3 rows, the search takes 32 s.

The method
- The cells are filled in reading order, trying "." first, then the digits allowed by the minlex rule.
- For each beginning of the puzzle, we keep the partial fillings of these cells that are "alone in their interface". The interface is the set of digits in each column, in each box of the current band, and in the current row.
- If another partial filling, compatible with the givens, has the same interface (a "twin"), both can be completed in exactly the same ways, so neither can lead to a unique solution.
- If no filling is alone, this beginning is impossible. At the last cell, "alone" means "unique solution".
- The twin test is exact (a small search), so dead fillings never need to be stored.
- Fillings equivalent by renaming the digits not yet used in the givens, or by a column permutation keeping the givens already placed, are kept once.

12x12 in detail
- Rows 1-2: the same search (about 2 s); 1415 fillings remain, up to symmetry.
- Row 3: inside an empty row the number of fillings explodes, so row 3 is checked as a whole. Each check tries all 287,919,360 third rows, with a twin search for each:
- with your givens (r3c9=1, r3c12=2): 59 fillings remain (624 s);
- with r3c12 empty: none remains (672 s);
- with r3c9 empty, even if r3c10..r3c12 are all given: none remains (541 s).
- Rows 4-12: the search restarts from these 59 fillings and finds your puzzle in 32 s.
(59 is counted up to column permutations and digit renaming only. Your "1 ED filling" probably uses more symmetries.)

Other sizes, found and proved by the same search (minlex form):
- 4x4 (2x2 boxes):

Code: Select all

.......1.1.2.2.3
+-----+-----+
| . . | . . |
| . . | . 1 |
+-----+-----+
| . 1 | . 2 |
| . 2 | . 3 |
+-----+-----+

- 6x6 (2x3 boxes):

Code: Select all

...........1..1..2..2..3.13.24.24.35
+-------+-------+
| . . . | . . . |
| . . . | . . 1 |
+-------+-------+
| . . 1 | . . 2 |
| . . 2 | . . 3 |
+-------+-------+
| . 1 3 | . 2 4 |
| . 2 4 | . 3 5 |
+-------+-------+

- 6x6 (3x2 boxes):

Code: Select all

...........1...1.2.1.2.3.2.3.4.3.4.5
+-----+-----+-----+
| . . | . . | . . |
| . . | . . | . 1 |
| . . | . 1 | . 2 |
+-----+-----+-----+
| . 1 | . 2 | . 3 |
| . 2 | . 3 | . 4 |
| . 3 | . 4 | . 5 |
+-----+-----+-----+

- 8x8 (2x4 boxes):

Code: Select all

...............1...1...2...2...3..13..24..24..35.135.246.246.357
+---------+---------+
| . . . . | . . . . |
| . . . . | . . . 1 |
+---------+---------+
| . . . 1 | . . . 2 |
| . . . 2 | . . . 3 |
+---------+---------+
| . . 1 3 | . . 2 4 |
| . . 2 4 | . . 3 5 |
+---------+---------+
| . 1 3 5 | . 2 4 6 |
| . 2 4 6 | . 3 5 7 |
+---------+---------+

- 8x8 (4x2 boxes):

Code: Select all

...............1.....1.2...1.2.3.1.2.3.4.2...4.5.3.4.5.6.47...2.
+-----+-----+-----+-----+
| . . | . . | . . | . . |
| . . | . . | . . | . 1 |
| . . | . . | . 1 | . 2 |
| . . | . 1 | . 2 | . 3 |
+-----+-----+-----+-----+
| . 1 | . 2 | . 3 | . 4 |
| . 2 | . . | . 4 | . 5 |
| . 3 | . 4 | . 5 | . 6 |
| . 4 | 7 . | . . | 2 . |
+-----+-----+-----+-----+

- 9x9: (3x3 boxes), 0.12 s:

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.1...3.7..25.6..8..367.4.19
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . 1 |
| . . . | . . 1 | . . 2 |
+-------+-------+-------+
| . . 1 | . . 2 | . . 3 |
| . . 2 | . . . | . 4 . |
| . . 3 | . 4 5 | . . 6 |
+-------+-------+-------+
| . 1 . | . . 3 | . 7 . |
| . 2 5 | . 6 . | . 8 . |
| . 3 6 | 7 . 4 | . 1 9 |
+-------+-------+-------+

- 10x10 (2x5 boxes), 100 s:

Code: Select all

...................1....1....2....2....3...13...24...24...35..135..246..246..357.1357.2468.2468.3579
+-----------+-----------+
| . . . . . | . . . . . |
| . . . . . | . . . . 1 |
+-----------+-----------+
| . . . . 1 | . . . . 2 |
| . . . . 2 | . . . . 3 |
+-----------+-----------+
| . . . 1 3 | . . . 2 4 |
| . . . 2 4 | . . . 3 5 |
+-----------+-----------+
| . . 1 3 5 | . . 2 4 6 |
| . . 2 4 6 | . . 3 5 7 |
+-----------+-----------+
| . 1 3 5 7 | . 2 4 6 8 |
| . 2 4 6 8 | . 3 5 7 9 |
+-----------+-----------+

- 10x10 (5x2 boxes), 91 s:

Code: Select all

...................1.......1.2.....1.2.3...1.2.3.4.1.2.3.4.5.2...4.5.6.3.4.5.6.7.4.516.728.59.......
+-----+-----+-----+-----+-----+
| . . | . . | . . | . . | . . |
| . . | . . | . . | . . | . 1 |
| . . | . . | . . | . 1 | . 2 |
| . . | . . | . 1 | . 2 | . 3 |
| . . | . 1 | . 2 | . 3 | . 4 |
+-----+-----+-----+-----+-----+
| . 1 | . 2 | . 3 | . 4 | . 5 |
| . 2 | . . | . 4 | . 5 | . 6 |
| . 3 | . 4 | . 5 | . 6 | . 7 |
| . 4 | . 5 | 1 6 | . 7 | 2 8 |
| . 5 | 9 . | . . | . . | . . |
+-----+-----+-----+-----+-----+

- 12x12 (4x3 boxes):

Code: Select all

.......................1........1..2.....1..2..3..1..2..3..4..2.....4..5..3..4...67..4..35.67..8..4.2..3.....19.43..65A7.2B.A7.5..39.3C.5.A.9.B.
+-------+-------+-------+-------+
| . . . | . . . | . . . | . . . |
| . . . | . . . | . . . | . . 1 |
| . . . | . . . | . . 1 | . . 2 |
| . . . | . . 1 | . . 2 | . . 3 |
+-------+-------+-------+-------+
| . . 1 | . . 2 | . . 3 | . . 4 |
| . . 2 | . . . | . . 4 | . . 5 |
| . . 3 | . . 4 | . . . | 6 7 . |
| . 4 . | . 3 5 | . 6 7 | . . 8 |
+-------+-------+-------+-------+
| . . 4 | . 2 . | . 3 . | . . . |
| . 1 9 | . 4 3 | . . 6 | 5 A 7 |
| . 2 B | . A 7 | . 5 . | . 3 9 |
| . 3 C | . 5 . | A . 9 | . B . |
+-------+-------+-------+-------+

With 2-row boxes (2x2, 2x3, 2x4, 2x5) the smallest puzzle is a regular staircase. With 2-column boxes (3x2, 4x2, 5x2) the first band is a staircase too, but the next bands are less regular.

Checks
- 4x4: same result as a brute force search over all 288 grids.
- 6x6 and 8x8: the same smallest puzzles from two different programs (one counts the partial fillings by interface, the other searches for twins).
- Each puzzle above has a unique solution, checked with an independent solver.

marek, it would be interesting to compare with your January results for these sizes.

Computations were done with the help of Claude (AI).

JPF

[marek stefanik]

I can't check the 10x10 with horizontal boxes, since it would take a very long time, but I get the same results for all the others.

I was surprised that you found 59 r123 fillings, since I believed I had proven that there's only 1, but I've realised that I'd done so only for 9x9.

We need to prove that latin rectangles follow the triangular pattern with 1 ED filling (where each digit has 1 rising diagonal) and then we can say that the first bands of sudokus have 1 ED filling also, since the boxes provide no extra value over the columns and there is only one way to partition the columns into boxes. This last part is what breaks with fewer rows.

It seems that it shouldn't be that hard to prove by induction on the number of rows, I'll look into it.

[JPF]

Hi Marek,

Following your post about proving the 1-ED-filling property by induction, here are some results. For bands of height 3 the property is now proven, for latin rectangles and for sudoku bands of any box width.

1. Boxes and twins. You are right that boxes add nothing for twins: in a complete band, a box is valid iff the column sets of its columns are disjoint, and that depends only on the column sets. But boxes do change which fillings are allowed, so the pattern is not the latin one. For 3 rows:

Code: Select all

latin rectangle sudoku band, boxes 3 x w (n = 3w)
......... .........
........1 ........1
.......12 .....1..2 (here w = 3)


In general the third row is 2w−1 dots, then 1, then w−1 dots, then 2. This matches our computed 6x6 (3x2), 9x9 and 12x12 (3x4) results.

2. Theorem (k = 3). For a sudoku band of 3 rows with boxes 3 x w, the pattern above is the minlex-smallest alive one. Its filling is unique up to relabelling the digits and permuting the clue-free columns inside each box. The same holds for 3 x n latin rectangles, with the clues at n−1 and n and the clue-free columns permuted freely.

Rows 1 and 2. If row 2 has no clue, swapping rows 1 and 2 everywhere gives a twin. So the smallest candidate for row 2 is a single 1 at column n. With it, rows 1-2 of an alive filling form a single cycle: otherwise, swapping the two rows on a cycle that avoids the clue gives a twin. That this configuration is achievable follows from the cyclic construction below. The two 1s of the pattern are the same digit a, as both are the same character in the minlex string.

The digraph criterion. Assume rows 1 and 2 form a single cycle, with the only clue in those rows being a in row 2, column n. The free columns are those with no row-3 clue. For distinct free columns c and d, draw an arc c → d if the current row-3 digit of d occurs in row 1 or 2 of c and is available for reassignment. The digit a in row 2, column n, is fixed.

A directed cycle gives a twin by rotating the row-3 digits along it. Each digit then occurs in exactly two of the pairs left for rows 1 and 2. These pairs form cycles on the digits, so orient each cycle to assign one digit per row in each column, keeping a in row 2, column n.
Conversely, any twin that changes row 3 permutes its digits along directed cycles. If row 3 stays fixed, the clue fixes the orientation of the original cycle of rows 1 and 2.
Thus the filling is alive exactly when the digraph is acyclic.

Lower bound. With ‘.’ before digits, a third row minlex-smaller than the pattern either has all its clues after column n−w, or has the 1 at n−w and no other clue. A clue between n−w and n would make it larger, and at column n the smallest possible digit is already 2, since 1 is in the same row.

Out-degree argument. With no row-3 clue, with the sole row-3 clue equal to a, or with the sole row-3 clue in column n, every free column has an outgoing arc. Away from column n, at most one of the two candidate digits is unavailable. If column n is free, only its protected digit a is unavailable there. Hence the digraph contains a directed cycle, and a twin. This covers the latin case and the sudoku case “only the 1 at n−w”.
All row-3 clues in the last box (sudoku). We may assume the whole row 3 of that box is given. Each digit lies in three different boxes, in three different rows. So for each column of boxes 1-2, its row-3 digit appears exactly once in rows 1-2 of boxes 1-2. Every vertex then has an incoming arc, hence a directed cycle and a twin.

Why the filling is cyclic. Write the pairs in cycle order as (s_i, s_{i+1}) in column g_i, with g_n = n and s_1 = a. The two fixed row-3 digits are a and r3c_n.

A sink must contain both in its pair. Since g_n is excluded, the first sink is g_1, and r3c_n = s_2.
After deleting g_1..g_k, the unavailable target digits are s_1..s_{k+1} together with the row-3 digit of g_k. No remaining pair lies entirely in that prefix, and only g_{k+1} can join it to the one additional digit, since g_n is excluded. So if a vertex remains, the next sink is g_{k+1} and the row-3 digit of g_k is s_{k+2}.
There are n−2 vertices, so the other clue column is g_{n−1}. The last unused digit completes row 3, giving s_{i+2} in every column g_i, with indices taken modulo n.
Conversely, with row 3 given by s_{i+2} and the clues in g_{n−1}, g_n, every arc goes to a smaller index. The cyclic filling is therefore alive.

Boxes. In the cyclic filling, a column covers three consecutive digits of the cycle. A box is valid iff these triples partition the cycle, i.e. iff its columns are one residue class of positions mod 3. Column n has position n, and the clue column has position n−1, so it is in another box. The rightmost choice is column 2w = n−w. Conversely, assign the residue classes 0 and 2 to the last and middle boxes, and place g_n and g_{n−1} in their last columns. This realizes the stated pattern. For the latin rectangle, simply place g_{n−1} and g_n in columns n−1 and n.

Remark. The two 1s must be the same digit. Here is an alive, non-cyclic band (boxes of width 2) where they are not:

Code: Select all

154236 ......
465312 .....2
326154 ...1.4


Its minlex third row is ...2.3, larger than ...1.2, so it does not affect the theorem.

3. k ≥ 4. The rotation of row k along a directed cycle still works. Repairing rows 1..k−1 is easy when they contain at most one clue: after the rotation the column/digit graph is (k−1)-regular bipartite, so it splits into k−1 perfect matchings, one per row, and the clue’s row gets the matching that contains its edge. What remains open is the repair when rows 1..k−1 contain several clues, which is the case in the triangular pattern.

Computer check (latin rectangles):

Rows 1..k−1 carry the minimal pattern with its cyclic filling, under every permutation of their clue-free columns. Row k is any compatible row.
In row k, one of the k−1 pattern clues is replaced by ‘.’. The cells to its left follow the pattern, and every cell of row k to its right is given.
For k = 4 (n = 5, 6, 7) and k = 5 (n = 6, 7), each of these 23,240 cases has a twin that changes at most 3 rows.

Two related references:

For k = n, the triangular pattern is Nelder’s critical set of size (n²−n)/2 for the back-circulant latin square.
In that language, twins are latin trades.

with the help of Claude (AI)
JPF

[marek stefanik]

For 3 rows, there is also an intuitive proof, but with a lot of theory behind it.

Hall's theorem (Philip Hall) equates to 'Any row where each subset of cells contains a sufficient number of different digits can be filled.' It implies that any elimination within a row can be done via subsets.

A Latin rectangle can always be completed into a Latin square. This was proven by Marshall Hall using Hall's theorem, by induction on the number of filled rows.
Here is the induction step (simplified): Suppose you have a Latin rectangle with r>0 unfilled rows. In an unfilled row, each cell has r candidates, so each set of k cells has k*r candidates. Since each digit has r candidates, these candidates belong to at least k different digits, which is enough to fill the cells. So, by Hall's theorem, the row has a solution.

The following ideas are important in distinction theory:
With two empty rows, one given is wlog, since we can just swap the rows. So, with r12 empty apart from one given, there is always a solution (if the given doesn't clash with anything in the column). Thus with three empty rows, any solution for r3 allows r12 to be filled. So in order to get a unique solution, r3 must have a unique solution per se. It must be solvable via a sequence of hidden singles (each subset, wlog naked, splits the row into two smaller parts, which must both be unique; so it can be easily proven by induction), which requires at least 2 givens.

Our pattern has the smallest pair of givens possible and there is only one ED way to keep the hidden singles flowing with these givens. This way then leaves r12 with only 1 solution.

But there is a problem if we want to take it further – the givens in r3 can actually break some 3xN rectangles, such as 3x7 with columns restricted to 134, 234, 234, 567, 567, 156, 127.
This is where I gave up in January.

I'll have a look at your proof tomorrow, now it's too late to think.