The New Sudoku Players' Forum

[coloin]

Thanks very much for trying - spectacularly average result.

To answer your queries
The 16 clue problem has been annoyingy me . I may give up now !
The 8+5+5 pattern was a hypothetical one - I agree that almost every clue if not all contributes to the hitting set cover.


The method looked promising - I would have thought one of the 4 pairs would have been favoured

EDIT
The 4 sets in your grid - these are the numbers in your grid but you have chosen to show the SF different to Gfroyle.
{45,49,55,59} - 69015,69317,68922,68691 counts for these
{24,25,94,95}


But still it is nothing like wolfgang's results
[EDIT - because your grid is relabelled and transposed !]

EDIT
You get an average of 24-25 clue grids for your locally minimal randomly generated grids -starting from a set grid.
Whenever I started from 81 and randomly removed clues, I tended to get a multiple solution at the 30-35 clue mark with THe SF grid. I tended to get slightly more 35 - 40 with random grids.

This might be a benchmark for selecting grids.

Thanks anyway - a good try.

Maybe we will get the result when someone solves Gfroyles big problem - and I doubt it will be done in 6 seconds !

C

[dukuso]

>Thanks very much for trying - spectacularly average result.
>
>To answer your queries
>The 16 clue problem has been annoyingy me . I may give up now !

we never give up completely, we just reduce our efforts from time to time

>The 8+5+5 pattern was a hypothetical one - I agree that almost
>every clue if not all contributes to the hitting set cover.
>
>
>The method looked promising - I would have thought one of the
>4 pairs would have been favoured

it was worth a try

>The 4 sets in your grid
>{45,49,55,59} - 69015,69317,68922,68691 counts
>{24,25,94,95}
>
>The 69317 is the biggest freq of the 81 - hardly significant though.

this is freq of _removed_ clues. Well, I should have substracted them
all from 100000.

>But still it is nothing like wolfgang's results.
>
>I cant understand the 24-25 clue grids - whenever I started
>from 81 and randomly removed clues, I first got more than 1
>solution at around the 30 clue mark.

you have to test _all_ clues. Only when none of them can be removed
the sudoku is minimal.

>Have you "just" counted the frequencies in your locally minimal
>randomly generated grids ? {I think so}

yes. Maybe I can repeat and only count the grids with 21 or fewer clues.

...

[coloin]

> >The 4 sets in your grid
>{45,49,55,59} - 69015,69317,68922,68691 counts
>{24,25,94,95}
>
>The 69317 is the biggest freq of the 81 - hardly significant though.

this is freq of _removed_ clues. Well, I should have substracted them
all from 100000.

..

ah ! well I suppose that makes that clue [69317] the worst then !
EDIT If you transpose your grid into the standard SF we can compare it to Wolfgangs Results.

>Have you "just" counted the frequencies in your locally minimal
>randomly generated grids ? {I think so}

yes. Maybe I can repeat and only count the grids with 21 or fewer clues.
...

yes that might exclude "background noise" which is obscuring the best clues

Meanwhile I will analyse the effect at 30 clues [non minimal] and compare the frequencies of what happens when you remove each of the 4 cues in turn.

[gfroyle]

Gordon wasn't updating his list for some time, I don't know whether
he is still searching. Last time he said he got more and more instances
which he already had.

It's still working away in the background - up to 30000 17s now - but I am currently in Barcelona for a week, so it's a bit inconvenient to do frequent updates, and follow the forum etc.

I intend to do a major update soon after I get back home...

Cheers

Gordon

[dukuso]

There _was_ a little improvement when I fixed the
r3c2, i.e. in the number of found 20-clue-sudokus,
although maybe it was not significant.
However it was a bit better when I only considered
sudokus with <22 clues.
I noticed that the numbers matched well with Wolfgang's
and I tried to fix some other clues and empty spaces
consecutively dictated by the generated tables
newly calculated after each fix.

Finally I even got some 17s ! They were all
already in Gordon's table, though.
So I assume Gordon is doing something similar
or there are just no other 17s in sf.



take this grid: (called "strangely familiar" or short "sf")

Code: Select all

639241785
284765193
517983624
123857946
796432851
458619237
342178569
861594372
975326418


counts of occupied cells for randomly generated
minimal sudokus of size <22 over sf :

1640 1743 1327 1519 1686 1795 1645 1656 1503
1388 1663 1569 1517 1439 1477 1508 1507 1377
1503 1925 1460 1510 1489 1816 1621 1338 1264
1559 1424 1438 1565 1720 1406 1589 1618 1548
1781 1790 1491 1461 1371 1362 1404 1429 1420
1546 1463 1452 1665 1605 1540 1746 1697 1575
1614 1445 1457 1620 1555 1389 1523 1515 1456
1613 1227 1419 1551 1552 1472 1510 1580 1634
1831 1777 1369 1543 1527 1487 1496 1677 1643


