The New Sudoku Players' Forum

[ravel]

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?

[Viggo]

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

[Moschopulus]

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.

[RW]

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.

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

[coloin]

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

[Moschopulus]

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

[coloin]

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 - 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 52m

unentwiner1-123679458456328179789541326215987643394156782867432591971265834638794215542813967
Found 293 unavoidable sets (27 of size 4 or 6).
MCN is 12.
1/4096 (0 puzzles gen'd; 0 uniques found); ETTF 0d 01h 00m

unentwiner2 - 127386945438295167965174238219738654843651792756429813391847526584962371672513489
Found 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 - 439286157176593284258147396381754629795632841624918735542371968867429513913865472
Found 402 unavoidable sets (24 of size 4 or 6).
MCN is 14.
1/4096 (62 puzzles gen'd; 0 uniques found); ETTF 0d 03h 19m

mcn12twenty17s - 873692451649517328521348976132976845498125637765483192954761283386254719217839564
Found 354 unavoidable sets (24 of size 4 or 6).
MCN is 12.
1/6144 (34 puzzles gen'd; 0 uniques found); ETTF 0d 13h 25m

mcn12ran2 - 123849567456217839789356124642598713971463285538172946397681452865724391214935678
Found 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]

Why dont we listen to Red Ed more often ?

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 55m


Rededmax - 157629834826743591493185267268491375934257618571836942385914726619572483742368159
Found 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

[Moschopulus]

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?

[RW]

Thank you Moschopulus for checking the grid!

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

[coloin]

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

AAA
AAA
AAA   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 more

4+14  6+12  6+12  8+10  8+10
ABB   ABB   AAB   AAB   AAB
ABB   ABB   ABB   ABB   AAB
BBB   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   ABC
ACC  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]

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.txt
123469785
456187932
789253164
371694528
698512347
542378691
215946873
864735219
937821456

{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

123456789457189236968372514219547368586213497734698125645921873891734652372865941
123456789457189236968372514219643857586297143734518962645921378891734625372865491
123456789457189236968372514219745368586231497734968125645813972891527643372694851

[coloin]

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

[RW]

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.

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

[coloin]

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 ?

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 !

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 !

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