The New Sudoku Players' Forum

[coloin]

The 416 is now understood - excellent.

I note also the confusion in the gang elements in the 44 was much worse than 1/44. That also explains why G coluldnt understand me when I was refering to it.

From Red Eds
Box2 in the 44 is equivilent/the same 25 times out of 44
Box 3 has 33? different combinations. - for what its worth.


When we are combining more than 3 boxes it gets complicated - and this is what defeated normal algebraic attempts at working out the total number of solutions.

It is slightly more complicated because when you have two boxes interacting at right angles there is always a different number of solutions possible to fill the box.
Eg taking B2 B4 independantly there are 5 possibles solution TOTALS for B5.
These are 432,384,392,400 & 448. The most common by far is the 400. It depends on the way the boxes interact see Frazer's post. This took me ages to comprehend by the way - but it is true !

I think I am right with these numbers

If there are 9! ways of expressing B2/B4 [B2 is fixed]
The way it works out can be expressed:
432 -- 1*1296 = 1296
384 -- 27*1296 = 34992
392 -- 54*1296 = 69984
400 --162*1296 =209952
448 -- 36*1296 = 46656
-------------
----------------------362880 = 9!

The rare 432 is eguiv to a gangster1/44 and this has 6^4 ways = 1296
The 3^3 ways of swapping the boxes which give a 384,392,400 - explains the 27 in the 27,54 and 162.

you need to study it to understand it


To answer G , well we dont know why a grid turns up 17 solutions with perhaps much more regularity than usual - if we did we perhaps could find a 16.

I have analysed Gs 17er with multiple 17s in it and it doesnt look special as regards its box combinations - note now 36 not 18. But I think it is special.

It is
400 - 26
392 - 6
384 - 1
448 - 3
432 - 0

Interestly in trying to construct grids with 384s - thats when pairs start appearing turning up - so I am now going for 392s and 400s - avoiding 448 and the dreaded number pairs. That might be the way.

In its favour of this analysis - grids constructed with more of the lower combinations definitely have have less total solutions. That might make all the difference. We need another breakthrough !

Regards

[coloin]

I think we have made a breakthrough - see the maths forum

Colin

[coloin]

Guenter and I have been analysing solution counts of
B12347 in an effort to see what is going on. - in the maths section.

B1 B2 B3
B4 B5 B6
B7 B8 B9

Also in an effort to decide which grid a 16 [if there is one] might be in

For B12347 the average solution count is around 2693

Guenter has published the series of all the possible configurations.

There are essentially 2802 different B2B3B4B7sudokugrids with 1035 different nonzero solution-counts for the remaining6*6 square plus 3*3 square of blocks B5B6B8B9 and B1.
Zero solutions only occur, when block1 can't be filled.Otherwise maximum is:6280 solutions,minimum is 1960.

[B1 has only one solution - one option per square]

The solution count for the B5689 is on average over 300000 and the total number of ways to fill these boxes alone was estimated as
9!*9!*403.2^2 [ approx] = 21407557176262656
and calculated by "Tim"some time ago
"I've now brute forced B1+B2+B4+B5 (took about 1 hour on a 4GHz pentium) and I get: 9!*25609120*48*48 = 21411158320742400"

Guenter has analysed these options !

"Takes about 5s times 2802. All counts divisible by 144.
Maximum 3904*144, minimum 1370*144. 761 different counts

average ~315464.02 "

Note there are 9 of these B5689 combinations in any one grid - which defines the grid.

I then started to analyse Gfroyles No 2 17er grid

Grfoyles No 2 grid

639 241 785
284 765 193
517 983 624

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418 .................... just a normal grid - not

boxes rearranged from
123
456
789
to
213
879
546

2187..........245952 solutions *
2356..........291744 solutions
7946..........246816 solutions *
1346..........309744 solutions
8956..........297072 solutions
1379..........245232 solutions *
2389..........285696 solutions
8754..........337536 solutions
2154..........314784 solutions

All the "B12347" solutions were decidedly average
[2305,2502,2513,2653,2762,2785,2804,2925,2929] solutions

Gfroyles Grid had 3 low solution rates in the 9 - all effectivly interlinking [actually all boxes interlink I think] My hunch is that it is difficut to get low solution to fit together.

Your tight 1960 grid probably has 8 other loose B5689s -I suppose we should prove that.
I will look at other average grids- the average is 310000.

Have you the solution list for the 761 ? That will be interesting.

Can we come up with a better combination of 9 ?

Perhaps that is all we have to do to get our grid with a 16 in it.

How difficult is it ?

Colin

[dukuso]

my currently most favourite ideas are:

