The New Sudoku Players' Forum

[Ocean]

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

The 'Sudoku Checker' site (http://www.maths.nuim.ie/staff/gmg/sudoku/checker.html), has a reference link to
"Gordon's ... collection of unavoidable sets for the SF grid: big file [http://www.csse.uwa.edu.au/~gordon/sfb.zip] (240,000 sets, 3 MB), small file [http://www.csse.uwa.edu.au/~gordon/sfs.zip] (20,000 sets, 180 KB)"

[Red Ed]

Ah, well that blows my other conjecture out of the water. There are several minimals in Gordon's sf-big.txt whose duals have >2 solutions, e.g. this one whose dual has 3 solutions:

Code: Select all

639|2.1|78.
28.|.65|1.3
5.7|..3|624
---+---+---
.23|8..|94.
.9.|..2|..1
..8|61.|.3.
---+---+---
.42|.7.|..9
...|...|...
97.|.2.|418

Ah ... hang on ... I can see what I've done wrong ...

I have been overly strict with my definition of "minimal". I was insisting that no two solutions of the dual problem (of meeting the relevant row/col/box constraints) shared a cell,value pair. I might prefer to call this strong minimality. What I should've been looking for were unavoidables for which no other solution to the dual shared a cell,value pair with the particular unavoidable in question (rather than with all unavoidables that solve the dual problem).

Oh, phooey. So my old posts refer to strong minimality, not ordinary minimality. I might go back and edit them in the next few days, or I might just go into hiding instead.

[Moschopulus]

... The SF grid must be special in some way that I don't understand.

Yes, how can it be that there is only one pseudo-puzzle with two solutions? It's hard to believe that this grid has some property that makes it that unique.

I wonder if there are counterexamples to your conjecture in another grid.

[Ocean]

... Can you post the different representatives of sizes 8 and 9? (whatever form is easiest)

Thank you for the types of size 6.

I am sure these must have been described somewhere, but tried to work them out anyway. Found ten different representations of minimal unavoidable sets of size 8 (but it's easy to count too many or miss some):

Code: Select all

T1
-----------
1..|2..|3..
.2.|3..|1..
...|...|...
-----------
21.|
...|
...|
-----------

T2
-----------
1..|2..|...
.2.|...|1..
...|1..|2..
-----------
21.|
...|
...|
-----------

T3
-----------
1..|2..|...
.2.|1..|...
...|...|...
-----------
2..|.1.|
.1.|.2.|
...|...|
-----------

T4
-----------
1..|2..|...
.2.|1..|...
...|...|...
-----------
2..|...|1..
.1.|...|2..
...|...|...
-----------

T5
-----------
1..|2..|...
.2.|.1.|...
...|...|...
-----------
2..|1..|
.1.|.2.|
...|...|
-----------

T6
-----------
12.|3..|...
..3|1..|...
...|...|...
-----------
231|
...|
...|
-----------

T7
-----------
1..|2..|4..
2..|3..|...
3..|4..|1..
-----------

T8
-----------
12.|3..|4..
34.|2..|1..
...|...|...
-----------

T9
-----------
12.|4..|...
34.|1..|...
...|...|...
-----------
23.|
...|
...|
-----------

T10 [Edit: This one should not be in the list, it cannot occur]
-----------
12.|34.|...
34.|21.|...
...|...|...
-----------

########

[Red Ed]

Code: Select all

T10
-----------
12.|34.|...
34.|21.|...
...|...|...
-----------

Aaah, close but no cigar. This one would be unavoidable if only there were any grids that contained it! Depends on your definition of unavoidable, I suppose, but we probably ought to concentrate on unavoidables that can actually occur in real grids.

I've been PM'ing Moschopulus with small minimal unavoidables recently (and making loads of mistakes myself!), which is why it looked like no-one had answered his request for 8-sets and 9-sets.

[Ocean]

Code: Select all

T10
-----------
12.|34.|...
34.|21.|...
...|...|...
-----------

Aaah, close but no cigar. This one would be unavoidable if only there were any grids that contained it!

Thank you! Of course you are right (should never have trusted eyes only ...).


Three types of size nine:

Code: Select all

9A
-----------
1..|2..|...
.2.|3..|...
..3|1..|...
-----------
231|...|...
...|...|...
...|...|...
-----------

9B
-----------
12.|4..|...
3.4|1..|...
...|...|...
-----------
243|...|...
...|...|...
...|...|...
-----------

9C
-----------
1..|2..|...
2..|...|3..
.3.|1..|2..
-----------
31.|...|...
...|...|...
...|...|...
-----------

[Red Ed]

Three types of size nine:

Yes ... as predicted here.

I should say a bit about the nature of the strong-vs-weak minimal unavoidable confusion (all of which was my fault and caused me to post varying degrees of nonsense). Having understood the mistakes I was making, I recently went back and changed my searcher to look for any type of minimal unavoidable but then to accrue stats in two different tables: one table if the unavoidable was "strong", the other if "weak".

The table I referenced above was compiled back in the days when everything I was doing used the overly-strict "strong" definition of minimality. So it misses some types of unavoidable (quite apart from the fact that it came from a random process that is going to miss stuff anyway). However, subsequent effort against "weak" minimal unavoidables has found, after many hours of searching, only ~4000 representative examples so far and none of size less than 18.

So, back in this post, I was right to suggest that the counts for the small minimal unavoidables (say size <12) were pretty stable, irrespective of any strong vs. weak distinction. This means that if you extend your own search to 10-sets and 11-sets then you should find only as many as I reported back then.

My search is random: generate grids, select ~30 clues as a puzzle, compare the multiple solutions to the original grid, check for minimality. Thus, I can never be sure that I've found everything. Are you adopting the same approach, or something different?

[Moschopulus]

I assume Ocean did these by hand? If so, congratulations on the size 8 job. I didn't have the nerve to try it. I think you did pretty well. Your answers agree with Red Ed's statistics.

You asked if this had been discussed before - I don't think so.

Please don't try size 10 ....there's too many!

Thanks to Red Ed for sending me the unavoidables. Your programs are doing very well. I think it's safe to say you have all of size up to 14 anyway.

Aaah, close but no cigar. This one would be unavoidable if only there were any grids that contained it! Depends on your definition of unavoidable, I suppose, but we probably ought to concentrate on unavoidables that can actually occur in real grids.

Just to be pedantic, using my definition of unavoidable "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" that wouldn't happen. For me, unavoidable sets are only defined in completed grids.

[Ocean]

My search is random: generate grids, select ~30 clues as a puzzle, compare the multiple solutions to the original grid, check for minimality. Thus, I can never be sure that I've found everything. Are you adopting the same approach, or something different?

I would say I used a different approach - actually two rather different methods.

1.
The smaller sets (8 and 9) were compiled 'by hand' - using a method that aims to cover all possible configurations for nonisomorphic minimal unavoidable sets of a given size. [I found the principles behind this method so simple that I thought I could explain them here... but it turned out to be harder to explain them than use them.]

2.
For the large sets I used a side-effect of the generation of pseudo-puzzles. (Wrote a simple pseudo-search program not too long ago). All pseudo-puzzles (with two solutions) contain a minimal unavoidable set defined by the 'difference' between the two grid solutions. So, from a collection of pseudo-puzzles it's straighforward to pull a bunch of minimal unavoidable sets - [even without knowing anything about them].

The last method is somewhat similar to yours, but when puzzles have only two solutions the extra check for minimality is not needed (it's done implicitly by counting the grid completions). The method does not generate grids at random, but takes as input a list of sudokus. (The input sudokus can then be either random generated or a carefully selected set). In terms of finding minimal unavoidable sets, this method is pretty random.

Ummm - I think the above methods hold even with the distinction between 'weak' and 'strong' minimality. Guessing: Method 1 will find both weak and strong, and method 2 will find only strong minimals. (But still in a learning modus - it's less than a week since I had to ask about the definition of 'minimal unavoidable set'.)

You asked if this had been discussed before - I don't think so.

Please don't try size 10 ....there's too many!

You bet. I'm probably too lazy to do that!

[Ocean]

Here are two basic properties of unavoidable sets.

Conjecture 1A (Geometry): A minimal unavoidable set never has only a single cell selected from any row, column or box.

Conjecture 1B (Values): No value in a minimal unavoidable set ever occurs exactly once in the set.

(Most certainly pointed at other places, but nevertheless very useful when constructing or examining canditate sets.)

[Red Ed]

I'm sure you know those two properties hold and are not really conjecturing anything, but for completeness I'll take the bait and provide proofs ...

Conjecture 1A (Geometry): A minimal unavoidable set never has only a single cell selected from any row, column or box.

True. A clue-set U is unavoidable iff (a) it has a distinct "dual" clue-set with the same row/col/box memberships and (b) it is contained in at least one sudoku grid. Let U be an unavoidable in which cell (r,c) is the only one in row r. Let V be a dual of U. U and V must have the same value in (r,c) because they have the same values in row r (and in the other 26 rows/cols/boxes) as a whole. This means that U\(r,c) and V\(r,c) are "duals" too (they are distinct and have the same row/col/box memberships), so U\x is unavoidable, meaning its parent, U, isn't minimal.

Conjecture 1B (Values): No value in a minimal unavoidable set ever occurs exactly once in the set.

True. Suppose unavoidable U has a solitary value, z, that appears only in row r and column c. Then it must also appear only in row r and column c in any "dual" unavoidable, V, i.e. in exactly the same location (r,c). As above, this means U\(r,c) and V\(r,c) are also duals, hence unavoidable, and so U can't be minimal.

... very useful when constructing or examining canditate sets.)

This seems like you're edging towards a systematic enumeration of representative minimal unavoidables. That would be very nice ...

[Moschopulus]

Thanks to everyone for their contribution here, especially Red Ed and Ocean. Thanks to Red Ed we have added *all* unavoidables of size up to 12 to checker and after some tests it appears to speed up the program, sometimes by quite a bit. When time permits we will put the updated version on the web page.

http://www.maths.nuim.ie/staff/gmg/sudoku/checker.html