The New Sudoku Players' Forum

[Moschopulus]

[The case "4 clues: 1" is obviously (also) a theoretical result, but how many others are...]

Here are the four types of size 6 (hope I get this right).

Code: Select all

12.......
.........
.........
2.1......
.........
.........
.12......
.........
.........

12.......
.........
.........
23.......
.........
.........
31.......
.........
.........

123......
.........
.........
231......
.........
.........
.........
.........
.........

12.......
.........
.........
2..1.....
.1.2.....
.........
.........
.........
.........


Then if you think about it for a while, there can't be any more. You can't have more than three different symbols, and you can only have two or three digits in any box.

Red Ed, the numbers are very interesting, thanks. Can you post the different representatives of sizes 8 and 9? (whatever form is easiest)

[gfroyle]

18 of the 17s generated a 16-pseudo-puzzle with 2 completions (I naively expected only two, while everybody else apparantly knew there had to be between four and eighteen). These 16-pseudos are all isomorph.

So you found isomorph 16-clue pseudos with non-isomorph solutions? When are two puzzles isomorph? I'm missing something here.

I think that what was meant is the following: the 16-clue pseudo-puzzle with 2 solutions can be turned into a 17-clue genuine puzzle in 18 different ways (presumably by adding any ONE clue from the 2 missing numbers - hence 9x2 = 18 different ways). This leads to 18 non-isomorphic 17-clue puzzles, but they all have isomorphic completions...

Gordon

[Ocean]

...
Thanks for those puzzles. How do you know these numbers are complete?

( i.e., how do you know there are *exactly* 29 17s in SF. I would bet there aren't any more, but how did you prove it?)

Thank you for challenging/arresting my too categoric formulations!

I have updated the post, including the the sentence "These numbers are 'the best I know so far', and will be updated from time to time." Some numbers are also updated.

The numbers are not proven, and should therefore be regarded as minimum values. They are all counts of actual findings (except the 2^47-1, which is a conjecture, but is easy to prove (oops, another conjecture...)). The numbers are not found by exhaustive search, rather by 'massive random search'. I have quite high confidence in "29 17s in SF", "1 16-pseudo" and "15 17-pseudos" for the SF-grid, since all these numbers converge fast, and reproduce over and over again. I had to increase the number of 18s from 724 to 729 (it seemed to have converged, but was actually slowly groing). The number of 18-pseudos is also growing slowly, while 19s, 20s and 19-pseudos is growing faster.

18 of the 17s generated a 16-pseudo-puzzle with 2 completions (I naively expected only two, while everybody else apparantly knew there had to be between four and eighteen). These 16-pseudos are all isomorph.

So you found isomorph 16-clue pseudos with non-isomorph solutions? When are two puzzles isomorph? I'm missing something here.

I think that what was meant is the following: the 16-clue pseudo-puzzle with 2 solutions can be turned into a 17-clue genuine puzzle in 18 different ways (presumably by adding any ONE clue from the 2 missing numbers - hence 9x2 = 18 different ways). This leads to 18 non-isomorphic 17-clue puzzles, but they all have isomorphic completions...

Gordon

Thanks to Gordon for a better formulation!

1. A short comment on the search method: the program searched for pseudo-puzzles by deleting one clue from known sudokus (trying all possible ways).

2. I knew Gordon had published one 16-pseudo, and expected to find this twice, - but I did not know that its solution (actually both solutions) was the SF-grid, which has 29 known 17s. Therefore it came as a surprise when the 16-clue pseudo-puzzle popped up 18 times, from different 'parent 17s'.

3. When are two puzzles isomorph? Here is 'my' definition:
Two grids (or subgrids) are said to be isomorphic, equivalent, or belong to the same class, iff one can be transformed to the other by (a combination of) the 'usual equivalence transformations': permutation of rows within bands, permutation of columns within bands, permutation of bands, transposition (swapping rows and columns), and renumbering the clues.


You are of course right when indicating that isomorphic 16-clue pseudos can not have non-isomorphic solutions! Here are a few conjectures (and more can be formulated. Proofs or rejections are welcome.)

Conjecture: Two isomorphic sudokus have isomorphic solution grids.

Conjecture: The solution set of two isomorphic pseudo-puzzles is a set of pairwise isomorphic grids.

[Edit:] False Conjecture: Two sudokus are nonisomorph if they are different from each other and have identical grid solution.
(This is not the case for puzzles with more than one solution.)

[Red Ed]

Conjecture: Two isomorphic sudokus have isomorphic solution grids.

True. For sudokus S,S' let g be the isomorphism: g*S = S'. Then g*Soln(S) contains g*S = S' and so must be equal to Soln(S').

