Max number of clues 2

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

Postby coloin » Mon Jun 11, 2007 4:29 pm

Code: Select all
+---+---+---+
|...|...|...|
|.64|.91|.52|
|.57|.43|.81|
+---+---+---+
|.18|.57|.34|
|.36|.89|.27|
|...|...|...|
+---+---+---+
|.91|.25|.46|
|.72|.36|.98|
|...|...|...|
+---+---+---+ 36-clue minimal pseudoku with 2 sols

123568479864791352957243681218657934536489127749312865391825746472136598685974213
189572463364891752257643981918257634436189527725364819891725346572436198643918275

I think this possibly answers Smythe Dakota's question ????
The clues are from the U4 unavoidable sets [36 in total] in the dukuso15 grid......
Code: Select all
Dukuso15 - 123568479864791352957243681218657934536489127749312865391825746472136598685974213

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

It is an isohex symmetrical grid with 36 U4s - and no U6s

Each one of the clues is the sole occupant of a [U4] unavoidable set.

Code: Select all
[isomorphic] solutions - [all] non minimal 37s
.2........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
..3.......64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
....6.....64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
.....8....64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
.......7..64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
........9.64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
.........864.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
..........64791.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
..........64.91352.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
..........64.91.52957.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
..........64.91.52.57243.81.18.57.34.36.89.27..........91.25.46.72.36.98.........
..........64.91.52.57.43681.18.57.34.36.89.27..........91.25.46.72.36.98.........
..........64.91.52.57.43.81218.57.34.36.89.27..........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18657.34.36.89.27..........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57934.36.89.27..........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34536.89.27..........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36489.27..........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89127..........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27.4........91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27..9.......91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27....1.....91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27.....2....91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27.......6..91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27........5.91.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27.........391.25.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27..........91825.46.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25746.72.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46472.36.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72136.98.........
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36598.........
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.8.......
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98..5......
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98....7....
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.....4...
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98.......1.
..........64.91.52.57.43.81.18.57.34.36.89.27..........91.25.46.72.36.98........3

BTW the 36 clues have 2 solutions - the dukuso15 grid and surprisingly another familiar grid.....
Code: Select all
+---+---+---+
|189|572|463|
|364|891|752|
|257|643|981|
+---+---+---+
|918|257|634|
|436|189|527|
|725|364|819|
+---+---+---+
|891|725|346|
|572|436|198|
|643|918|275|
+---+---+---+  the MC grid.......no U4s but 150 U6s

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby ravel » Tue Jun 12, 2007 10:32 am

Havard wrote:here is another load of minimal 37s:
Only the puzzles in lines 7-13 are non isomorphic to former ones. So there are 23 minimal 37's so far.

Finding them is a lot harder than finding 17 clues (i wonder, if Gordon ever tried that). In the same time, in which i had found 38 17's (with option to get many more known ones with 2off/2on), i just managed to find 8 34's with a similar strategy (1off/2on, 1off/1on, 2off/2on).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Wed Jun 13, 2007 7:29 pm

Congratulations on the minimal 37s! I took the first 37 posted by coloin and added 9 clues and got this 46 clue puzzle with 17 non-redundant clues:

Code: Select all
 *-----------*
 |.23|45.|..9|
 |45.|.89|2..|
 |8.9|32.|4.5|
 |---+---+---|
 |28.|713|..4|
 |3..|..2|1..|
 |...|8..|..2|
 |---+---+---|
 |54.|23.|.97|
 |732|.98|54.|
 |9.8|574|.2.|
 *-----------*

I then used gsf's program to create all (5708) minimal puzzles in hope of finding more distant 37s. Unfortunately there was no more 37s, but I find the clue distribution very interesting:
Code: Select all
29 485
30 1224
31 2044
32 1456
33 334
34 85
35 30
36 42
37 8

Lots of high clue puzzles here, no puzzle with less than 29 clues. Now I wonder if all grids have regions like this.

I looked at the 2-digit unavoidables of all grids found that contain 37 clue puzzles and the grids are as average as average can be. In the structures thread we found that grids with lots of 2-digits unavoidables are less likely to have low clue puzzles. Here I looked at ten grids with 70 or more 2-digit unavoidables, only six of them had 19 clue puzzles. So far I haven't seen a single grid with less than 70 2-digit unavs that don't have 19 clue puzzles. Shouldn't grids like these be more likely to have high clue puzzles?

