The New Sudoku Players' Forum

[Wolfgang]

As i posted some time ago, my idea for searching for low clues in a given grid was, first to try to find low clue sets that make all 3-rookeries unique. Now i implemented a simple method for this (starting with 12 or 18 randomly chosen cells and dropping and adding numbers then, based on how much they contribute to make 3-rookies unique) and tested it with the 2 gfroyle grids.
It was easy to find 14 and 15 clue sets. The second ("new") grid seemed to be slightly better, i also found 3 13 clue sets under about 100 less 16 clues each (none in the first). With the 13 and 2 of the 14 clue sets i tried to continue to make the (126) 4- and (84) 6-rookeries unique, but i needed at least 19 clues for the latter (ending up with 22 clues).
The obvious problem was that with the best 15 clue set i got this way, only 14 of the 84 6-rookeries were unique and no number could improve that much. (Compare: in gfroyles nr 1000 there was a 15 clue set for the 3-rookies, 41 of the 6-rookies were unique and one number made them all unique).
But maybe my method can be of some worth, when it can be improved to be faster (and is run on a faster machine than my notebook).
In the moment i have run it with the 2 grids and the one of coloin for half an hour. It found 5 14-16 clue sets each for gfroyls and none for coloins. So coloins grid doesnt look "promising" for me.

[Wolfgang]

Last night i counted for each cell, how often it is part of the clue sets for 3-rookeries i generated:

Code: Select all

 grid 1 (strangely fam.)         grid 2 (new)
 40 36 23 53 88 56 36 61 71      97 62 50 59 56 35 55 39 39 
 22 71 40 48 61 39 48 52 29      33 75 25 55 49 32 65 31 62 
 41 134 42 63 49 80 68 20 22     38 142 39 51 57 95 69 25 25
 51 34 47 60 57 40 68 77 53      34 39 60 36 77 61 76 113 39
 88 73 63 26 39 15 17 25 40      40 58 65 37 13 80 36 24 35 
 59 43 45 91 62 62 94 94 57      51 68 34 72 66 76 48 54 66 
 51 39 30 57 31 49 64 30 30      43 37 58 122 29 36 83 28 22
 47 27 29 63 77 45 29 45 50      50 36 49 43 93 35 44 64 116
 79 66 32 60 55 41 52 63 61      67 46 60 63 57 39 71 39 29 


I can see some correlation to the cells that are contained in all 17-clues:
<number>:<how often in my sets>(<order for this number in my sets>)
1:134(1), 1:63(4), 2:94(1), 3:51(3), 4:88(1), 4:59(2), 6:53(5), 6:41(6), 7:88(1), 7:36(8), 7:31(9), 8:71(1), 8:61(2), 8:60(4)

So i wonder, if the statistic is better, when the numbers are chosen according to this distribution.

[dukuso]

you fix a grid, e.g. Gordon's "strangely familiar".
You search for clue-sets which make each of the 84 3-rookeries
in that grid unique.
You found some with 13 or 14 clues.

For 6-rookeries you needed 19 clues, though.

You generated some thousand 17-clue sets which make
all 84 3-rookeries unique in str. fam. and counted how often
each of the 81-cells appeared in one of these 17s.
That's the table you posted.

(correct ?)


I don't understand:

can see some correlation to the cells that are contained in all 17-clues:
<number>:<how often in my sets>(<order for this number in my sets>)
1:134(1), 1:63(4), 2:94(1), 3:51(3), 4:88(1), 4:59(2), 6:53(5), 6:41(6), 7:88(1), 7:36(8), 7:31(9), 8:71(1), 8:61(2), 8:60(4)

[Moschopulus]

Wolfgang, I don't understand what you wrote either. Could you explain further please?

[Wolfgang]

you fix a grid, e.g. Gordon's "strangely familiar".
You search for clue-sets which make each of the 84 3-rookeries
in that grid unique.
You found some with 13 or 14 clues.

For 6-rookeries you needed 19 clues, though.

Yes, for the other grid i also found 3 12-clue sets, same problem with the 6-rookeries.

You generated some thousand 17-clue sets which make
all 84 3-rookeries unique in str. fam. and counted how often
each of the 81-cells appeared in one of these 17s.

no, in this run i found about 350 13-15-clue sets, and for each cell with a clue i increased the cell count for the table.

Then i looked at the 29 17-clue sudokus of gfroyle. They all have 14 clues in common. Here is the grid with those clues marked with x:

Code: Select all