1) restrict to 16-configurations with 2 or 3 ones, such that
the ones and other clues uniquely determine the set of all 9 ones,
discarding the actual values of the other clues, just the fact
that they are clues not equal to one.
Most of Gordon's 17-sudokus have this property for some digit.
Then use these additional ones and the other clues not equal to two
in the same manner to find the other 2-clues etc.
This gives some restrictions, how to place the 16 clues.
Try to classify these patterns.

2) fill in all small unavoidable sets randomly first, then
the other clues at random. That makes it much more likely
to find sudokus with unique solution. Maybe Gordon is
already doing this

[dukuso]

>I think you got one of my edits
>
>I think we have moved on a bit with my last post.
>
>I know its the maths thread - but I think I have shown why
>Gfroyles grid is special -

he has lots of them. 4000+ AFAIR, 450 on the webpage.
Do you have a special one in mind ?

>we need to construct a similar but better one.
>I will put a summary on the minimum thead.
>
>This was the Plan A
>"

missing three points here ?

>249183
>...367459
>...158726
>213......
>745......
>869......
>971......
>582......
>436......
>
>with 1960 solutions. It also has only 199296 solutions when you solve the
>complement 6*6. "
>
>That is tight

(dicht,straff,eng)

>But I think Plan B is the way forward ..........the complement 6*6s.....
>
>"Takes about 5s times 2802. All counts divisible by 144.
>Maximum 3904*144, minimum 1370*144. 761 different counts,
>average ~315464.02 "
>
>So 761 different counts
>
>>you mean, we do the B12347 calculation 9 times for that grid,
>with each of the boxes as B1 ?
>
>No I did the calculation B1245 the [6*6]- 9 times
>
>Grfoyles No 2 grid
>


+ + + + + + + 3 6
8 + + + 1 + + + +
+ + + + 2 + + + +

+ 3 + 6 + 2 + + +
+ + + + + + 1 9 +
+ + + 5 + + 8 + +

1 + + + + + 9 + +
+ 6 + + + + + 7 +
+ + + 3 + + + + +

http://www.csse.uwa.edu.au/~gordon/sudokumin.php

?

>639 241 785
>284 765 193
>517 983 624
>
>123 857 946
>796 432 851
>458 619 237
>
>342 178 569
>861 594 372
>975 326 418 .................... just a normal grid - not
>
>rearranged from
>123
>456
>789
>to
>213
>879
>546

what you mean ? Why should it (not) have been rearranged _that_ way ?

>2187..........245952 solutions *
>2356..........291744 solutions
>7946..........246816 solutions *
>1346..........309744 solutions
>8956..........297072 solutions
>1379..........245232 solutions *
>2389..........285696 solutions
>8754..........337536 solutions
>2154..........314784 solutions

ahh, now I see. The first 4 digits are block-numbers.

>Gfroyles Grid had 3 low solution rates of the 9 - all
>effectivly interlinking [actually all boxes interlink I think]
>
>>XX-
>>X-X
>>-XX
>>
>>Do you follow ?
>
>why are they important ?
>
>Perhaps not vital - but the empty boxes are selfilling
>in a valid sudoku grid [Which we are starting with]

at most one solution

>The boxes
>12X
>4X6
>X89
>
>The tight boxes unite around the central box
>126X and X689 to define the grid.

don't know where you get 126X and X689 from.

>Thanks for the B12347 but I think the enumeration fir B1245 is the
>one we need to look at.

could be done using those data. That was the method which I thought
were most easy. Mayber there was a better method ?

>Your tight 1960 grid probably has 8 other loose B1245s -I suppose
>we should prove that.

loose ? You mean, we should run it through the same computation as above ?
OK : 320400,398736,293328,247824,307584,393696,311472,335952,199296

>I will look at other average grids - but It takes my program half
>an hour each !

I can send my solver, if you want.

>Have you the solution list for the 761 ?
>That will be interesting.

I sent the list for the 2802.

>Can we come up with a better combination of 9 ? That is all we have
>to do to get our grid.

find a sudokugrid, where the 9 solution-counts computed as above
have minimal sum ? We should write a program to identify the
9 corresponding classes from the 2802-gang for a given sudokugrid !
Then we can calculate these 9 numbers in a fraction of a second by
table-lookup.

Reminds me, that I also wanted to write a program to identify
the 6 gang416-indices of a given sudokugrid.
And the 84-graphisomorphismclasses of the 3-symbol-subset-grids.
And a program to compute all unavoidable sets of size <10 for a given grid.

Can't we share these tasks ?



Guenter.

[coloin]

Plan A was
do the B12347 first
Plan B
do the B5689
but it appeared a huge task - obviously not!

Every grid has 9 of thes middle box computations which are different.

Your 1960 is suitably loose [ie not tight, not lacking in constriction]

Gfroyles -no 2 has changed - it was no 2 of the 29 17ers in one grid [sorry]
I would have thought it is up there with the best!

