The New Sudoku Players' Forum

by **JPF** » Thu Sep 07, 2006 8:21 am

Eioru wrote:Does this pattern have any puzzle?

Code: Select all
..*...*.. .*...*... *...*...* ...*...*. ..*...*.. .*...*... *...*...* ...*...*. ..*...*..

Yes.
Here's an easy one :

Code: Select all: . . 4 . . . 7 . . . 9 . . . 8 . . . 5 . . . 7 . . . 1 . . . 4 . . . 8 . . . 2 . . . 1 . . . 3 . . . 6 . . . 1 . . . 9 . . . 7 . . . 8 . . . 9 . . . 7 . . . 4 . .

JPF

by **Eioru** » Tue Sep 12, 2006 6:38 am

Searching it for the hardest puzzle.

Code: Select all: 123456789 598732641 746198352 419683275 837215496 265947813 681379524 952864137 374521968

This is first try, but only be rated 7.2

Code: Select all: ..3..6... ..8...64. ....9.... 4...8...5 .3.2.5.9. 2...4...3 ...37.... 9.2...1.. ...5.....

by **Red Ed** » Tue Sep 12, 2006 1:33 pm

Eioru wrote:Searching it for the hardest puzzle.
...

Eioru, this thread is about general properties of solution grids (such as number of unavoidable sets or entwined pairs) and how those properties vary for certain types of "interesting" solution grid (e.g. grids that contain 17-clue puzzles).

Your last two posts don't seem to be on-topic. Perhaps you could post to a different thread next time.

by **coloin** » Tue Sep 12, 2006 7:35 pm

Red Ed wrote:The one with the lowest completion count, a mere 113314 solutions, was this
Code: Select all
123|456|789 456|789|123 897|231|564 ---+---+--- 248|573|691 369|814|257 571|692|348 ---+---+--- 682|147|935 734|925|816 915|368|472

You might hope that, with such a low completion count from each generalised diagonal, this grid should be good for low-clue puzzles, but with MCN 9 and 23 unavoidables of size 4 or 6 that does not appear to be the case!

Probably not a result worth remembering, but it was a fun exercise.

Indeed strange that these grids which supposedly could be more likely to have a low clue puzzles - but dont.

I have always thought that the number of grid solutions in an incomplete puzzle was relevant......but I think it is related to the number of unavoidable sets / ways to iterate the unavoidable sets which contributes to this number of grid solutions. This is not necesarily a reliable index. It is high in the MC-like grids for this reason. Despite its initial attractiveness for choosing individual clues it has not proved that useful.

Similarly none of the fully-entwined [FE] grids that you found.......
have revealed any low solution clues........which begs the question why does the SFB have 17s ?

Is it just luck/coincidence/statistically likely - that "nearly" all grids have a 19 somewhere in them, say 1 in 10 have an 18 and only 1 in 100000 has a 17.

Hopefully I am not being too presumptious by saying [without evidence] that there are 19s in all the FE grids !

C

It looks that way !

by RW » Sun Sep 17, 2006 6:32 pm

coloin wrote:Is it just luck/coincidence/statistically likely - that "nearly" all grids have a 19 somewhere in them, say 1 in 10 have an 18 and only 1 in 100000 has a 17.

Hmm, I do think it's mostly luck/coincidence, but I'm not that sure that "nearly" all grids have a 19.

I made some further research on grids with high amount of 2-digit unavoidables. I picked 10 random grids with 70 or more 2d-unavoidables and searched them all for 19 clue puzzles, here's the results:

Code: Select all: (2d-unavoidables; MCN; amount of 19-clue puzzles; grid) 71;15; 0;386214975549783621721569348865127439437695812912348567198432756274956183653871294 70;14 22;374856912582913647961724538658379421193642785427581369745268193219437856836195274 70;14; 7;374215689126489753958367124745638291612794835839521467483152976597846312261973548 70;12;17;436815279579642138128937456285793614967421385314586927643278591792154863851369742 71;15; 0;421659837367281945859437126134826759276915384985374261798562413612743598543198672 70;12; 7;214936785876542139593817642768425391952361874431789256325198467687254913149673528 71;13;10;814635792396742581527981634981523467642897153735164829468219375179358246253476918 70;15; 0;465139287972648531318752946649281375153476892827593164586317429794825613231964758 70;15; 0;918423756726519384543768912832654179657891243194372568481935627279186435365247891 70;15; 4;612475398854329617397861254149236785583197462276548931438612579961754823725983146

