## Structures of the solution grid

Everything about Sudoku that doesn't fit in one of the other sections
I dont want to count them manually, but i understand it this way:
Remove 3 numbers from the solution grid and try to find 2 cells, where you can reinsert the digits, so that the puzzle becomes unique. Sample for digits 1,2,3 in the SF grid: The 2 in r3c5 and the 3 in r2c9.
Code: Select all
`+-------+-------+-------+| 5 6 . | . 8 9 | 4 7 . | | 8 4 9 | 7 . 6 | . 5 3 | | . . 7 | 4 2 5 | 8 9 6 | +-------+-------+-------+| . 5 8 | . 9 4 | 6 . 7 | | 9 7 4 | . 6 . | . 8 5 | | . . 6 | 8 5 7 | . 4 9 | +-------+-------+-------+| 6 9 . | 5 4 . | 7 . 8 | | 7 . 5 | 6 . 8 | 9 . 4 | | 4 8 . | 9 7 . | 5 6 . | +-------+-------+-------+`

Did you mean the same?
ravel

Posts: 998
Joined: 21 February 2006

Hi Ravel

Thank you for this example.

Yes, this puzzle is unique with these two clues, and it has 24 solutions in this 3-rookery. So it depends on how you choose the candidates within this rookery and with a clever selection of two candidates, it becommes unique. So this is obviosly why I got only 15 3-rookeries in the SF-grid.

If you only have got 6 solutions within the 3-rookery like removing 1,2,4:

Code: Select all
` 5 6 . | 3 8 9 | . 7 . 8 . 9 | 7 . 6 | . 5 3 . 3 7 | . . 5 | 8 9 6-------+-------+------ 3 5 8 | . 9 . | 6 . 7 9 7 . | . 6 3 | . 8 5 . . 6 | 8 5 7 | 3 . 9-------+-------+------ 6 9 . | 5 . . | 7 3 8 7 . 5 | 6 3 8 | 9 . . . 8 3 | 9 7 . | 5 6 .`

Then you can select the two candidates in any two cells, and the solution becomes unique.

/Viggo
Viggo

Posts: 60
Joined: 21 April 2006

RW wrote:I still wonder if the entwining affects the possibility of low clue puzzles. I ran an exhaustive check with checker on my "9-entwined" grid and found no 17s. I also had my computer search for 18s for 8 hours, but then I had to unplug the machine and stuff it into my car so I couldn't complete the test. Found no 18s in the first 8 hours though, I'll try to complete the search when I've got time.

I ran the search for an 18 in your grid

123469785456187932789253164371694528698512347542378691215946873864735219937821456

and none was found. It took about 18 hours.

Incidentally, this is very fast for an MCN 13 grid, or in fact any grid.
Moschopulus

Posts: 256
Joined: 16 July 2005

Thank you Moschopulus for running the search. That confirmed my suspision that the grid wouldn't have any low clue puzzles. I remember reading somewhere about grids without 18s, but I can't find it now. How common is this? Are there any grids without 19s or 20s...? I'd like to check the entwining of those grids. I suspect there would be some kind of correlation between low clue puzzles and the entwining of the grid. I would be very suprised to find a 17-clue puzzle with less than 10 fully entwined pairs in the solution.

Moschopulus wrote:It took about 18 hours.

Incidentally, this is very fast for an MCN 13 grid, or in fact any grid.

Does this suggest anything else than that it just happened to be fast? I'm not very familiar with checker or what could affect the time it takes.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

I think you can be reasonably certain that almost all [apart from two !]grids have at least one 19 in them -

The post you saw is this one - "Grid containing a 20 and no 19"

and I think it will answer many of your questions - and it will be useful to reopen thread here.

The grid is the dukuso16 grid described in a recent post
Code: Select all
` - 145726983837495261926381574293874156581269347674153892318547629459632718762918435 proved with checker not to have a 19 `

The other grid refered to is a canonical variant from the min clues thread
Code: Select all
`canonvarno19 - 123789456456123789789456123231564897564897231897231564312645978645978312978312645proved with suexmult not to have a 19 `

The canonical grids - there are many and they may prove difficult to interpret - they have multiple symettry and puzzlemorphs - they may have no entwining between two clues ?see

The "20 but no 19" thread went on with a short test of random grids

