The New Sudoku Players' Forum

by **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

by **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).

by 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

by **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

by **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

by 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

by **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

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

by 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

by **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.]

by 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

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

by **ravel** » Sun Jun 17, 2007 10:13 pm

Two adds from the same region (ER 7.8)

Code: Select all: 120406700407109000069720100206900450040000000900205610030000000602300070794502360 120406700407109000069720100206900450000000000900245610030000000602300070794502360

by **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

by **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

The New Sudoku Players' Forum

Max number of clues 2