6  3  9    2  4x 1  7x 8   5
2  8x 4    7  6  5  1  9   3
5  1x 7    9  8  3  6  2   4
1  2  3    8x 5  7  9  4   6x
7x 9  6    4  3  2  8  5   1
4x 5  8    6  1  9  2x 3   7
3x 4  2    1  7x 8  5  6   9
8  6  1    5  9  4  3  7   2
9  7  5    3  2  6x 4  1x 8x


Then i went through the numbers 1-9 and looked at my numbers in the corresponding cells in my table, eg for 1 you have (for line 1 to 9):
1: 56 (r1c6),48(r2c7),134x,51,40,62,57,29,63x
That means the two 1's in the 17-clues are in the cells with the top two numbers in my grid (the 1:63(4) above should be 1:63(2), and 4:59(2) should be 4:59(4)).
Having done this for the 14 clues, i saw that for 5 of the 7 numbers one clue is in the top number cell of my table, for 2 of them the second clue in the cell with the second largest number (if i did not make more mistakes looking through them).

That looked good for me, but it does not bring me anything further. Also if i fix those 7 clues looking for the 3-rookeries i dont have any chance to find one of the 15-clue-sets in the 17-clue sudokus that make the 3-rookeries unique. I think, not because my algorithm would not allow it (tending to go elsewhere), but because they are needles in a haystack.

I also dont believe in the meantime, that the statistic for random sudokus for this grid would be (remarkable) better, if you dont chose the cells equal distributed, but weighted with the numbers of my table.

[Moschopulus]

Wolfgang: one grid you look at is SF (Strangely Familiar). What is the other grid?

I have done some searches for a 17 now and then in the grid I posted in the first message of this thread. No 17 yet. I picked 10% of all the possible 17s (generated by the algorithm) randomly and didn't find a 17.

It would probably take about a month to check all the possibilities for a 17. I don't know if I'll bother. One option is to share the computation somehow, if people were interested. But who cares? Maybe people care more about the SF grid. I'll post a message about SF and sharing a computation in the minimum clues thread.

[Wolfgang]

Wolfgang: one grid you look at is SF (Strangely Familiar). What is the other grid?

gfroyles "similar grid" from page 2

[Moschopulus]

Here is another grid with no 16.

721638549958427631643519827597864213432175986816293754185946372279381465364752198

Proved by the same method as before, took about 4 hours. (see first message in this thread)

[dukuso]

here is the band which is used most rarely in Gordon's
17s compared with random grids:

Code: Select all

123456789
457189236
968372514


lots of unavoidables.
And here the best one:

Code: Select all

123456789
456789231
789231564


found, using Kjell's program to print the bands from a grid

[coloin]

Heres a grid which I believe will never be represented as a 16 !

I did get it down to 28 clues !

145628937
627395184
893741562
472156398
356982741
918437625
581269473
264573819
739814256


Heres a few unavoidable double pairs for starters !

25 sets of {x,x,x,x} !
Plus the rest.

Or maybe more unavoidables are better !

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

Unavoidables for 3 and 4 numbers not included - if there are any ?
C

[Moschopulus]

I agree it probably doesn't have a 16.
Here are 14 unavoidables, any two disjoint.

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

For any grid, the largest number of pairwise disjoint unavoidables is an important number.
Let's call it the max clique number (MCN).
Most grids seem to have MCN in the range 9-12.
13 is not unusual, and 14 is pretty rare although I have seen others.
I've only ever found one grid with MCN = 15, that's the grid at the start of this thread.
8 is not unusual, 7 pretty rare.

I wonder if low MCN indicates a higher probability of a puzzle with small number of clues.
I'd like to compare the MCNs of gfroyle's grids that have a 17 to the MCNs of random grids.

[dukuso]

>Heres a grid which I believe will never be represented as a 16 !
>
>I did get it down to 28 clues !

?

