The New Sudoku Players' Forum

[Red Ed]

on looking manually,,,this may be another unavoidable set in grid2

Code: Select all

36  (2) ..8..3.6....1..8...9368.1.4...8.74....5341.8...4..5.16..7526.4...2.3..7..897.4.3.

Yeah, it is. But it's not minimal, so it's not interesting.

[eleven]

Here is a puzzle with 2 solutions.

Code: Select all

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


The 2 solutions A and B are :

Code: Select all

179258364632749851845316927726183495958462173314597682563974218281635749497821536
146275389798143652352896417521689734973524168864317925415968273689732541237451896

They differ on 60 cells.

Cool, i like that (sorry to break the discussion). So you can choose any of the 60 cells, put in the number of the one or other solution and get 2 equivalent unique sudokus. From the solvers point of view that means, if you can solve the one, you can solve the other the same way.
I tried e.g. to put in 5 in r5c2 and got an interesting sudoku. Its amazing that putting in 7 makes it the same.

[Added:] This also is a good solver test - most solvers do the puzzles stupidly from top to bottom, following there technique hierarchy.
Put 3, then 5 into r6c4 and look, how different the solution paths are.

[RW]

How many unavoidable sets are there in the 48 empty cells?

That's not quite what you mean. There are NO unavoidable sets in the empty cells. But there ARE unavoidable sets confined to those positions in either of the original solution grids.

Actually, that was what I meant, though perhaps unavoidable set isn't the right term when speaking about empty cells...

The puzzle with 48 empty cells has 92 solutions. This means that if we examine the unavoidable sets in all 92 solutions, we should find a maximum of 91 different unavoidable sets (that all appear in at least two grids in two different permutations) that can be placed in the 48 empty cells without causing a contradiction with the 33 given clues.

91 is still such a small number that it should be possible to list. I just wonder if there is some faster way to find these than examining all possible solutions...

If we had a list of these unavoidable sets and a list that shows which unavoidable sets (and which permutations of these sets) appear in which solution, then it should be possible to determine the shortest path between the two grids.

RW

[coloin]

Thanks Red Ed, my understanding has now been updated. In some ways it confirms that a clue can only be inserted if it doesnt appear in any of the minimal and non-minimal unavoidable sets remaining. In solving the puzzle with the other 2 [5] clues the 9 would then become superfluous.


OT

Is it worth updating the pseudo-puzzle / megaclue thread which outlines the extent of the unavoidables in every grid. [I suspect most people are completely oblivious]

Can an individual puzzles properties be pinpointed directly to the unavoidable sets that each individual clue or group of clues is responsible in "covering" ? I can see a few [trivial] clue patterns [4-clue][naked single] where a clue may be inserted. Any puzzle with an isomorphic example of this pattern will have this insertion.


In persuit of RW's line - we perhaps would need to find our most distant 2 grids with a max of 33 common clues [mc-grid and a.n.-othergrid] with the least [or most] ? <92 sol


Are ther really only 91 different minimal unavoidable sets with a different position pattern ? I am of the view that there will be at least 91

[Addlan]

Here is a puzzle with 2 solutions.

Code: Select all

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


The 2 solutions A and B are :

Code: Select all

179258364632749851845316927726183495958462173314597682563974218281635749497821536
146275389798143652352896417521689734973524168864317925415968273689732541237451896

They differ on 60 cells.

This is an interesting phenomenon. And we may get more from it: the length of the path between these two isomorph grids in this case is 1 clue. However, if they are aligned properly at first, the length is 0, i.e. they are equivalent. If they were aligned in other ways, the length of the path could vary a lot. The key is how to find an optimized path from one grid to another.

[RW]

Are ther really only 91 different minimal unavoidable sets with a different position pattern ? I am of the view that there will be at least 91

Looking at those 48 cells in any solution out of the 92 possible solutions, each unavoidable set leads to at least one other possible solution. As a result N unavoidable sets will lead to a minimum of N+1 solutions. The puzzle has 92 solutions, therefore N<92.

RW

[Addlan]

Looking at those 48 cells in any solution out of the 92 possible solutions, each unavoidable set leads to at least one other possible solution. RW

Is it not that one unavoidable set leads to at least two solutions? If that is, N<=92/2=46

[RW]

Looking at those 48 cells in any solution out of the 92 possible solutions, each unavoidable set leads to at least one other possible solution. RW

Is it not that one unavoidable set leads to at least two solutions? If that is, N<=92/2=46

One unavoidable set leads to at least two solutions, yes. But each unavoidable after that leads to at least one more solution, not two more. For example two unavoidable sets with one common cell gives three solutions.

A new unavoidable set with no cells in common with previous sets doubles the amount of solutions. So two unavoidable sets with one cell in common and a third disjoint set gives six solutions.

RW

[Red Ed]

Why didn't anyone just count the minimal unavoidables? There are 422, contrary to RW's claims.

An isolated sub-puzzle

Here's a nice small-scale counterexample. Consider the following isolated sub-puzzle:

Code: Select all

 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   89  89  | .   .   .   | .   .   .
-------------+-------------+------------
 .   .   .   | .   .   47  | .   .   47
 .   .   47  | .   .   47  | .   .   .
 .   79  479 | .   .   .   | .   .   47
-------------+-------------+------------
 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   78  78  | .   .   .   | .   .   .

This contains four minimal unavoidable sets, which I'll call "a", "A", "x" and "X".
"a" and "A" are dual min-unavs on digits 4 and 7; "x" and "X" are duals on digits 7, 8 and 9.