A while ago I removed all clues from boxes 159 in the Pt-grid (the grid with the highest amount of 2-digit unavoidables) and started creating minimal puzzles, hoping to find high clue puzzles with three empty boxes. The search was terminated when Windows decided to install updates and reboot the machine at 3am... I always forget to turn that off... Until then I had found 67340 puzzles with the following clue distribution:
Code: Select all
24 5
25 823
26 12881
27 33669
28 17894
29 2034
30 34

As comparison I took a random grid, removed the same three boxes and made some minimals from there. I didn't run it very long, but I can already see a big difference:
Code: Select all
23 15
24 155
25 459
26 982
27 344
28 19

The average number of clues in the Pt-grid is 27.11, while the average in the random grid is 25.78. If this difference applies to the full grids as well, then there should most certainly be a lot more 36 and 37 (and 38?) clue puzzles in grids like the Pt-grid. But as ravel pointed out, finding these high clue puzzles is not very easy...

As for the high clue puzzles with 3 empty boxes, there's an estimate of 600 million minimal puzzles with boxes 159 empty in the Pt-grid. Looking at the stats above, I expect these to include some 32 clue puzzles and perhaps even some 33s (I'm not going to complete that search).

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby coloin » Fri Jun 15, 2007 6:25 pm

Thanks RW......the old structures thread again !

Indeed the PT grid was thought to be a good grid for the big clues for the reason you have outlined [remember that the way we generate puzzles means that there is a bias towards smaller puzzles, so the norm for your average grid is 27 clues , the PT grid would have a real value of 28 ?]

Having said that the best that I found in the PT when I did it was a 34, and I think you can probably find a 34 in every grid.....indeed I found 34s in the SF grid and I eventually found several 35s in the SFB grid !!!. [these grids have 17puzzles and have a low 2-clue unavoidable count]

I think also that the difficulty in finding these puzzles is highlighted by ravel and we struggled to find a 35 for a long time.

Which makes the 36s and subsequent 37s all the more surprizing......

The problem is confounded by the many more ways to put 35+ clues into a puzzle [>10 million times more ways to do this than a 17]. The problem is different than the 17-puzzles in that by and large we have no difficulty solving the puzzle but what we have difficulty with is fitting in so many minimal/essential clues.

The post at the top of this page is an example of a human version of the set cover problem.

I "manually" identified 36 disjpoint unavoidable sets, added a clue to hit the remaining unavoidable - and removed 2 clues to provide minimality. [A 35 clue minimal in a very short time]

These puzzles [PT,duk15 etc] [high 2-clue unavoidables] but have fewer unavoidable sets in total [ only sets of 45 and less are of any relevance anyway].......can some one come up with a tool to sort this one ???????

The problem is finding which region to look at in a grid, [ a region might be 20 clues plus 20 non-clue spaces].

There is bound to be a good region in all grids, but I think it was a chance finding that I found a good region in the grid I obsessivly studied.

The grid with the 37s.. which you found 42 36-puzzles..... I think these could be used for furthur 2off/3on by haverd....I will repeat your study with 40+6 other clues.......

.....having said that I have failed to find significantly any more than what havard has already found.....26 37s [and over 150 36s]

Code: Select all
003400009450080200809320400280713000300002100000800000540030090732098540908504020
003400009450080200809320400280713000300002100000800000540230090730098540908504020
003400009450080200809320405280713000300002100000800000540030090732098500908504020
003400009450080200809320405280713000300002100000800000540230090730098500908504020
023400009450080200809300400280713000300002100000800000540030090732098540908504020
023400009450080200809300400280713000300002100000800000540230090730098540908504020
023400009450080200809300405280713000300002100000800000540030090732098500908504020
023400009450080200809300405280713000300002100000800000540230090730098500908504020

020400009050089030009203054200098040005302908908541320006004500000000003000035461
020400009050089030009203054200098040098541320005302908006004500000000003000035461
020400009050089030009203054200098045005302908908041320006004500000000003000035461
020400009050089030009203054200098045098041320005302908006004500000000003000035461
020450009050089030009203004200098040005302908908541320006004500000000003000035461
020450009050089030009203004200098040098541320005302908006004500000000003000035461
020450009050089030009203004200098045005302908908041320006004500000000003000035461
020450009050089030009203004200098045098041320005302908006004500000000003000035461