its
xxx | 24x| 7xx
x8x | xxx| x9x
x1x | xxx| xxx
-----------------
xxx | 8xx| xx6
7xx | xxx| xxx
4xx | xxx| 2xx
-----------------
3xx | x7x| xxx
xxx | xxx| xx2
xxx | xx6| x18

goes to

639 241 785
284 765 193
517 983 624

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418

I rearranged the boxes in an effort to show the interaction between the two particular 6*6s which had both a low solution rate.

B1245 and B5689
I rearranged it to show this interaction - both have a low solution rate.

The other clues in the other boxes 3&7 [&5] have one solution.
>"at most one solution" read ONE solution

The fact that the solution rate is low means you have more chance of getting away with less clues in the grid.

Actually - all boxes interact with each other - therefore probably it is academic.

Programming me .......no thanks I would love to if I could....
Share tasks......it took me half the night to do those 9 calculations !
Please just keep me informed.

This is the way

"find a sudokugrid, where the 9 solution-counts computed as above
have minimal sum ? We should write a program to identify the
9 corresponding classes from the 2802-gang for a given sudokugrid !
Then we can calculate these 9 numbers in a fraction of a second by
table-lookup. "

Yes...........Brilliant

Your favorite ideas from your last post will be next in action.

Have you heard the song "you are 17 going on 16 " ?

Colin

[dukuso]

>Gfroyles -no 2 ...

you claim that you picked one of his grids almost at random and
it showed unusual behaviour ?

>Programming me .......no thanks I would love to if I could....
>Share tasks......it took me half the night to do those 9 calculations !
>Please just keep me informed.

then you should have explained them better, so everyone
could have understood and admired it !
Although, I'm wondering meanwhile whether anyone except you,Mosch.
and me is following this

>This is the way
>
>"find a sudokugrid, where the 9 solution-counts computed as above
>have minimal sum ? We should write a program to identify the
>9 corresponding classes from the 2802-gang for a given sudokugrid !
>Then we can calculate these 9 numbers in a fraction of a second by
>table-lookup. "
>
>Yes...........Brilliant

what makes you think that the B12347+B5689 partition is more promising
than the usual B123+B456789 ?

>Your favorite ideas from your last post will be next in action.
>
>Have you heard the song "you are 17 going on 16 " ?

no. I heard : "with 17 you still have dreams"

>Colin
Guenter.

[Moschopulus]

>you claim that you picked one of his grids almost at random and
>it showed unusual behaviour ?

I agree. I could pick the numbers in one grid and find a connection to the signs of the zodiac. Does that mean the signs of the zodiac are the *cause* of the behaviour in that grid?

I need to see some statistics to be convinced that there is some connection. Coloin, can you compare numbers of solutions to numbers of clues on lots of grids?

I guess intuitively the reasoning is that if boxes 12347 have a small number of completions, then only a few clues need to be added to them to get a unique solution. If there were lots of completions then lots of clues would need to be added to ensure a unique solution. In the first case, most of the clues are already in boxes 12347. I'm not convinced that some clues are "more powerful" than other clues. Is there any evidence for this? Or are you just guessing.


>Although, I'm wondering meanwhile whether anyone except you,Mosch.
>and me is following this

udosuk said on another thread that (s)he was following it. one more!

[Moschopulus]

Going back a bit to a discussion between red ed and gfroyle:

For SF I get the following sort of numbers (focusing on the small exchangeable sets because these give the most power in restricting the size of the hitting set):

2 exchangeable 4-sets
1 5 19 23
36 37 72 73

(as a C programmer, my numbering of the cells is from 0..80 row by row)

14 exchangeable 6-sets
7 8 43 44 79 80
19 20 65 70 73 79
63 67 71 72 76 80
18 19 27 31 46 49
51 52 53 69 70 71
28 33 37 41 50 51
21 23 48 50 75 77
0 6 20 24 36 38
3 4 39 40 75 76
15 16 33 34 78 79
12 13 48 49 57 58
4 5 49 50 67 68
21 22 30 31 66 67
10 13 15 19 22 24
.............

Hi Gordon.

Just eyeballing it, I can find a 10-set {19,37,80,50,52,36,4,78,49,22} which hits all these unavoidable sets, i.e. this set meets all these sets. Maybe we can find a smaller one, I don't know. But the point is, it didn't take long. I first note that the pairwise intersections between these unavoidable sets are small (just 0 or 1 I think). I looked at how many sets contain a number, and found that 19 is in four of them and 50 is in three of the unavoidable sets. Then 37, 80, 4, 49, 22 are in two of the unavoidables, so take them too. [there may be errors here, but its not important]