one out of seven grids had an 18 - it is difficult to be absolutly sure that an 18 is not present - one of our series or random grids had over 2000 19s before Ocean and I lost Interest !

Moschs "miracle" grid - exceptional in that it had so many [approx 180] 19s [but no 18]in many regions despite it having so many 4 sets and an MCN of 15.
Code: Select all
`Mosch1 - 937856241562194387481273569823647915615932478749581623378469152196725834254318796`
This grid may be of more interest to you.
coloin

Posts: 1733
Joined: 05 May 2005

RW wrote:I suspect there would be some kind of correlation between low clue puzzles and the entwining of the grid. I would be very suprised to find a 17-clue puzzle with less than 10 fully entwined pairs in the solution.

An interesting proposition. It would be interesting to compare some random grids to the grids that have a 17 with respect to the number of fully entwined pairs (2-rookeries that are minimal).

I did a comparison before of the MCN. Random grids have an average MCN of 11, whereas grids with a 17 have an average MCN of 10.

This may be related to the running time issue. Perhaps the number of fully entwined pairs is related to the running time of checker.

Very briefly, say you want a puzzle with 20 clues. Checker will generate a maximal collection of disjoint unavoidable sets, choose one clue from each of these sets, and then add in as many clues as necessary to get up to 20 clues. Do this in all possible ways. Typically there might be 11 disjoint unavoidable sets (MCN=11), so checker would choose one clue from each and then another 9. For each choice, check to see if there is a unique solution.

Now, if there are lots of small unavoidable sets around, there's a smaller number of choices to be made so checker will go faster.

So maybe "few fully entwined pairs" is another way of saying "lots of small unavoidable sets".
Moschopulus

Posts: 256
Joined: 16 July 2005

Taking RW s grid as an example and comparing it with two grids I constructed [by inserting as many 4-sets with different clues]

This is the firstline of checker128 searching for a 16
Code: Select all
`RWgrid - 123469785456187932789253164371694528698512347542378691215946873864735219937821456Found 214 unavoidable sets (52 of size 4 or 6).MCN is 13.1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 00h 52munentwiner1-123679458456328179789541326215987643394156782867432591971265834638794215542813967Found 293 unavoidable sets (27 of size 4 or 6).MCN is 12.1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 01h 00munentwiner2 - 127386945438295167965174238219738654843651792756429813391847526584962371672513489Found 271 unavoidable sets (32 of size 4 or 6).MCN is 12.1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 00h 33m`

If the speed of checker is relevant maybe the unentwiner2 grid seems to be better again !

Maybe I can get dukuso to write a program which gives a quick readout of our 36 2-rookerys !

Two more [remarkable] grids and one random mcn12 to compare
Code: Select all
`mcn14one17 - 439286157176593284258147396381754629795632841624918735542371968867429513913865472Found 402 unavoidable sets (24 of size 4 or 6).MCN is 14.1/4096 (62 puzzles gen'd; 0 uniques found); ETTF 0d 03h 19mmcn12twenty17s - 873692451649517328521348976132976845498125637765483192954761283386254719217839564Found 354 unavoidable sets (24 of size 4 or 6).MCN is 12.1/6144 (34 puzzles gen'd; 0 uniques found); ETTF 0d 13h 25mmcn12ran2 - 123849567456217839789356124642598713971463285538172946397681452865724391214935678Found 330 unavoidable sets (32 of size 4 or 6).MCN is 12.1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 02h 24m`

C
coloin

Posts: 1733
Joined: 05 May 2005

Why dont we listen to Red Ed more often ?