Conjecture: The solution set of two isomorphic pseudo-puzzles is a set of pairwise isomorphic grids.

True for the same reasons as above (in fact this applies to any pair of isomorphic sudokus, no matter how many solutions they have). In other words: the grid G solves (i.e. contains) S iff g*G solves g*S.

Conjecture: Two sudokus are nonisomorph iff they are different from each other and have identical grid solution.

I think you mean "if", not "iff" ... but still this is False. Pick a grid G that's fixed by some non-trivial symmetry op (with relabelling as necessary), h. Let S be a puzzle in G that's not fixed by h. Then S and h*S are different sudokus which are isomorphic and have the same solution G = h*G. (For concreteness, h could be transposition + a particular relabelling and S could be any puzzle whose clue positions are not transpo-invariant.)

Here's a conjecture of my own. Grateful for any ideas ...
Conjecture: the dual of any minimal unavoidable set has exactly two solutions, and these are isomorphic.
By the "dual" of a set of clues, C, (in this case, of a minimal unavoidable set), I mean the puzzle that is: find a pattern of cells/values that satisfies the same 27 row/col/box membership constraints as C.
[Update: this is False, as demonstrated by the SF grid]

[gfroyle]

Here's a conjecture of my own. Grateful for any ideas ...
Conjecture: the dual of any minimal unavoidable set has exactly two solutions, and these are isomorphic.

Do you really mean this?

As written, it is clearly false - if you take the simplest unavoidable, just a 4-cell pattern such as

Code: Select all

1..2
.....
2..1


then the two solutions of the dual problem are the original grid and the one obtained by exchanging the 1s and 2s in the pattern, which will almost certainly be non-isomorphic.


If you want a specific example, then our old friend SF

Code: Select all

6 3 9  2 4 1  7 8 5 
2 8 4  7 6 5  1 9 3 
5 1 7  9 8 3  6 2 4 

1 2 3  8 5 7  9 4 6 
7 9 6  4 3 2  8 5 1 
4 5 8  6 1 9  2 3 7 

3 4 2  1 7 8  5 6 9 
8 6 1  5 9 4  3 7 2 
9 7 5  3 2 6  4 1 8


with unavoidable with corners at r1c2 and r3c6 is not isomorphic to

Code: Select all

6 1 9  2 4 3  7 8 5 
2 8 4  7 6 5  1 9 3 
5 3 7  9 8 1  6 2 4 

1 2 3  8 5 7  9 4 6 
7 9 6  4 3 2  8 5 1 
4 5 8  6 1 9  2 3 7 

3 4 2  1 7 8  5 6 9 
8 6 1  5 9 4  3 7 2 
9 7 5  3 2 6  4 1 8


In fact, I would think that pretty much the ONLY unavoidables with this property would be the 18-cell ones consisting of all the cells of two colours.

Cheers

Gordon

[Red Ed]

As written, it is clearly false - ...

Oops, silly me, my definition of dual was phrased badly. As corrected above, it should be:
The dual of a set of clues, C, is the puzzle that is: find a pattern of cells/values that satisfies the same 27 row/col/box membership constraints as C.

So the dual of your four-cell pattern ...

Code: Select all

  1..|2..|...
  ...|...|...
  2..|1..|...
  ---+---+---
  ...|...|...
  ...|...|...
  ...|...|...
  ---+---+---
  ...|...|...
  ...|...|...
  ...|...|...

... is the puzzle: find a pattern of cells/values that satisfies:

• B1,B2 each contains {1,2}
• R1,R3 each contains {1,2}
• C1,C4 each contains {1,2}
• all other Bx,Rx,Cx are empty

... which in the example above results in pattern you first thought of, and the same but with 1/2 interchanged.

Apologies for bad explanation first time round. But the conjecture still stands:
Conjecture: the dual of any minimal unavoidable set has exactly two solutions, and these are isomorphic.
Any ideas? [Update: this is False, as demonstrated by the SF grid]

[Moschopulus]