003000000450080200080023005014800006360001500598630410630098004005010060941360000
003000000450080200080023005014800006360001500598630410630098004805010060041360000
003000000450080200080023005014800006360001500598630410630098100805010060041360000
003000000450080200080023045014800006360001500598630010630098004005010060941360000
003000000450080200080023045014800006360001500598630410630098000005010060941360000

000456709450700100700000000200000003530602910067300020340567290602930400000204300
000456709400700100700000000200000003530602910067300020340567290602930400005204300

023450789000080030009002504000090800001804973000000042300078405005200098090540320
023450789000080030009002504000090800001804973000000042300978405005200008090540320

100406700006000000780100004017500090690301005805960400371690008508003900960005007


What was the gsf command to make all puzzles from a subgrid ?

Going up a clue level is very difficult, going sideways seems to be a whole lot easier, so it is going to be difficult to show that there might be a 38 in any particular [ PT] grid.

The irritating thing is that I think there [almost certainly] is a 38 out there [unlike the fact that there isnt a 16 !]. I say almost certainly because we have found 36s in a random grid, now we have a few 37s made from those 36s. There are 5 billion different grids, and there are many many regions [at least 10^20] in a grid.

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby gsf » Fri Jun 15, 2007 7:12 pm

coloin wrote:What was the gsf command to make all puzzles from a subgrid ?

by all you mean ?
all combinations of adding one clue:
Code: Select all
-go0.1c

0: off count -- don't turn off any clues
1: on count -- turn on 1 clue
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Fri Jun 15, 2007 7:21 pm

coloin wrote:[remember that the way we generate puzzles means that there is a bias towards smaller puzzles, so the norm for your average grid is 27 clues , the PT grid would have a real value of 28 ?]

I used gsf's program that systematically creates all minimal puzzles, shouldn't be any bias like that. Though I suspect that emptying three boxes should have some effect on the average number of clues.

coloin wrote:The grid with the 37s.. which you found 42 36-puzzles..... I think these could be used for furthur 2off/3on by haverd....I will repeat your study with 40+6 other clues.......

