Red Ed wrote:...

Ocean wrote: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.

...

Moschopulus wrote:Ocean wrote: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!

Red Ed wrote: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

Red Ed wrote:"... 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...

Red Ed wrote: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