Wolfgang's rookery numbers:
40 36 23 | 53 88 56 | 36 61 71
22 71 40 | 48 61 39 | 48 52 29
41 134 42| 63 49 80 | 68 20 22
51 34 47 | 60 57 40 | 68 77 53
88 73 63 | 26 39 15 | 17 25 40
59 43 45 | 91 62 62 | 94 94 57
51 39 30 | 57 31 49 | 64 30 30
47 27 29 | 63 77 45 | 29 45 50
79 66 32 | 60 55 41 | 52 63 61



counts of clues in randomly generated minimal
sudokus over sf :

average:24.104503 , 1000000 samples
19 3
20 229
21 6277
22 61494
23 227035
24 352839
25 248868
26 86121
27 15453
28 1589
29 89
30 3



--------------------------------------------------------------------

counts of occupied cells for randomly generated
minimal sudokus of size <22 over sf ,
when the "+" cells are deleted last (if possible)
and the "-" clues are deleted first :

Code: Select all

2238 3563 2923 3560    +    -    + 3447 3686
2730 4258 3288 3897 3159 3775    - 3786 4079
3195    +    - 4587 3560 3428 3033 3199 3110
2570 1897 4396    + 4887 3216 3371 3512 4993
   + 2785 3096 3169 3753 2761 5259 2749    -
5030 3641 3211 5224 3757 3532    + 4664 3088
4802 4052 4727 5608 5689 4077 3372 4754 4588
   + 3384    - 4270 3049 2813    - 3026 2444
2006    - 3280 3961 4139 5304 4619    + 3583


counts of clues in randomly generated minimal
sudokus over sf for the run with "+","-" above :

average:23.343729 , 1000000 samples
17 13
18 27
19 342
20 4133
21 37340
22 174711
23 344562
24 297497
25 116921
26 22175
27 2163
28 112
29 4

this took 2 hours, it's probably possible to make it much faster.


-Guenter.

[coloin]

counts of clues in randomly generated minimal
sudokus over sf for the run with "+","-" above :

average:23.343729 , 1000000 samples
17 13
18 27
19 342
20 4133
21 37340
22 174711
23 344562
24 297497
25 116921
26 22175
27 2163
28 112
29 4

this took 2 hours, it's probably possible to make it much faster.


-Guenter.

Now...... that is progress !

And there is more

There are 10 clues which are all in the SF list of 29

--- -4- 7--
-8- --- ---
--- --- ---

--- 8-- ---
7-- --- ---
3-- --- 2--

4-- -7- ---
--- --- ---
--- --- --8

There are 3 "8" clues
The pattern of the other clues completes the remaining "8" clues. Dukosu has mentioned this previously.

The reason the grid completes slightly better than others is that the 16 clues just happen to rather efficiently cover many of the unavoidable sets in this grid. The remaining 7 clues cover the rest of the unavoidable sets as well as allowing the grid to complete. [Which comes first ?] [EDIT ? the fact that you can generate a clue means it is already in an unavoidable set with the previous clue...!]

There are 29 17 grids of this pattern.

To get a 16 we have to be slightly more efficient !

We have to be fairly sure a clue is "in" before we use it. You would think r2c3 is "in" on this basis. The results could be skewed if there happens to be a lot of 17s with r2c3. This would be unfortunate !

Just how many ways/patterns are there to define 10 clues giving 16.
There will be 9*8*7 ways for the 3 clues - but whether you get this number of patterns for the 7 other clues - Im not sure.

C

[dukuso]

>There are 10 clues which are all in the SF list of 29
>
>--- -4- 7--
>-8- --- ---
>--- --- ---
>
>--- 8-- ---
>7-- --- ---
>3-- --- 2--
>
>4-- -7- ---
>--- --- ---
>--- --- --8

however, you would need this before you know about any 17s in the grid

>There are 3 "8" clues
>The pattern of the other clues completes the remaining "8" clues.
>
>The reason the grid comples slightly better than others is that
>the 16 clues just happen to rather efficiently cover many of the
>unavoidable sets in this grid.

so, you could start from this 10-clues configuration and design
a grid for it, such that the unavoidables are met well.

>The remaining 7 clues cover the rest of the unavoidable sets as
>well as allowing the grid to complete. [Which comes first ?]
>
>There are 29 17 grids of this pattern.
>
>To get a 16 we have to be slightly more efficient !
>
>We have to be fairly sure a clue is "in" before we use it.
>I think r2c3 is "in". The results could be skewed because
>there happens to be a lot of 17s with r2c3. This would be unfortunate !
>
>Just how many ways/patterns are there to define 10 clues giving 16.
>There will be 9*8*7 ways for the 3 clues - but whether you get this
>number of patterns for the 7 other clues - Im not sure.
>
>C


I once tried to count the classes of these 10-patterns,
there must be a post from me.
AFAIR it was some hundreds or thousands.