Here's the 42 36s if you're interested:
..34....945..8.2..8.932...528.713..43....21.....8.....54..3..9.732.98.4.9.85.4...
.234....945..8.2..8.93..4.5.8.713..43....21.....8....254..3..9.732.98...9.85.4...
.234....945..8.2..8.93..4.5.8.713..43....21.....8....254.23..9.73..98...9.85.4...
.234....945..8.2..8.93..4.5.8.713..43....21.....8.....54.23..9.73..98...9.85.4.2.
.234....945..8.2..8.93..4.5.8.713..43....21.....8.....54..3..9.732.98...9.85.4.2.
.234....945..8.2..8.93..4.5.8.713...3....21.....8....254.23..9.73..985..9.85.4...
.234....945..8....8.93..4...8.713...3....21.....8....254..3..9.732.9854.9.85.4.2.
.234....945..8....8.93..4...8.713...3....21.....8....254.23..9.73..9854.9.85.4.2.
.234....945..8.2..8.93..4.528.713..43....21.....8.....54..3..9.732.98...9.85.4...
..34....945..8.2..8.932.4.5.8.713...3....21.....8....254..3..9.732.985..9.85.4...
..34....945..8.2..8.932...528.713..43....21.....8.....54..3..9.732.985..9.85.4...
.234....945..8....8.93..4.5.8.713...3....21.....8....254.23..9.73..985..9.85.4.2.
.234....945..8.2..8.93..4.5.8.713...3....21.....8....254..3..9.732.985..9.85.4...
..34....945..8.2..8.932...528.713...3....21.....8.....54.23..9.73..98.4.9.85.4.2.
.234....945..8....8.93..4.5.8.713..43....21.....8....254..3..9.732.98...9.85.4.2.
.234....945..8....8.93..4.5.8.713..43....21.....8....254.23..9.73..98...9.85.4.2.
.234....945..8.2..8.93....528.713...3....21.....8.....54..3..9.732.98.4.9.85.4.2.
..34....945..8.2..8.932...528.713...3....21.....8.....54..3..9.732.98.4.9.85.4.2.
.234....945..8.2..8.93....528.713...3....21.....8.....54.23..9.73..98.4.9.85.4.2.
..34....945..8.2..8.932...528.713..43....21.....8.....54.23..9.73..98.4.9.85.4...
.234....945..8.2..8.93..4.528.713..43....21.....8.....54.23..9.73..98...9.85.4...
..34....945..8.2..8.932.4.5.8.713..43....21.....8.....54..3..9.732.98...9.85.4.2.
..34....945..8.2..8.932.4.5.8.713..43....21.....8.....54.23..9.73..98...9.85.4.2.
..34....945..8.2..8.932.4.5.8.713..43....21.....8....254..3..9.732.98...9.85.4...
.234....945..8.2..8.93..4...8.713...3....21.....8....254.23..9.73..9854.9.85.4...
.234....945..8.2..8.93..4...8.713...3....21.....8....254..3..9.732.9854.9.85.4...
..34....945..8.2..8.932...5.8.713..43....21.....8.....54.23..9.73..98.4.9.85.4.2.
..34....945..8.2..8.932...5.8.713..43....21.....8.....54..3..9.732.98.4.9.85.4.2.
.234....945..8....8.93..4.5.8.713...3....21.....8....254..3..9.732.985..9.85.4.2.
..34....945..8.2..8.932.4...8.713...3....21.....8....254..3..9.732.9854.9.85.4...
..34....945..8....8.932.4...8.713...3....21.....8....254..3..9.732.9854.9.85.4.2.
..34....945..8.2..8.932.4.528.713..43....21.....8.....54..3..9.732.98...9.85.4...
..34....945..8.2..8.932.4.528.713..43....21.....8.....54.23..9.73..98...9.85.4...
..34....945..8....8.932.4.5.8.713...3....21.....8....254..3..9.732.985..9.85.4.2.
.234....945..8.2..8.93....528.713..43....21.....8.....54..3..9.732.98.4.9.85.4...
.234....945..8.2..8.93....528.713..43....21.....8.....54.23..9.73..985..9.85.4...
.234....945..8.2..8.93....528.713..43....21.....8.....54.23..9.73..98.4.9.85.4...
.234....945..8.2..8.93....5.8.713..43....21.....8.....54..3..9.732.98.4.9.85.4.2.
.234....945..8.2..8.93....5.8.713..43....21.....8.....54.23..9.73..98.4.9.85.4.2.
.234....945..8.2..8.93....528.713..43....21.....8.....54..3..9.732.985..9.85.4...
..34....945..8....8.932.4.5.8.713..43....21.....8....254..3..9.732.98...9.85.4.2.
..34....945..8.2..8.932...528.713..43....21.....8.....54.23..9.73..985..9.85.4...


Note that they all come from the same 42-clue region...

coloin wrote:What was the gsf command to make all puzzles from a subgrid ?

Code: Select all
sudoku -qFN -m puzzles.txt > minimals.txt

(ravel, perhaps you could add -qFN to your description here. It runs a lot faster that way.

gsf, the process of creating all minimal puzzles using the -m command is still a lot slower than anything else your program does. Is there any commands to make it run faster?)

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby coloin » Fri Jun 15, 2007 8:59 pm

Thanks for all that.....

I know gsfs program gets all the puzzles ...eg from your 46 clue [suprapuzzle] subgrid......

But we are talking about getting the average value of all puzzles from a full grid.,.. of course there are too many to get them all, and by the random removal of clues method you tend to get slightly smaller puzzles - it is to do with the probability.......[Ocean explained it]

Anyhow it possibly means the average size puzzle in the PT grid is as high as 28 ! [TBC]

You have got all the puzzles from a region of 46 clues,19 unmovable clues and 35 clue empty clues.

I took this 46 clues, consisting of the 40 clues from the 8 37-puzzles.
Plus 6 random others [not the same as yours]

Code: Select all
+---+---+---+
|.23|4.6|.89|
|45.|.8.|2..|
|8.9|32.|4.5|
+---+---+---+
|28.|713|...|
|3..|..2|1.8|
|.91|8..|3..|
+---+---+---+
|54.|23.|.9.|
|732|.98|54.|
|9.8|5.4|.2.|
+---+---+---+

