Pseudo-puzzles

Everything about Sudoku that doesn't fit in one of the other sections

Re: Pseudo-puzzles and minimal unavoidable sets

Postby Ocean » Sun Jan 08, 2006 9:01 pm

Red Ed wrote: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)"
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Pseudo-puzzles and minimal unavoidable sets

Postby Red Ed » Sun Jan 08, 2006 10:24 pm

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.
Last edited by Red Ed on Wed Jan 11, 2006 7:35 pm, edited 2 times in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Pseudo-puzzles and minimal unavoidable sets

Postby Moschopulus » Sun Jan 08, 2006 11:56 pm

Red Ed wrote:... 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.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Unavoidable sets of size 8

Postby Ocean » Thu Jan 12, 2006 7:24 pm

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

########
Last edited by Ocean on Fri Jan 13, 2006 6:42 pm, edited 1 time in total.
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Unavoidable sets of size 8

Postby Red Ed » Thu Jan 12, 2006 9:03 pm

Ocean wrote:
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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Unavoidable sets of size 8

Postby Ocean » Thu Jan 12, 2006 10:10 pm

Red Ed wrote:
Ocean wrote:
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.|...|...
...|...|...
...|...|...
-----------
Ocean
 
Posts: 442
Joined: 29 August 2005

Unavoidables

Postby Red Ed » Thu Jan 12, 2006 10:43 pm

Ocean wrote: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?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Unavoidable sets of size 8

Postby Moschopulus » Fri Jan 13, 2006 12:44 am

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.

Red Ed wrote: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.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Re: Unavoidables

Postby Ocean » Fri Jan 13, 2006 2:34 am

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

Moschopulus wrote: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
 
Posts: 442
Joined: 29 August 2005

Conjectures about unavoidable sets

Postby Ocean » Fri Jan 13, 2006 9:20 pm

Here are two basic properties of unavoidable sets.

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

:idea: 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.)
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Conjectures about unavoidable sets

Postby Red Ed » Fri Jan 13, 2006 10:59 pm

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 ...

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

:idea: 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 ...
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Moschopulus » Fri Jan 27, 2006 11:56 am

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
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Previous

Return to General

cron