[coloin]

however, you would need this before you know about any 17s in the grid

yes but I did I generate these 10 "sort" of independantly

so, you could start from this 10-clues configuration and design
a grid for it, such that the unavoidables are met well.

yes ive tried ! but its fairly impossible to control

I once tried to count the classes of these 10-patterns,
there must be a post from me.
AFAIR it was some hundreds or thousands.

yes you did mention the method

If you know which clue number is wrapped up in more unavoidable pairs this would be a good number to get all nine of.
C

[Moschopulus]

Finally I even got some 17s ! They were all
already in Gordon's table, though.
So I assume Gordon is doing something similar
or there are just no other 17s in sf.

Can you do the same with your grid with gangsters 42,5,42 - 42,1,42.
Can you find a 17 in this grid?

[Wolfgang]

With a similar approach as dukuso, but much slower and with a "broader" search, i also found one of the 17 clue sudokus directly in sf.
But though i spent more time for ssf (similar to strange familiar) i did not even find an 18 clue there.
So i doubt, that there is a 17 clue in this grid, although it behaved "better" down to 19 clues.
I hope i will find some time in the next week to improve my method.

[dukuso]

let's first wait Gordon coming back with 10000 new 17s :-)
Maybe he already tried such things, maybe it's not
promising at all.

[tso]

The answer to the question "What's the least number of clues required for a 9x9 Sudoku with irregular boxes" may have been answered definitively:

Code: Select all


+---+---+---+---+---+---+---+---+---+   
|                   | 6             |   
+   +---+---+---+   +---+---+---+   +   
|   |       |   |         7 |   |   |   
+---+   +---+   +---+---+---+   +   +   
|       |       |           | 8 |   |   
+   +---+   +---+   +---+---+   +   +   
| 1 |       |       |       |   |   |   
+   +   +---+   +---+   +---+   +   +   
|   | 2 |       |   |   |       |   |   
+   +   +   +---+   +   +   +---+   +   
|   |   | 3 |       |   |   |   |   |   
+   +   +   +   +---+   +   +   +---+   
|   |   |   | 4 |       |   |       |   
+   +   +---+   +   +---+   +---+   +   
|   |   |       | 5 |   |       |   |   
+---+---+   +---+   +   +---+---+   +   
|           |       |               |   
+---+---+---+---+---+---+---+---+---+   



I got this from:

http://www.bumblebeagle.org/dusumoh/
http://www.bumblebeagle.org/dusumoh/9x9/index.html

I've made no attempt to solve this, nor can I verify that it has a unique solution. I'll trust him on both points -- that it is a valid puzzle, and that I will probably be very hard to solve.

[dukuso]

yes, I talked with Bob Harris about these (and about copyright..)
He never bothered to minimize the clues and he just
prefers n*n-"dusumohs"
with n clues, one in each row,column,area.
So, now he just deleted one clue in the 36 puzzles he had and 7 of them
turned out to be uniquely solvable.

It would be interesting to find a pattern which gives an
infinite series of n*n-dusumohs with n-1 clues.

[me13013]

Howdy,

I'm not sure what you mean by infinite. Do you mean some rule to transform an NxN pattern into an (N+1)x(N+1) pattern, so that once you find an N-1 clue puzzle, you just apply the rule and out pops a puzzle of the next larger size?

(other random thoughts) Tso, am wondering how you managed to find my bumblebeagle site. Not that I was trying to hide it but I'm wondering how you happened to come across it.

As Guenter mentioned, I have only been searching for N-clue NxNs, with the one clue each per row, column, and box. And in general I was interested only in puzzles that were fully forced in the sense that a person can sit down and solve them without every having to backtrack. I have yet to find such a puzzle for the 9x9s (the 9-clue 9x9 at my site requires 18 backtracking steps). But in the process of searching for 8x8s, I discovered that the search was more fruitful if I limited it to "snakey" boxes (polyominos in which no square has more than two neighbors). And only when I limited my 9x9 search that way was I able to find any puzzles that were uniquely solvable at all. I'm not saying they don't exist, just that the density of solutions is somehow related to the types of pieces.

Because of the way I made those 8-clue ones after first discovering them as 9s, the 9th clue is verrrrry easy to guess. If I get some time I could relax the constraints on the clues and see if I can find a more interesting 8-clue one.

I also found some 7 clue ones that had two solutions, which as Guenter pointed out to me is the minimum possible for 7 clues. The holy grail would be a puzzle with no clues and 9! solutions. In other words, the layout allows only one possibility for the latin square. The player could just write 1-9 along the top row and start solving. I believe Mark Thompson found one of these for 5x5 or 6x6.

Hope that is of interest to folks,
Bob H

[tso]

Tso, am wondering how you managed to find my bumblebeagle site. Not that I was trying to hide it but I'm wondering how you happened to come across it.

Can't remember.