There were ony 8 clues which were unmovable / essential generating 350000 puzzles of which 169674 are unique, this was the clue distribution.
Code: Select all
350000 puzzles                          1000000 puzzles generated
C:\temp>clusta rw2solsa                 C:\temp>clusta rw2solsb                 
lines:169674 average clues:26.850590    lines:262808 average clues:26.987538   
   23  15                                  23  15                               
   24  1658                                24  1685                             
   25  18649                               25  21753                           
   26  51950                               26  75585                           
   27  52327                               27  85042                           
   28  28434                               28  49156                           
   29  11511                               29  20564                           
   30  3588                                30  6336                             
   31  1134                                31  1955                             
   32  331                                 32  584                             
   33  42                                  33  77                               
   34  20                                  34  29                               
   35  9                                   35  13                               
   36  4                                   36  10                               
   37  2                                   37  4                               


Here are 6 of the 10 36s which are new [poss lead to new 37s in other grids]
Code: Select all
..34....945..8.2..8.932.4..2..713...3....21.8...8.....54..3..9.732.9.54.9.85.4.2.
.234....945..8.2..8.93..4..2..713...3....21.8.........54..3..9.732.9854.9.85.4.2.
.234....945..8.2..8.93..4..2..713...3....21.8...8.....54..3..9.732.9.54.9.85.4.2.
.234...8945..8.2....93..4..28.713...3....21...........54..3..9.732.9854.9.85.4.2.
.234...8945..8.2....93..4.528.713...3....21...........54..3..9.732.985..9.85.4.2.
.234...8945..8.2....93..4.528.713...3....21...........54.23..9.73..985..9.85.4.2.


You can see that we havnt yet got all the 37 clues yet. [there should be 8] we have only got 4 out after 1000000 tries !

But we have most of the other lesser puzzles, Even though there are 37 clue puzzles in there we have to generate 150000 puzzles to find one !

Perhaps this is an example of what we are up against

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby ravel » Sat Jun 16, 2007 10:36 pm