Solutions to the ISP

There are three solutions to this ISP.

The first contains min-unavs "a" and "x":

Code: Select all

 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   8x  9x  | .   .   .   | .   .   .
-------------+-------------+------------
 .   .   .   | .   .   4a  | .   .   7a
 .   .   4a  | .   .   7a  | .   .   .
 .   9x  7ax | .   .   .   | .   .   4a
-------------+-------------+------------
 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   7x  8x  | .   .   .   | .   .   .

Permuting "a" to "A" gives the second solution, but kills "x" ...

Code: Select all

 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   8   9   | .   .   .   | .   .   .
-------------+-------------+------------
 .   .   .   | .   .   7A  | .   .   4A
 .   .   7A  | .   .   4A  | .   .   .
 .   9   4A  | .   .   .   | .   .   7A
-------------+-------------+------------
 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   7   8   | .   .   .   | .   .   .

... whereas permuting "x" to "X" gives the third solution but kills "a":

Code: Select all

 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   9X  8X  | .   .   .   | .   .   .
-------------+-------------+------------
 .   .   .   | .   .   4   | .   .   7
 .   .   4   | .   .   7   | .   .   .
 .   7X  9X  | .   .   .   | .   .   4
-------------+-------------+------------
 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   8X  7X  | .   .   .   | .   .   .

Conclusion

It's possible to have more minimal unavoidables than solutions.

[RW]

Why didn't anyone just count the minimal unavoidables? There are 422, contrary to RW's claims.

Here's a nice small-scale counterexample. Consider the following isolated sub-puzzle:

I think we are using terminology differently again... I said there'll be a maximum of 91 unavoidable sets that all appear in at least two grids in two different permutations. Swapping the digits in an unavoidable set doesn't create a new unavoidable set IMO, it's just a different permutation of the same set. So in your counterexample, I'd call "a" and "A" the same set, likewise "x" and "X".

If we consider all minimal sets that have the same digits and occupy the same cells as the same unavoidable set, there shouldn't be more than 91.

422 is quite a big number though... Are you sure you have filtered out all doubles?

RW

[Red Ed]

RW, an unavoidable set consists of one value in each cell of the pattern. It was defined a long time ago and you can't change it now. In my previous post, "a" and "A" are different unavoidables.

Your concept appears to be that of an "ambiguous footprint". From that concept, I suppose a minimal ambiguous footprint (MAF) would be one that contains no smaller ambiguous footprint. If your claims pertain to those then I can't contradict them -- or rather I haven't tried to yet

[Red Ed]

422 is quite a big number though... Are you sure you have filtered out all doubles?

All bar two of the minimal unavoidables had valency 2, i.e. 2-1 = one other permutation with the same footprint. The other two had valency three. Grouping together min-unavs with the same footprint would give at least 210 groups (though how many exactly, I haven't checked).

Note that a permutation of a minimal unavoidable is not necessarily minimal (but of course is still an unavoidable).

[RW]

Sorry for the confusion...

Your concept appears to be that of an "ambiguous footprint". From that concept, I suppose a minimal ambiguous footprint (MAF) would be one that contains no smaller ambiguous footprint. If your claims pertain to those then I can't contradict them -- or rather I haven't tried to yet

Or perhaps we could rather use the more common term "deadly pattern". A minimal deadly pattern would be what we get if we remove all given clues from a minimal unavoidable set, right?

Grouping together min-unavs with the same footprint would give at least 210 groups (though how many exactly, I haven't checked).

If this is true, then there must be some kind of "inner loops", where permutating different unavoidables eventually leads to the same new grid... Have to give it a thought...

Note that a permutation of a minimal unavoidable is not necessarily minimal (but of course is still an unavoidable).

Could you give an example of a minimal unavoidable whose permutation isn't a minimal unavoidable? I suppose this can happen only with unavoidbles that have valency >2... I am not very familiar with the properties of such unavoidables.

RW

[Red Ed]

(For RW)

This trivalent minimal unavoidable ...

Code: Select all

..3..6.8....8..1....813.4.6...7.48..9..583.1...5.91.64..2645.7...7.2..3.5.93.7.4.

... has the following three permutations (of which the first is the identity permutation) ...

Code: Select all

..3..6.8....8..1....813.4.6...7.48..9..583.1...5.91.64..2645.7...7.2..3.5.93.7.4.
..8..3.6....1..8....368.1.4...8.74..5..391.8...9.45.16..5726.4...2.3..7.9.75.4.3.
..8..3.6....1..8....368.1.4...8.74..5..391.8...9.45.16..7526.4...2.3..7.9.57.4.3.

... from which it can be seen that the second and third contain a U4 in these positions ...

Code: Select all

........................................................**................**.....

... and so the second and third are not minimal unavoidables.

[Red Ed]

... minimal unavoidable whose permutation isn't a minimal unavoidable ... can happen only with unavoidables that have valency >2

Yes. I guess you know why, but for the benefit of others I'll explain. Imagine listing all the permutations (that have the same footprint) of a given unavoidable as I did in the previous post. An unavoidable in that list is minimal if & only if for each of its digits d@(r,c) it's the only unavoidable in the list that has d@(r,c).

If all the permuted unavoidables are minimal, I call them strongly minimal. Otherwise, the minimal ones (if any) are only weakly minimal. IIRC, most unavoidables are strongly minimal; only a few of the bigger (18+ cells) unavoidables are weakly minimal.