If I understand the conjecture (and I probably don't) then it is equivalent to the following:

Any minimal unavoidable set has just one permutation of the cells that results in a valid (partial) grid.

If there were more than one permutation then the dual would have more than two completions. Please let me know if I have not understood, which is quite likely.

Example:

Code: Select all

1 2 3 . . . . . .
. . . . . . . . .
. . . . . . . . .
2 3 1 . . . . . .
. . . . . . . . .


is minimal and there is only one permutation that results in a valid partial grid, namely interchanging the two rows

Code: Select all

2 3 1 . . . . . .
. . . . . . . . .
. . . . . . . . .
1 2 3 . . . . . .
. . . . . . . . .


But this unavoidable

Code: Select all

1 2 3 . . . . . .
. . . . . . . . .
. . . . . . . . .
2 3 1 . . . . . .
. . . . . . . . .
. . . . . . . . .
3 1 2 . . . . . .
. . . . . . . . .
. . . . . . . . .


is not minimal, and has two permutations that give valid grids:

Code: Select all

2 3 1 . . . . . .   3 1 2 . . . . . .
. . . . . . . . .    . . . . . . . . .
. . . . . . . . .   . . . . . . . . .
3 1 2 . . . . . .   1 2 3 . . . . . .
. . . . . . . . .   . . . . . . . . .
. . . . . . . . .   . . . . . . . . .
1 2 3 . . . . . .   2 1 3 . . . . . .
. . . . . . . . .   . . . . . . . . .
. . . . . . . . .   . . . . . . . . .


[Red Ed]

If I understand the conjecture (and I probably don't) then it is equivalent to the following:

Any minimal unavoidable set has just one permutation of the cells that results in a valid (partial) grid.

Your examples capture the notion I'm getting at, but the words above don't. I often think of minimal unavoidables in terms of their row, col and box memberships (e.g. B1 contains {1,2,3} etc. in your first example). The fact that there is more than just one -- I am conjecturing always two -- ways of meeting these constraints is precisely what makes these sets unavoidable.

Further, I'm conjecturing that any two realisations of those row, col and box constraints are isomorphic. This isn't true for general clue-sets, but all the minimal unavoidables I've checked so far do exhibit this property.

I'll post some verification (- or not!) checks in the next few days: with a growing list of 130000+ representative minimal unavoidables, I've got plenty of test cases ...

PS: I've got another, somewhat half-hearted, conjecture:
Conjecture: a minimal unavoidable is never also a valid sudoku puzzle.
The closest I've come to disproving this is with a size 37 minimal unavoidable that is contained in just 3 sudoku grids. However, I have no intuition about why this conjecture should be true, or not.
[Update: this has been shown to be False now. Told you it was a half-hearted conjecture!]

[Ocean]

Conjecture: Two isomorphic sudokus have isomorphic solution grids.

True. For sudokus S,S' let g be the isomorphism: g*S = S'. Then g*Soln(S) contains g*S = S' and so must be equal to Soln(S').

Conjecture: The solution set of two isomorphic pseudo-puzzles is a set of pairwise isomorphic grids.

True for the same reasons as above (in fact this applies to any pair of isomorphic sudokus, no matter how many solutions they have). In other words: the grid G solves (i.e. contains) S iff g*G solves g*S.

Thank you for supplying the proofs!

And also for rejecting the third conjecture! I agree with you completely, the third conjecture was wrong. But still I can not quite leave the idea behind it. Here is a new version, in two parts, plus a separate conjecture about the SF grid.

Conjecture 1: If a grid G is fixed by some symmetry op h, any sudoku S that has G as its solution grid is either fixed by the same symmmetry op h, or there exists a different sudoku S'=h*S isomorphic to S, which also has G as its solution grid.

Conjecture 2: If a grid G is not fixed by any symmetry op h, then two sudokus that both have G as solution grid are nonisomorph iff they are different from each other.

Conjecture 3: The SF grid is not fixed by any symmetry op h.

Here's a conjecture of my own. Grateful for any ideas ...
Conjecture: the dual of any minimal unavoidable set has exactly two solutions, and these are isomorphic.
By the "dual" of a set of clues, C, (in this case, of a minimal unavoidable set), I mean the puzzle that is: find a pattern of cells/values that satisfies the same 27 row/col/box membership constraints as C.

To begin with, I have only one basic question:

Is there a formal definition of "minimal unavoidable set" (in the sudoku sense)?
(Would be pleased if somebody could spell it out, or point at a source.)

[Red Ed]

Conjecture 1: If a grid G is fixed by some symmetry op h, any sudoku S that has G as its solution grid is either fixed by the same symmmetry op h, or there exists a different sudoku S'=h*S isomorphic to S, which also has G as its solution grid.

True, but IMHO not worded very well. S' = h*S always has the same solution grid as S (since h fixes G). Given that, the rest of the conjecture just says that either S' equals S or it doesn't!

Conjecture 2: If a grid G is not fixed by any symmetry op h, then two sudokus that both have G as solution grid are nonisomorph iff they are different from each other.

True. Let S' = h*S != S be isomorphic sudoku puzzles with one solution each: G = Soln(S), G' = Soln(S'). h*G contains h*S = S', so it must be the case that G' = h*G != G. So no two (distinct) sudokus of G can possibly be isomorphic.

Conjecture 3: The SF grid is not fixed by any symmetry op h.

This is easily checked by grinding through the symmetry group, which I'm too lazy to do (sorry).

Is there a formal definition of "minimal unavoidable set" (in the sudoku sense)?

An unavoidable set is a collection of cells in a sudoku grid such that any valid puzzle for that grid must contain at least one of those cells. A minimal unavoidable is one that does not strictly contain any other unavoidables.

For an alternative definition, let Z be a particular collection of (cell,value) pairs, i.e. something you think might be an unavoidable set. Let Constraints(Z) be the 27 statements of the form "box B contains values {...}", "row R contains values {...}" and "column C contains values {...}", with the "..." parts depending on Z. By definition Z satisfies Constraints(Z); iff any other Z' also satisfy Constraints(Z), and Z itself can be embedded in a valid sudoku grid, then Z (and its friends Z') are unavoidables. Z is then minimal iff all none of the Z' (including Z itself) satisfying Constraints(Z) have any (cell,value) pairs in common. The point of this alternative definition is just to formalise the notion that unavoidables are subsets of grids that you can change (carefully) without affecting the validity of the parent grid.

This is a minimal unavoidable:

Code: Select all

1..|2..|...
...|...|...
---+---+---
2..|1..|...
...|...|...
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...

because the only way of matching the corresponding constraints is (reading left to right, then top to bottom): 1,2,2,1 or 2,1,1,2. That's >1 ways of meeting the constraints (therefore unavoidable) and no cell,value pairs in common (therefore minimal).

[Moschopulus]

Conjecture 3: The SF grid is not fixed by any symmetry op h.

True. Now you know that your puzzles can't be equivalent....

To begin with, I have only one basic question:

Is there a formal definition of "minimal unavoidable set" (in the sudoku sense)?
(Would be pleased if somebody could spell it out, or point at a source.)

I'll give another definition. An unavoidable set in a completed grid is a set of cells such that some permutation of those cells results in another valid completed grid.

A minimal unavoidable set is an unavoidable set with the property that no subset is an unavoidable set, except itself.

[Ocean]

...

Conjecture 2: If a grid G is not fixed by any symmetry op h, then two sudokus that both have G as solution grid are nonisomorph iff they are different from each other.

True. Let S' = h*S != S be isomorphic sudoku puzzles with one solution each: G = Soln(S), G' = Soln(S'). h*G contains h*S = S', so it must be the case that G' = h*G != G. So no two (distinct) sudokus of G can possibly be isomorphic.

...

Conjecture 3: The SF grid is not fixed by any symmetry op h.

True. Now you know that your puzzles can't be equivalent....

Thanks again for the proofs!

Is there a formal definition of "minimal unavoidable set" (in the sudoku sense)?

An unavoidable set is a collection of cells in a sudoku grid such that any valid puzzle for that grid must contain at least one of those cells. A minimal unavoidable is one that does not strictly contain any other unavoidables.

For an alternative definition, ...

and for the definitions of minimal unavodable sets.


I think understand the idea for smaller sets at least. To see if I got the general idea right in general, I jump on a bigger one.
Using

"... any pseudo puzzle on n clues must have its solutions differing by a unique minimal unavoidable set, from which you can borrow any clue to make a uniquely-solvable puzzle on n+1 clues."

Taking the pseudo-puzzle:
502008471040710203107000000300104607070000105010057300601002730720030014493871500
and comparing its two solution grids, we can calcultate the unique minimal unavoidable set (and its dual) as:

060390000908006050030425986059080020804263090206900048080540009005609800000000062
030960000809005060060243859085020090206389040904600082050490008008506900000000026

Code: Select all

The Unavoidable set U:
 *-----------*
 |.6.|39.|...|
 |9.8|..6|.5.|
 |.3.|425|986|
 |---+---+---|
 |.59|.8.|.2.|
 |8.4|263|.9.|
 |2.6|9..|.48|
 |---+---+---|
 |.8.|54.|..9|
 |..5|6.9|8..|
 |...|...|.62|
 *-----------*

Its Dual D:
 *-----------*
 |.3.|96.|...|
 |8.9|..5|.6.|
 |.6.|243|859|
 |---+---+---|
 |.85|.2.|.9.|
 |2.6|389|.4.|
 |9.4|6..|.82|
 |---+---+---|
 |.5.|49.|..8|
 |..8|5.6|9..|
 |...|...|.26|
 *-----------*

Further:

Gordon's list of unavailable sets for the SF-grid ('sf-big.txt') contains sets of sizes from 4 to 45. I wondered if these were minimal. Checking the last one on the list, gives: (First the solution grid, then an unavoidable set of size 45, then the difference).

639241785284765193517983624123857946796432851458619237342178569861594372975326418 (SF)
009241005200005090010900620120050906096432850008019037000108560061590372900306018 (U45)
630000780084760103507083004003807040700000001450600200342070009800004000075020400 (36-P2)

[Edit] Also: (Second solution grid to 36-P2, and the dual unavoidable set)
631459782984762153527183964213897645768245391459631278342576819896314527175928436 (GRID2)
001459002900002050020100960210090605068245390009031078000506810096310527100908036 (DUAL)

[Edit]
The difference between the unavoidable set (U45) and its solution grid is a 36-clues pseudo-puzzle with two solutions (and 45 clue completions.) The two solution grids should differ by a unique minimal unavoidable set, and in fact it is equivalent to the 45-set (or its dual). Therefore, if I have got this right, this unavoidable set is minimal. It is also a proper sudoku (having one solution). Hence...

PS: I've got another, somewhat half-hearted, conjecture:
Conjecture: a minimal unavoidable is never also a valid sudoku puzzle.
The closest I've come to disproving this is with a size 37 minimal unavoidable that is contained in just 3 sudoku grids. However, I have no intuition about why this conjecture should be true, or not.

False by counterexample. This minimal unavoidable set is also a valid sudoku:
009241005200005090010900620120050906096432850008019037000108560061590372900306018

[Red Ed]

Gordon's list of unavailable sets for the SF-grid ('sf-big.txt') contains sets of sizes from 4 to 45. I wondered if these were minimal. Checking the last one on the list, gives:
...
The difference between the unavoidable set and its solution grid is a pseudo-puzzle with two solutions. Therefore, if I have got this right, this unavoidable set is minimal.

That 45-set isn't minimal, so doesn't disprove the conjecture. EDIT: oops, yes it is minimal, and your example does disprove the conjecture. Well done!

However, this 49-set is minimal and also has only one parent grid:

Code: Select all

.42|53.|...
39.|7.1|46.
.7.|4.8|...
---+---+---
563|8..|.4.
8.4|.59|..6
.29|6..|853
---+---+---
...|1.3|6.4
986|24.|137
4.1|967|528


So, in the end, you were right. That particular conjecture is False. Good: one down, one to go.

btw, the 49-set above was found by examining grids that are @-invariant, where @ is some symmetry op. If my first conjecture about solutions of duals being isomorphic is correct, then it was necessary to restrict the search in this way.

(edited to show a 49-set rather than the original smaller set)

[Ocean]

That 45-set isn't minimal, so doesn't disprove the conjecture.

OK, thanks. If the 45-set
009241005200005090010900620120050906096432850008019037000108560061590372900306018
is not minimal, then there must be a flaw in my argument (sorry!) - and it should be possible to find a subset of the 45-set which is a minimal unavoidable set. (Is that correct?) (Will update the previous post when/if I get it right...).

PS -
So far I have only found a missing sentence in the argument (but not the crucial flaw):
"The difference between the unavoidable set and its solution grid is a 36-clues pseudo-puzzle with two solutions (and 45 clue completions.) The two solution grids should differ by a unique minimal unavoidable set, and in fact it is equivalent to the 45-set (or its dual). Therefore, if I have got this right, this unavoidable set is minimal."

[Red Ed]

If the 45-set
009241005200005090010900620120050906096432850008019037000108560061590372900306018
is not minimal, then there must be a flaw in my argument

Oops, my fault: finger trouble converting that 45 to the stupid format used by my program. You're quite right, that 45-set is minimal and it does disprove my half-hearted conjecture. Well done!

btw, what's this 'sf-big.txt' you mentioned? Is it generally available anywhere?