RW wrote:(ravel, perhaps you could add -qFN to your description here.
Sorry, i forgot to add this option (i knew, that it is faster with singles constraints only).

Finally i found some 37's, but it took me 6 days:
Code: Select all
120406000457109206000027001210600008806002000975804602000040900590000104700901000
120406000457109206609027001210600708006002000975804602000000000590000107700901000
120056789050109206000072510210037698000001002930020150000000000590000860000065900
000450700057189206000007005000010804080000060064890000075961408800540607040070051
000450700057189006000007005000010804080000060064890003075961408800540607040070051
000450700057189206000007005000010804080000060064090000075961408800540607040078051
000450700057189006000007005000010804080000060064090003075961408800540607040078051
000000000407000206600720500208930400370008002964270803030000000746590308802300605
103456089050109036009000100000005098006804000800000600301548062502901003000032010
020000000407009206009007041208000065075000408946805027060000000704000012802071654

The ER's are between 4.4 and 8.4, the 8th one should be nice to solve (6.7).

I started with one of the 27 clue minimals of Mauricio's famous 37 clue puzzle with ER 11.0 (but i think each random puzzle would have been good enough). It was easy to get many (too much) 30 clues with a 1off/2on search. Then the air was getting thinner and from 32 on i sometimes added 1off/1on puzzles (which i had from the 1off/2on search). From 34 on i also added 2off/2on's.
The first 37 popped up, when i already had over 500 36 clues.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Sun Jun 17, 2007 9:51 am

Congratulations on the new 37s! So now we have 13 different grids with 37s. It turns out the amount of 2-digit unavoidables isn't that average after all:
Code: Select all
54: 2
55: 0
56: 0
57: 2
58: 3
59: 0
60: 0
61: 1
62: 0
63: 1
64: 1
65: 2
66: 0
67: 1

The average for randomly generated grids is about 55.5, the average among grids with 17s is 51, so it perfectly makes sence if the average for the grids with 37s settles around 60... Of course, the sample we have so far is too small to make any conclusions.

coloin wrote:There were ony 8 clues which were unmovable / essential generating 350000 puzzles of which 169674 are unique, this was the clue distribution.

I was expecting a lot more and a lot smaller puzzles from your search. I chose the added eight clues very carefully to give as few redundant clues as possible. I guess the 46 clues region I searched might be the tightest region in the whole grid.

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby ronk » Sun Jun 17, 2007 11:48 am

RW wrote:So now we have 13 different grids with 37s.

[edit: My post was about puzzle grids, not grids.]
Last edited by ronk on Sun Jun 17, 2007 1:42 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sun Jun 17, 2007 1:19 pm

ronk wrote:There are at least 32 non-equivalent 37s so far.

So there is, but only 13 grids. Interesting that in most grids where we have found a 37, there has been more lurking in the same region of the grids. This is IMO a good indication that there is a lot more 37s than 17s. These are the only 37s that are alone in their grids:
Code: Select all
.8...16..4.67....1....8....2..5781.38....2....573..2..34..67.2.5782.43.66.283...4
12.4.6...4571.92.6....27..121.6....88.6..2...9758.46.2....4.9..59....1.47..9.1...
12.4.6...4571.92.66.9.27..121.6..7.8..6..2...9758.46.2.........59....1.77..9.1...
.........4.7...2.66..72.5..2.893.4..37...8..296427.8.3.3.......74659.3.88.23..6.5
1.3456.89.5.1.9.36..9...1.......5.98..68.4...8.....6..3.1548.625.29.1..3....32.1.
.2.......4.7..92.6..9..7.412.8....65.75...4.89468.5.27.6.......7.4....128.2.71654

Are there more 37s in the neighbourhood, or are these truly the only 37s in those region of the grids?

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby ronk » Sun Jun 17, 2007 5:38 pm

RW wrote:So there is, but only 13 grids.

Aha, that ambiguous word grid bites me again. If we've got to have a single words for starting grids and solution grids, IMO puzzles and solutions would be better.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Sun Jun 17, 2007 10:13 pm

Two adds from the same region (ER 7.8)
Code: Select all
120406700407109000069720100206900450040000000900205610030000000602300070794502360
120406700407109000069720100206900450000000000900245610030000000602300070794502360
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Mon Jun 18, 2007 9:11 pm

Well done ravel - excellent

I know the pleasure of stepping up clues !

It also perhaps demonstrate that they are not that uncommon....

Thanks for the grid solution analysis on them RW....I dont think I ever counted up all the puzzles in my set of 46 clues - there may well be more.

Your 2-clue stats are interesting - holding up for the PT grid.............

I agree ronk the word "grid" has been used very loosely and abiguously. The "solution" word also is widely abused , I recently [above] confused gsf with the "subgrid" word .!

IMO the "[solution] grid" is the 81 completed cells you end up with when you complete a valid "puzzle"

"subgrids" are any puzzle which has less than 81 filled clues.

to include

invalid puzzles
non-minimal puzzles
minimal puzzles
puzzles with more than one grid solution - got to be called subpuzzles [logically][but not subgrids]
pseudopuzzles - these are subpuzzles which have 2 [? or 3] grid solutions specifically.

Coincidently the reason I state this is because I have maybe come to grips with defining the "region" word [coming up more and more] perhaps more meaningfully from which many puzzles are associated.

A region is effectivly a non minimal [but valid] puzzle !

There are many many of these !!!! See here

But how to pick them...........tricky

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby gsf » Tue Jun 19, 2007 3:52 am

there have been a few posts and pm's about the -m (minimize) and -goN.M (N-off M-on) options to my solver

thanks for the comments -- I'll address them collectively here

-m is implemented by recursively removing clues and running the solver with quick constraints (-qFN) to verify one solution
I replaced that verification with a barebones backtrack solver and that gives ~40% time improvement
I don't see how to do that verification without a solver

I also checked other places where the internal solver is called and where the -q constraints in scope don't matter
(usually where the -e filtering is not applied or where puzzle stats are not in play) I use simpler constraints like -qFN or the barebones solver

the -goN.M code is a bear
not many lines (~70 C) but hard to get right
I'm waiting for some numbers from our multi-threaded colleague to see if my code is doing too much work
there is a pruning step that makes -go produce fewer puzzles than expected
the N offs are done first, then the M ons
an on candidate is skipped if it is implied by the constraints in scope
these clues would be dropped if -m were applied later
I've convinced myself that this is ok, but its now documented to make it clear
you can use -goN.Mi to forces these implicit candidates to be attempted

-go uses an internal splay tree on minlex canonical puzzle keys to prune dups
some puzzle input, and certainly N>2,M>2 may exhaust memory
there are documented -go options after the M that bypass the prune
but the generation may take longer if there are a lot of dups
and the output will need to be processed to remove dups
but that could use external sort with higher capacity than the internal splay tree

solver version 2007-06-17 posted
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General