4/10 had no 19s and the maximum amount of 19s was 22, which leaves all grids very far from any 18 puzzles. Based on these results I would say that there should be a lot more grids that require at least 20 clues than there is grids that can be solved in 17 clues. Looking for grids with 17 clue puzzles by choosing grids with "good properties" has never given any good results, but apparently grids with no 19s aren't hard to find this way. Even if the 17s are more common in grids with better properties (1/160000 random grids have 17s and 1/127 FE-grids have 17s), most of the 17s are in grids that don't seem to be very special, there's just so many more grids hat have average properties. My guess is that it's quite the same with "no 19s" grids, most of them should be grids that don't have this good properties.

These are actually all grids with 70 or more 2d-unavoidables found in a random sample of 5.000.000 grids (produced by gsf's program). That would estimate over 4000 grids with no 19s, only among the grids with >70 2d-unavs. A set of 5M random grids usually have around 100 grids with MCN 16, giving 100.000 MCN 16 grids (only counting MCN 16 grids with four disjoint 16-perms), many of which shouldn't have 19s either. And as I said, there should be a lot more grids with average properties, but still no 19.

I noticed one interesting thing with the puzzles produced. The grids with a few 17 clue puzzles usually have all the puzzles in the same region, with many common clues. These grids don't. The 22 puzzles from grid #2:

Code: Select all: 000800010000000040900020000600300000000000780007001000045000003010007006000090200 000050902080900040001000000600000000000040080007001000045008000000007006030000200 000050000000000607900024000000009420003600000007000000000000103200000050806100000 000050000000000607900024000000009420003600000007000000000000093200000050806100000 000050000000000607900024000000009420003600000007000000000008103200000050006100000 000006002080900040001000000600000000000040080007501000040000090000007006830000200 000000000502900000000004008000070020103000000400501000000260090000030050800000004 000000000002900000000004508000070020103000000400501000000260090000030050800000004 000006000000010607900004000000009420003000000007500000000200093010000050806000000 000000000000010607900004000000009420003600000007500000000008193200000050006000000 000000000002003007060004008000000401003002000007500000040060090010000050800100000 000000900080013600000700000600000401003002000007500000040060000010000050000000270 000000900080013000000700500600000401003002000007500000040060000010000050000000270 000000900000010600000700030000009401003002000007500000040060000010000050800100070 000006002002000007060004000000009400100000080007080000040000090000037006800100000 000006002080900040001000000600000001000040080007080000040000090200007006030100000 000000902000000600001704000000009400103600000007080000040060000000000050800100070 000000000002900000000004508000000020100000700400081060000260090000000000830005004 000000900502003000000004008000000020100000700400081000000260000000000850006090004 004000000000003600001700500000000001090640000020080300000060090000007000800100004 004000000000000040001700500000009001090040000020080300000200093000000006800105000 070006000080900040000020030600000001003040000000080000040000090010007806000100000

There's not a single clue that is common to all puzzles. Only 8 of the clues are not used in any of the puzles. The 17 puzzles of #4 doesn't have any common clue either. The 10 puzzles of #7 have one common clue (r9c5).

The searches took 6-16 hours each on Pentium M 1.7GHz. For some reason #6, MCN only 12, was among the fastest (<8h).

I've looked at all produced puzzles, most are very easy, none seemed really interesting.

RW

by **coloin** » Thu Sep 21, 2006 1:09 am

OK

So there are more grids without 19s....good.

Bearing in mind the grids with the fewest 20s...The PT, Canonvant and the MC - which all have a high number of 4 and 6 clue unavoidables.

This is not born out by your grids.......this one had a very low size 4 and 6 unavoidable count !

Code: Select all: 918423756 726519384 543768912 832654179 657891243 194372568 481935627 279186435 365247891 Found 157 unavoidable sets (38 of size 4 or 6). The maximum # of disjoint unavoidable sets (max clique number -- MCN) is 15.

The puzzles are spreadout throughout the grid.........I noticed this in a grid which had 2000 19s but no18 ! - I couldnt explain it either !

C

by **Moschopulus** » Thu Sep 21, 2006 1:27 pm

RW wrote:The searches took 6-16 hours each on Pentium M 1.7GHz. For some reason #6, MCN only 12, was among the fastest (<8h).

The MCN is only a guide to the speed of checker. I noticed long ago that sometimes a grid with a lower MCN would be quicker. I never really understood why. Maybe the number of 2-d unavoidables is a better measure of how quick checker will be?

by **ronk** » Sun Sep 24, 2006 7:25 pm

If one removes a single clue from a minimal 9x9 sudoku, the minimum number of solutions is 2 ... but what is the maximum? On what unavoidable set ... or entwined unavoidable sets ... is this maximum based?

I assume this has been covered somewhere, but without having seen it, my guesses of search keywords haven't been successful.

TIA, Ron

by **coloin** » Mon Sep 25, 2006 7:46 pm

ronk wrote:If one removes a single clue from a minimal 9x9 sudoku, the minimum number of solutions is 2 ... but what is the maximum? On what unavoidable set ... or entwined unavoidable sets ... is this maximum based?

Coincidentally last week I added just such a topic to this thread....perhaps it deserves a thread of its own

C

by RW » Thu Sep 28, 2006 5:47 pm

I might have overestimated the amount of grids without 19s to be found among the MCN 16 grids. Seems the MCN doesn't affect the possibility of 19 puzzles very much. In my collection of 1000 MCN 16 grids there was 3 with >70 2-d unavoidables. Two of them didn't have 19s, one had. Out of the five MCN 15 grids with >70 2-d unavs i checked, four didn't have 19s, no big difference there.

Trying to find a grid with fewer 2-d unavoidables and no 19 i checked twenty MCN 16 grids with 63 2d-unavs and all of them had 19s, mostly found during the first half hour of running checker. I stopped all searches immediately after finding the first 19s, but I suspect most of them has plenty of 19s. The average amount of 2d-unavs in my MCN 16 collection is 62, so these came from the better half. However, this doesn't change my belief that 'no 19s' are more common than 17s. Trying to find a grid with a 17 by looking at 2000 grids with "quite good features" would most likely not give any result at all.

Moschopulus wrote:The MCN is only a guide to the speed of checker. I noticed long ago that sometimes a grid with a lower MCN would be quicker. I never really understood why. Maybe the number of 2-d unavoidables is a better measure of how quick checker will be?

I think it does predict the running time better. As I mentioned, a complete search for a 19s was done in <8 hours in this MCN 12 grid (7 hours and forty-something minutes):

Code: Select all: 214936785876542139593817642768425391952361874431789256325198467687254913149673528

On the same computer, a complete search for 18s in this MCN 16 grid required more time (7h 57min):

Code: Select all: 246137895751698342389452716537214689624589137198763524412376958973845261865921473

On the MCN 16 grid I used checker128 which seemed to be the fastest option. The grid has only 53 2-d unavs, smallest amount in my MCN 16 collection. No 18s were found. The complete search for 19s took 2 days 4 hours and 45 minutes. The grid has 299 unique 19s, which again shows that there's more low clue puzzles in grids with fewer 2-d unavs. Keeping in mind that the running time on the the 70+ grids I checked earlier varied from 6h to 16h, the 2-d unavs is no absolute measure for running time either. I guess there's just lots of different factors that affect it in unpredictable ways.

RW

by RW » Tue Oct 03, 2006 8:42 am

Moschopulus wrote:It would be nice in a way if MC were the only grid to have exactly one 20 up to isomorphism. This would distinguish it in another way.

I'm sorry to dissapoint you, but the truth isn't that nice. The Pt-grid also has only one 20 up to isomorphism and with only 6 isomorphs, it beats the MC-grid comfortably. The 6 isomorphs:

Code: Select all: ......78..5.1.9.......2...4..1.4.......8....2.9....5..3..2.......4....63...57.... ....56...4.7....2..8.3......3......7..58..........2.4...8...9.....91...3.62...... 12...........8.3.6..9....5....6...9...5.....28...3.........4..5.749............18 ...4...8..5....3.6....27....3...5......8....2..6....4........75..491....9.......8 .2......94.7.8..........15.....4.8....5.....2.9.7......18.........9...63..2..3... ..3.5.......1.9.2.68.......2......9...58.........3...1...26.....74.....3...5..4..

It is also the first grid I know of that has cells that aren't part of any 20-clue unique puzzle:

Code: Select all: ....................................74..9163...................5....82...........

Red Ed wrote:I don't think it helps in the search that you're doing right now, but I should mention that the Pt grid is 6-way automorphic, with automorphism group generated by the two operators (r,s12) and (r,s23) where:
r = swap rows 1,3 and rows 4,6 and rows 7,9

It actually does help, unfortunately I thought about it only after searching the first three clues of the first unavoidable. The positions of the cells in the first unavoidable set {11,14,21,24} in the six isomorphs:

Code: Select all: 1.2|2.1|1.2 3.4|4.3|3.4 1.2|2.1|1.2

Any puzzle with a clue in any of the cells marked '1' would have an isomorph that turns up in a search with 11 fixed, any puzzle with a clue in any of the cells '2' would turn up in a search with 14 fixed and so on. Now look at the grid, and you see that both the six cells marked '1' and the six cells marked '2' are unavoidable sets:

Code: Select all: *-----------------------------------------* |*1 2 #3 |#4 5 *6 |*7 8 #9 | | 4 5 7 | 1 8 9 | 3 2 6 | |*6 8 #9 |#3 2 *7 |*1 5 #4 | |-------------+-------------+-------------|

Therefore all unique puzzles in the grid would have an isomorph that turns up in a search with either 11 or 14 fixed. For any further research, just fix 11 and multiply the result by 6 and you get statistics for the whole grid. I just started to count the 21s, but it might be that it takes too long...

RW

by **coloin** » Tue Oct 03, 2006 2:42 pm

To update then

coloin wrote:Bearing in mind the grids with the fewest 20s...The PT, Canonvant and the MC - which all have a high number of 4 and 6 clue unavoidables

Code: Select all: Bands No. of 20s Max clues MCN Av.puzz.size PT 132 132 132 , 414 414 414 6 34 15 25.55 Canonvant 1 53 53 , 1 138 138 184 34 14 [plus 2] 25.33 MC 1 1 1 , 1 1 1 648 35 12 [plus 6] 25.70

I have been struggling to fix clues in our MC grid

It would appear that we could fix at least 3. [Maybe 4 or 5][but which ?]

see Canonical grid has no 19

Using checker I fixed the clues 11,44 and the result was -
There are 23 20-puzzles in this branch (all puzzles were solved

Code: Select all: 100000700000000023089100000030500090060007200000000004000040000005900000070002600 100000700000700023089000000030500090004000000800001060000040000600008010000300005 100000080400000003009020400030500000060090201007000000000040900000008000070300005 100000080050709020000000006030500000004000000800001060000040900000008300070300005 100000080050700003009000000030500000000007000800200064000040900600008010000010005 100000080050700003009000050030500000004090200000001000000040900000000002078300600 100000080050700003009000000030500007000090000800001004000045000600000012000300600 100000080006000000700023400030500000004090200090001000000040900600008010000000005 100000080000000003009020400000504000060090000807000060002040900005008010000300000 100000089000700100000023000030500007004000000800000060000040000600008002070300005 103000080000709000080020000000500000004090200007001060002040900600000010000000005 100000080000000003009020400030500000004800000800001060000040900605070010000002000 100000009050000003009020400000500000004090000800001060302040070000008010000000600 100000000050000003009020400030500800004090200000001000000040070000908000070000605 100000000006700020080003000030500800000000001007200060000040070040908000000000605 100000000050700003009020000000500090004090200000001060002640008000000300070000005 100000000006700020080003000030504090000000200007000060000600008040008300000010005 100000000006780003009000050001500090000000200000030004300040008040900000070002000 120000000000780003009003000001500090060000000800200004000040008005900010000000600 100000000050700003009020006030500007000090200000001000000040908605000000070000040 100000000050080003009020400000560007004007000890000000002040900000000010000300005 103000000050000020000020406030500007004090001800000000000040900000008000070300005 120000000000780003009003000000500007004090200000000060002040900600000000070010005

If the MC grid has an effective MCN of 18 and we can fix clues the potential for counting 21 ,22 and possibly 23 clue puzzles is real.

Can you see the clues which filter the 648 isomorphs ? Is this possible ?

Is it these clues ?

Code: Select all: X X X 100000080400000003009020400030500000060090201007000000000040900000008000070300005

9*9*8 = 648

C

by RW » Tue Oct 03, 2006 3:41 pm

I wrote:For any further research, just fix 11 and multiply the result by 6 and you get statistics for the whole grid.

Of course, some puzzles may come up several times in different isomorphs if they have clues in many of the six cells the first clue can move too. Therefore these need to be removed before multiplying by 6. Right now 1/16 of the 21 count is done and if they don't start to turn up a lot more often soon, there might be < 2000 unique puzzles, including isomorphs, < 350 up to isomorphism. With the 2 first clues fixed (11 & 13) the search is estimated to take less than a day, in four days I should have the exact amount of 21s.

After finding this grid with only six 20s, I once again wonder if there might be a grid without a 20... bearing in mind that the grid with most 17s isn't the grid that appears to have the "best properties", then maybe the grid with least 20s shouldn't be the one that appears to have the best properties either...

RW

by **coloin** » Wed Oct 04, 2006 9:11 am

Yes it is complicated....fixing the clues

Note checker will also give non minimal puzzles around each of the 20s in the count for 21s - so this will reduce your expected total furthur.

I will have a go at finding 21s around one of the 20s.

379 minimal 21 clue puzzles found with clue 1 at position 11
These at most have 3 differing clues from the original 20 clue puzzle
There may be more if you go back furthur........bound to be more.

I see how its not quite as simple.......as multiplying by 6......hmmm
for example these ones would be double counted

Code: Select all: 1..4.........8.3.6..9....5....6...97..5.....28...3....3....4....749............18 12.4.........8.3.6..9....5....6...9...5.....28...3.........4..5.7.9...........418

There were 19 with clue 11 and 41

Code: Select all: 1........4...8.3.6..9....5....6...9...5.....28...3.........4..5.7.9..........3418

Assuming these puzzles are all non isomorphic .....
Therefore at least [6 x 379] minus 21 = 2253 minimal puzzles....

It will be an interesting result when you get it..........

Here is a [skewed] count of some of the puzzles in the PT

Code: Select all: C:\Suexk>clusta ptcount lines:1000000 average clues:25.566304 21 9 22 1051 23 22174 24 137344 25 323361 26 324568 27 152286 28 35032 29 3931 30 239 31 5

It is skewed by a bias because the program statistically is more likely to find [by removing clues] smaller puzzles. see

Never the less it tends to show up grids which dont have 19s [by failing to find a 20] I will update this with several others I have [mc,canonvant etc]

There may still be a grid without a 20......

C

by **ronk** » Wed Oct 04, 2006 12:50 pm

The term "2-digit unavoidable" is used frequently in this thread. But what exactly does it mean?

Since some of the 2-digit unavoidable sets are quite large, it can't mean only two digits appear in the set. So does "2-digit" mean each cell in the set can only be one of two values? IOW is each 2-digit unavoidable effectively a BUG-Lite?

For example, consider this unavoidable from the megaclue grid here. Is it a "2-digit unavoidable?"

Code: Select all: 8 1 7 | 5 9 6 | 2 3 4 9 2 3 | 4 7 1 | 6 8 5 4 6 5 | 2 8 3 | 7 1 9 -------------+-------------+------------ 7 5 18 | 18 2 9 | 4 6 3 2 38 9 | 6 34 48 | 5 7 1 13 4 6 | 137 135 57 | 9 2 8 -------------+-------------+------------ 6 9 2 | 38 35 58 | 1 4 7 5 78 148 | 178 14 2 | 3 9 6 13 37 14 | 9 6 47 | 8 5 2 Reduced to just the two possible clues in each cell: 8 1 7 | 5 9 6 | 2 3 4 9 2 3 | 4 7 1 | 6 8 5 4 6 5 | 2 8 3 | 7 1 9 -------------+-------------+----------- 7 5 18 | 18 2 9 | 4 6 3 2 38 9 | 6 34 48 | 5 7 1 13 4 6 | 37 15 57 | 9 2 8 -------------+-------------+----------- 6 9 2 | 38 35 58 | 1 4 7 5 78 48 | 17 14 2 | 3 9 6 13 37 14 | 9 6 47 | 8 5 2

A follow-on question: How does one know which of the unavoidable sets output by checker are 2-digit unavoidables ... or are they all 2-digiters?

The New Sudoku Players' Forum

Structures of the solution grid