>145628937
>627395184
>893741562
>472156398
>356982741
>918437625
>581269473
>264573819
>739814256
>
>
>Heres a few unavoidable double pairs for starters !
>
>25 sets of {x,x,x,x} !
>Plus the rest.
>
>Or maybe more unavoidables are better !
>
>{11,12,41,44,62,64,} {27,29,58,59,73,77,83,88,} {35,36,95,96,}
>{11,13,71,73,} {26,27,36,37,} {44,45,84,88,95,98,} {52,59,62,69,}
>{11,19,23,27,57,59,73,78,85,88,91,95,} {34,36,42,44,62,66,}
>{11,16,31,36,} {27,28,87,88,} {44,49,55,59,94,95,} {62,63,72,73,}
>{11,17,25,27,32,36,61,62,73,76,93,95,} {44,48,54,59,88,89,}
>{12,15,22,29,35,39,} {41,43,81,83,} {56,58,64,68,74,77,96,97,}
>{13,15,22,26,43,45,52,56,} {37,39,68,69,97,98,} {71,74,81,84,}
>{14,15,74,75,} {21,22,81,82,} {38,39,67,68,97,99,} {43,46,53,56,}
>{15,19,34,39,56,57,66,68,74,78,81,85,91,97,} {22,23,42,43,}
>{15,16,55,56,} {22,28,31,39,43,49,63,68,72,74,81,87,94,97,}
>{15,17,22,25,32,39,43,48,61,68,81,89,93,97,} {54,56,74,76,}
>{13,18,33,37,45,47,51,52,65,69,71,79,92,98,} {24,26,84,86,}
>{14,18,21,24,33,38,51,53,} {46,47,65,67,75,79,82,86,92,99,}
>{18,19,78,79,} {23,24,33,34,} {42,47,51,57,91,92,} {65,66,85,86,}
>{16,18,24,28,47,49,72,79,86,87,92,94,} {31,33,51,55,63,65,}
>{17,18,47,48,} {24,25,51,54,61,65,} {32,33,92,93,} {76,79,86,89,}
>{12,19,23,29,34,35,41,42,64,66,83,85,91,96,} {57,58,77,78,}
>{12,17,25,29,32,35,76,77,83,89,93,96,} {41,48,54,58,61,64,}
>{13,14,21,26,45,46,52,53,71,75,82,84,} {37,38,67,69,98,99,}
>{13,19,23,26,34,37,42,45,52,57,66,69,84,85,} {71,78,91,98,}
>{14,16,46,49,53,55,63,67,72,75,82,87,94,99,} {21,28,31,38,}
>
>Unavoidables for 3 and 4 numbers not included - if there are any ?
>C


average number of clues in randomly created minimal sudokus
over this grid is 24.77 , which is pretty high,
average is 24.38, "most canonical" has 25.72, sf has 24.12 ,
sfb (17,no unav.in 2-rookeries) has 23.98 , ssf has 24.09.
Starting from an empty grid gives 23.88 average.

how does this correlate with MCN s ?

[Moschopulus]

average number of clues in randomly created minimal sudokus
over this grid is 24.77 , which is pretty high,
average is 24.38, "most canonical" has 25.72, sf has 24.12 ,
sfb (17,no unav.in 2-rookeries) has 23.98 , ssf has 24.09.
Starting from an empty grid gives 23.88 average.

how does this correlate with MCN s ?

Yes, would be interesting.

The first grid in this thread is

937856241
562194387
481273569
823647915
615932478
749581623
378469152
196725834
254318796

I call it MG (for Miracle grid, or Moschopulus grid).
It has MCN = 15.

You posted earlier that the average for MG is 24.49, slightly above a random grid but not as high as this grid.

Still, there might be some correlation.

[coloin]

Thanks for that analysis
: The grid is made from a
1xx
x2x
xx3

or

x1x
2xx
xx3

pattern in all the boxes. So there wont be a simple 4 clue unavoidable set with the 1/2,2/3,1/3 clues !

Code: Select all

+---+---+---+
|145|.2.|.3.|
|627|3..|1..|
|893|..1|..2|
+---+---+---+
|..2|15.|3..|
|3..|..2|..1|
|.1.|43.|.2.|
+---+---+---+
|..1|2..|4.3|
|2..|..3|.1.|
|.3.|.1.|25.|
+---+---+---+           which has 16 solutions.



A random grid with a full B1 and filled similarly like this has considerably more solutions.

Code: Select all

+---+---+---+
|145|3..|..2|
|627|1..|..3|
|893|.2.|1..|
+---+---+---+
|..1|..2|.3.|
|...|.13|2..|
|3.2|.54|.1.|
+---+---+---+
|21.|.3.|.4.|
|.3.|2.1|5..|
|...|...|321|
+---+---+---+    which has 5395 sols



But I think there are a reduced number of solutions in the former because of constrants generated - [No extra clues are generated in either grid] - so it might still be useful.

C

[Moschopulus]

This grid posted by coloin

145628937
627395184
893741562
472156398
356982741
918437625
581269473
264573819
739814256

has no 16. Exhaustive search for a 16 completed.