It's pretty crude, but what about listing the numbers of sets that contain each number, and using that to generate a hitting set. It would probably be better to first generate a collection of unavoidable sets with small pairwise intersections - what do you think? Maybe this is the hard part, but it doesn't have to be the best such collection. Disjoint unavoidable sets are good.

Let a_i be the number of sets containing i, for i from 0 to 80. Say the numbers a_i have values 1,2,... k. (k=4 above). First take the numbers that are in k unavoidable sets, then take the numbers in k-1 sets if not already used, etc. Of course this is too naive to get a minimal hitting set, but it might get one that's not too bad. (?) I wonder how big it is.

From there one can try Guenter's idea of choosing some or all of the clues in this hitting set, and adding others at random.

Someone probably tried this already.....?

[dukuso]

just for completeness, I assume this is the grid
where M. was talking about.

639 241 785
284 765 193
517 983 624

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418

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


Seems that I was too optimistic with the number of unavoidable sets.
I had an error in the uploaded nppcs2.exe program.
It was for latin squares and discards the blocks.


We could also use some disjoint unavoidable sets and merge them.
Or try to identify otherwise (empirically?) subregions which must
hold k clues at least.

[coloin]

Ok Im sorry, - the joke was lost on me initially

"find a sudokugrid, where the 9 solution-counts computed as above
have minimal sum ? We should write a program to identify the
9 corresponding classes from the 2802-gang for a given sudokugrid"


these are the solutions for B5689 that Guenter provided - for a grid which had a single low solution rate for one B5689 [thank you]
320400
398736
293328
247824
307584
393696
311472
335952
199296

and he has provided me with a complete list of the solution totals. Thankyou. There is a wide range of these solution totals.

I generated these for Gfroyles 17 no 2 grid of 29 - which is not a random grid - and I think there is a possibility that they represent why there are so many minimal puzzles in the grid.

245952 solutions
291744 solutions
246816 solutions
309744 solutions
297072 solutions
245232 solutions
285696 solutions
337536 solutions
314784 solutions

On a trial of one, I cant say that I have proved anything I admit.

Would I be able to use your solver program ? - mine took 45 minutes for each B5689 !
I will analyse more of Gfroyles grids, the minimal double 16er and other grids to see if there is anything in my theory.

I apologise for the reference to the song in the "Sound of Music" maybe we will be able to laugh at that when/if we get the 16.

[Moschopulus]

What is the highest number of unavoidable sets of size 4 that a grid can have?

Or what is the highest known?

[dukuso]

What is the highest number of unavoidable sets of size 4 that a grid can have?

Or what is the highest known?

8 bands from the 416 have 6 such sets. Though not disjoint.
That would give a theoretical maximum of 36

123456789
457189236
869372415

[Moschopulus]

8 bands from the 416 have 6 such sets. Though not disjoint.
That would give a theoretical maximum of 36

Thanks. Can three such bands be put together to form a valid grid?

123456789
457189236
869372415

I note something that may be interesting here.
The 6 unavoidable sets come in 2 groups of 3. The groups are
148
413
831

and

692
965
256

I have permuted the columns in the second one to show that it is the same as the first one.

Do the other 8 bands in the 416 also have this property?

The 3 unavoidable sets in the first one are
14.
41.
... (call this one A)

1.8
...
8.1 (call this one B)

...
.13
.31 (call this one C)

There is no cell common to all of A,B,C so we require 2 clues from these 3 unavoidable sets. This reminds me of a 3x3 subsudoku (Latin square) like
123
312
231
which also uses 9 cells and also requires 2 clues. We have found another such configuration.


1) Given 2 unavoidable sets of size 4 that are NOT disjoint, like say A and B above, do they always have a third partner like C? Probably not. Is it a good thing or a bad thing if they do? Probably a bad thing. This might help in dealing with non-disjoint unavoidable sets. Should we look for grids where the A's and B's don't have a partner C? Note that the cells in C are determined by A and B.

2) Define an (m,k) unavoidable set to be a set of m cells which requires k clues. We have two examples of (9,2) unavoidable sets, the 3x3 subsudoku
123
312
231
and the sets above like
148
413
831.
Are there any other (9,2) sets?
Can we classify the (9,2) unavoidable sets?
Is there an (m,2) unavoidable set with m<9 ? (edit: apart from the union of two disjoint (4,1) unavoidable sets)

[Moschopulus]

What is the highest number of unavoidable sets of size 4 that a grid can have?

Or what is the highest known?

8 bands from the 416 have 6 such sets. Though not disjoint.
That would give a theoretical maximum of 36

123456789
457189236
869372415

Wait. I just realized, can't we have sets across the bands and stacks, like

1...5....
.........
.........
5...1....
...

I still would like to know if 3 of these 8 bands can be put together to form a valid grid....please help dukuso