Red Ed wrote:I don't have a list of "essentially different" grids, but I can generate grids that are essentially-invariant under any of the 28-or-so classes of cell perms that have such fixed points. For example, here's an essentially-invariant grid of the op that permutes rows and columns 1->4->8->2->5->9->3->6->7 (I picked this op as it's from the class, 23, with the smallest number of fixed grids).
Code: Select all
` 157|629|834 826|743|591 493|185|267 ---+---+--- 268|491|375 934|257|618 571|836|942 ---+---+--- 385|914|726 619|572|483 742|368|159 `

Perhaps someone could investigate your comment about maximal minimal sudokus on this, presumably somewhat special, grid. Or, if keen, on the whole list of 162 (for fixed B1) ... I can produce these easily if desired.

Code: Select all
`RWgrid - 123469785456187932789253164371694528698512347542378691215946873864735219937821456 Found 214 unavoidable sets (52 of size 4 or 6). MCN) is 13.1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 00h 55mRededmax - 157629834826743591493185267268491375934257618571836942385914726619572483742368159Found 189 unavoidable sets (27 of size 4 or 6).MCN is 12.1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 00h 17m `

Lets wait and see if this can be explained
coloin

Posts: 1733
Joined: 05 May 2005

I ran the search for a 19 in RW's grid

123469785456187932789253164371694528698512347542378691215946873864735219937821456

and none was found.

Checker did find a 20

103000700050080900700050000000090000008510040000000600200006000000700010900000050

I think there's something interesting going on here. Having no 19 is extremely unusual. RW also pointed out that the "entwining" is extremely unusual. Are these related?
Moschopulus

Posts: 256
Joined: 16 July 2005

Thank you Moschopulus for checking the grid!

Moschopulus wrote:Having no 19 is extremely unusual. RW also pointed out that the "entwining" is extremely unusual. Are these related?

As I counted earlier in this thread, this grid that also has no 19 is nothing near as minimally entwined as my grid:

145726983837495261926381574293874156581269347674153892318547629459632718762918435

2-perm - 21
4-perm - 6
8-perm - 1
16-perm - 8

This tells us that the abscence of low clue puzzles doesn't imply few fully entwined pairs. But it still might be that few fully entwined pairs implies that there is no low clue puzzles...?

So far I haven't found any grid (not created by myself) with less than twice as many fully entwined pairs as my puzzle. On my first attempt to make a grid with few minimal 2-rookeries I managed to make a 14 (which I unfortunately deleted...) and then my second attempt gave this 9. This tells me that even though it is unusual, it shouldn't be hard to press the number even lower.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

So we have a third grid which doesnt have a 19 - despite the MCN as low as 13 !
I think [simplistically ] that a grid will by represented with a minimal number of clues if all the unavoidables can be covered by 17,18,19 or 20 clues.
If a grid needs 20 clues it is because there is no combination of 19 clues which hits all the unavoidable sets.

There are two processes here
1. A high MCN - eg dukuso16 grid - it doesnt have a 19 because there is no combination of 16 plus 3 clues which hits all the [high number of] 4 sets in this grid.
2.Reduced number of 2-perms - I think the reduced number of 2-perms inherently means there are more small 2-clue unavoidables - which you get with higher rates of 4,8 and 16 perms. This means that the RW grid doesnt happen to have any combination of 13 plus 6 clues which hits all the unavoidables.

Similar grids to RWs must be rare - and I would be impressed if we get one with less than 9 2-perms.

Incidently - how are we working out the 36 2-rookeries ?

I am running {checker128 19} on rededmax and entwiner2 [somewhat optimstically]

I have thought about the 170 essentially different 2-rookerys - if it helps in understanding constructing the grids.

2-perm
Code: Select all
`AAAAAAAAA   one 18 clue unavoidable sets between 2 clues - fully entwined+---+---+---+|1..|...|..2||.2.|1..|...||...|.2.|1..|+---+---+---+|.1.|..2|...||...|.1.|2..||..2|...|.1.|+---+---+---+|..1|2..|...||...|..1|.2.||2..|...|..1|+---+---+---+ +---+---+---+|12.|...|...||...|1..|.2.||...|.2.|1..|+---+---+---+|.1.|..2|...||..2|.1.|...||...|...|.12|+---+---+---+|..1|2..|...||2..|..1|...||...|...|2.1|+---+---+---+  these two cannot be morphed by row/box swapping`

4 perm
Code: Select all
`ABB   ABB   BBB   = +---+---+---+|12.|...|...||...|1..|.2.||...|..2|1..|+---+---+---+|21.|...|...||...|.1.|..2||...|2..|.1.|+---+---+---+|..1|...|2..||..2|..1|...||...|.2.|..1|+---+---+---+ but there will be different ways to complete a 14 clue B unavoidable set.here are more4+14  6+12  6+12  8+10  8+10 ABB   ABB   AAB   AAB   AABABB   ABB   ABB   ABB   AABBBB   ABB   BBB   ABB   BBB`

8 perm
Code: Select all
`ABC   ACC   ABB  ABC  ABB   ACC  ABC  ABC   ABB       ABC   ABC   ABC  ABC  ABB   ACC  ABC  ABC   ABC     CCC   CBC   CCC  BBC  CCC   BBC  BBB  ABC   ACC    `

16 perm
Code: Select all
`ABC  ABB  ABB  ABC  ACC  ABC  DDD  DDD  DDC  `

These ones are impossible
Code: Select all
`ACC  ABC   ABCACC  ABC   ACB?BB  ?DD   CBB `

There is only one way to have the 4-unavoidable and the two types of 6-unavoidable between 2 clues.

I am not sure about the different ways to have 8,10,12 and 14-unavoidable sets between 2 clues - this would then presumably add up to 170 from dukuso.

I am up to 33 clues in the RW grid.

C
coloin

Posts: 1733
Joined: 05 May 2005

coloin wrote:Incidently - how are we working out the 36 2-rookeries ?

OK........I had a look manually ! at the grids which were quick with checker

The rededmax and unentwiner2 grid just dont have enough of the 4 set unavoidables which rules out 2-perms between 2 clue numbers. [edit they have 27 and 20 entwined 2-rookeries - so rubbish ]

But then I remembered an old program of Guenters which gave us unavoidables......except it didnt give us them all......it only gave the 2 -clue unavoidables.....but not the 18-clue ones ......just what we need !

Here is the output from RW grid - which has 27 lines [out of 36]

Code: Select all
`C:\Suexk>nppcsu rw.txt123469785456187932789253164371694528698512347542378691215946873864735219937821456{11,12,71,72,}    {24,29,34,37,43,48,63,69,87,88,}    {55,56,95,96,}{11,13,41,43,}    {24,28,36,37,55,57,64,69,72,79,85,88,92,96,}{11,14,21,24,}    {37,39,43,46,55,58,62,69,72,75,83,88,96,97,}{11,19,22,24,35,37,43,47,54,55,61,69,72,73,}    {86,88,96,98,}{11,15,23,24,43,44,51,55,}    {37,38,67,69,72,76,82,88,96,99,}{11,17,31,37,}    {24,26,42,43,72,78,84,88,93,96,}    {55,59,65,69,}{11,18,32,37,72,77,81,88,}    {24,25,43,49,53,55,66,69,94,96,}{11,16,24,27,33,37,43,45,52,55,72,74,91,96,}    {68,69,88,89,}{12,14,21,29,34,39,62,63,71,75,83,87,95,97,}    {46,48,56,58,}{12,19,22,29,}    {34,35,47,48,54,56,86,87,95,98,}    {61,63,71,73,}{12,18,25,29,32,34,48,49,94,95,}    {53,56,63,66,}    {71,77,81,87,}{12,16,33,34,45,48,52,56,63,68,71,74,91,95,}    {27,29,87,89,}{13,19,22,28,73,79,92,98,}    {35,36,85,86,}    {41,47,54,57,61,64,}{13,15,23,28,36,38,76,79,82,85,92,99,}    {41,44,51,57,64,67,}{13,17,26,28,31,36,41,42,57,59,78,79,92,93,}    {64,65,84,85,}{13,16,33,36,}    {27,28,41,45,52,57,64,68,74,79,85,89,91,92,}{14,19,35,39,46,47,54,58,73,75,83,86,97,98,}    {21,22,61,62,}{14,15,44,46,75,76,}    {21,23,38,39,51,58,62,67,82,83,97,99,}{14,16,45,46,74,75,}    {21,27,33,39,83,89,91,97,}    {52,58,62,68,}{15,19,35,38,98,99,}    {22,23,73,76,82,86,}    {44,47,51,54,61,67,}{17,19,22,26,31,35,42,47,54,59,61,65,84,86,}    {73,78,93,98,}{18,19,47,49,53,54,61,66,73,77,81,86,94,98,}    {22,25,32,35,}{15,18,23,25,32,38,51,53,81,82,}    {44,49,66,67,76,77,94,99,}{15,16,44,45,74,76,}    {23,27,33,38,67,68,}    {51,52,82,89,91,99,}{17,18,77,78,}    {25,26,65,66,}    {31,32,42,49,53,59,81,84,93,94,}{16,17,26,27,}    {31,33,91,93,}    {42,45,52,59,65,68,74,78,84,89,}{16,18,25,27,45,49,66,68,74,77,81,89,91,94,}    {32,33,52,53,}-----------------------------------------------------------------------`

here is nppcsu.exe

I have looked at a few grids.......your grid will take some beating.

three more like yours with 27 unentwined 2-rookeries
Code: Select all
`123456789457189236968372514219547368586213497734698125645921873891734652372865941123456789457189236968372514219643857586297143734518962645921378891734625372865491123456789457189236968372514219745368586231497734968125645813972891527643372694851`
Last edited by coloin on Sun Jul 02, 2006 7:48 pm, edited 1 time in total.
coloin

Posts: 1733
Joined: 05 May 2005

Eventually a minimal 35 was found in the RWgrid
Code: Select all
`+---+---+---+|1..|4..|7.5||45.|1..|93.||78.|.53|..4|+---+---+---+|.7.|.9.|5..||.98|.1.|.4.||5..|3.8|.9.|+---+---+---+|.1.|.46|873||86.|.3.|...||...|..1|...|+---+---+---+`

Code: Select all
`1..4..7.545.1..93.78..53..4.7..9.5...98.1..4.5..3.8.9..1..4687386..3.........1...1..4..7..45.1..93.78..53..4.7..9.....98.1.34.5..3.8.9..1..4687386..3.........1.5.`

C
coloin

Posts: 1733
Joined: 05 May 2005

Thank you coloin for finding the 35, seems to be a real toughie! I understood that the minimal 35s could be more common than the 17s, is this true?

And thanks for finding Guenters program, it shall be of great help.

coloin wrote:I have looked at a few grids.......your grid will take some beating.

three more like yours with 27 unentwined 2-rookeries

Does "a few" stand for "a few well picked grids" or "a few million computer generated grids"? Interesting though that you found three with the same amount, but none with more unentwined 2-rookeries.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

RW wrote:Thank you coloin for finding the 35, seems to be a real toughie! I understood that the minimal 35s could be more common than the 17s, is this true?

Well we only have four grids where a 35 has been found.....and two of the grids were random grids....so possibly many grids have a 35. But I think it is extremely unlikely that I have found the best [or worst]region in any of the grids. And although the canon grid would appear to be the most likely to have a 36 there are bound to be other grids out there which have a 36. Unless there is something mathmatical which precludes it. There is progressivly less room for more clues to be the sole occupant of an unavoidable set.

In the search for 17s - because they only occured in 1in 10000 grids - searching for 17s was done by roving puzzle generating programs over many grids - this cant be done easily [I dont think Gfroyle even thought about it] because there are at least a million times more ways to but 35 clues into a puzzle than the 10^16 ways to but 17 clues into a puzzle - for every grid ! Considering you can barely generate 31 clue puzzles by random clue removal it is truly a surprize when the 35 turns up. One other thing which surprized me was the enormity of 34s in dukuso15 [over 3000 in the one region searched in, but no 35 !] I think this may reflect the enormity of the number of minimal puzzles in any one grid !

The 35 clue puzzle grinds to a halt early on in my hands - suexrat9 gives it 150, which isnt spectactular......I do wonder what special way it can be solved without backtracking ?
RW wrote:And thanks for finding Guenters program, it shall be of great help.

Yes to think I had it all along...I didnt really understand what it produced - dukuso was so far ahead at understanding the ins and outs of this !
RW wrote:Does "a few" stand for "a few well picked grids" or "a few million computer generated grids"?

Well, I am not able to change the program to give us a number "out of 36", but I am sure dukuso or Red Ed could modify it to search through "all" the grids to provide us with the answer. I made a few manually - by walking round the grid with 4 sets - but I didnt get near 27.

I found the three more by searching [visually] through the output of the set of grids [the set have the same gangster in B123 and B147] This gangster was chosen as it is was mentioned to be the least common in GFroyles 17s - as well as having the most unavoidables !
RW wrote:Interesting though that you found three with the same amount, but none with more unentwined 2-rookeries.

Yes,I await someone who can implement a bigger search, the 27 seems to be very rare..... but I do think a 28 is out there !

C
coloin

Posts: 1733
Joined: 05 May 2005

PreviousNext