Su-Doku's maths

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

Postby coloin » Fri Aug 05, 2005 3:58 pm

Your method of classifying is more workable !

Yes each ganster will a significant expansion element - if they have the same number of solutions then that is ok. I might have thought it was as much as 6 ber B2 and 6 for B3 ie 36 - obviously not thankfully.

Are you allowing 3 permutations for the gangster in B1B4B7 ?

That would then be 3*3 permutations for each B12347

I think the whole enumeration is possible this way - but the usefulness perhaps is if we can get the B12347 with the least number of solutions.

My classification [prev post] is not necessary although the equivilances you get might ? turn out to have the same combination of box interactions - [note this is now doubled as each box has two different cross planes with one box].
If they have the same number of solutions - I would expect the box interactions to be the same. Maybe it doesnt work.

I will run a check on a few B12347s
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby dukuso » Fri Aug 05, 2005 4:33 pm

coloin wrote:Your method of classifying is more workable !

Yes each ganster will a significant expansion element - if they have the same number of solutions then that is ok. I might have thought it was as much as 6 ber B2 and 6 for B3 ie 36 - obviously not thankfully.

Are you allowing 3 permutations for the gangster in B1B4B7 ?

** no gangster here. I just generate all the extensions of B1B2B3
** and then group them

That would then be 3*3 permutations for each B12347

I think the whole enumeration is possible this way - but the usefulness perhaps is if we can get the B12347 with the least number of solutions.

**I have some incomplete statistics already

solutions, count of B1B2B3B4B7s with such many solutions
-------------------------------------------------------------
2264 ,528
2370 ,1032
2392 ,1032
2474 ,1208
2486 ,1186
2552 ,538
2600 ,538
2628 ,549
2630 ,480
2664 ,504
2696 ,528
2744 ,240
2760 ,216
2764 ,228
2808 ,444
2816 ,408
2824 ,444
2828 ,966
2880 ,550
2892 ,304
2896 ,240
2988 ,160
2992 ,228
3008 ,142
3068 ,204
3072 ,247
3130 ,624
3196 ,624
3238 ,624
3256 ,84
3454 ,312
3500 ,216
4000 ,42
4192 ,22

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


My classification [prev post] is not necessary although the equivilances you get might ? turn out to have the same combination of box interactions - [note this is now doubled as each box has two different cross planes with one box].
If they have the same number of solutions - I would expect the box interactions to be the same. Maybe it doesnt work.

I will run a check on a few B12347s




maybe I will restart the computation in the next days
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby coloin » Fri Aug 05, 2005 5:04 pm

Great
I suppose the end justifies the means
The solution totals are the same - therefore they are eqivalent.

I made solution totals 2126,2166, 2328,2481 and a 2502 straight off with my "sadman". but your methods are awsome.

The number of totals is going to be 415*415 ?

Pairings send the solution total > 10000 I think

Sit back and let the computor whirl.

Only 9!*56^2*216^4 to go

Thanks
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby dukuso » Sat Aug 06, 2005 1:41 pm

edit:
the calculation below is wrong. Some classes are missing.
For an update see this post:
http://forum.enjoysudoku.com/viewtopic.php?p=12563#p12563

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

there are essentially 2802 different B2B3B4B7 sudokugrids
with 1035 different nonzero solution-counts for the remaining
6*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.

When OTOH you fill a 6*6 square then there are typically
~300000 solutions for the rest.
A file with 2802 representatives is uploaded to
http://magictour.free.fr/b12347.p

essentially different means, that these 2802 cannot be transfered into
one another by our 9!*6^8*2 sudoku-transformations
nor by permuting the 3 entries in some minirows or minicolumns.


Guenter.



and here is the first sudoku with only 2 clues in a 6*6 square
which I found in Nr.39 of the 2802:


Code: Select all
...169347
...248159
...357268
2145.....
357......
869......
135......
728......
946.8....

Last edited by dukuso on Fri Oct 28, 2005 3:05 am, edited 1 time in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby coloin » Sat Aug 06, 2005 3:42 pm

Brilliant

Number of

XXX
..X
..X

or
... X
X [X] X
... X


Whilst this was being calculated :
I thought we could go the other way and from the minimum solutions of the 1960 we could find the 4 box [a four box square or the four corners - they are the same] with the minimum number of solutions.

[If my program would do it I would guess the minimum might be 4 392s !]

Put them together and we have one tight mama !!!!! [Pairs not present ???]

.............but the number of solutions for a corner box is more than 130000 [sadman stalls here][I see 300000 is your figure]
.............of course if we really went for the knarliest grid we would do the big calculation first.........leave it for now[plan B]



............this is not quite the final answer
............every grid has 9 different "middle box" "crunching exercises" which are all different
............so we are not quite there yet................

I am glad we are making progress with this now - and we have got something out of it.............. .

Gfroyles 17er grid is starting to reveal itsself I fear
We need to do the 9 crunching exercises for it - I reckon one of them will be a very low combination.

The tight box combinations will coincide with the "important" 6 boxes [which determine the grid"] in the 17er grid.

The 6 -a formulation of these ones:
XX-
X-X
-XX

Do you follow ?
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby Moschopulus » Sun Aug 07, 2005 12:07 am

dukuso wrote:there are essentially 2802 different B2B3B4B7 sudokugrids
with 1035 different nonzero solution-counts for the remaining
6*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.


Do you think this is useful in searching for a 16?

And why?
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Sun Aug 07, 2005 7:50 pm

I hope it s useful

We need to find the grid first.

We need to know why Gfroyles 17ers have so many 17s in them - [I hope it isnt that he has just looked harder.]
If they are special - we need to find out why - and then improve on it - to find a 16.

There are so many grids out there - I cant believe we have found the grid which has the best chance [but fails].

Anyhow - what we have done is to count the number of solutions for the following patterns

X[X]X
...X
...X which is also

...X
X[X]X
...X

average 2693 solutions [middle box is forced if valid]

and its opposite mate

X...X
......
X...X

which has 320000 solutions approx [equiv to B5B6B7B8]

we can find minimal simultaneous grids from these pairings easily - maybe these are the grids we should look in. We should aim for one without pairs in them - which is more than we can say for Gfroyles 17.

I am looking at Gfroyle grid as I type - and I am hoping something startling will turn up !

[Boxes 1278 = 245952 solutions][Boxes 34569 = 2925 solutions]

It is a hunch - and it is tempered by the fact that each grid has 9 of these combinations in it. So its a combination effect.

Maybe it will lead to nothing - but we need to cheer up Gfroyle ! and I know how determined Guenter is.

What we are doing is digging deeper into the mathematics governing these sudoku grids which is fasinating.

By the way G - I cant open p files

Thanks

Colin
Last edited by coloin on Sun Aug 07, 2005 7:38 pm, edited 1 time in total.
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby coloin » Sun Aug 07, 2005 11:08 pm

Pre-empting Guenter

No of ways to populate B1245

9!*9!*403.2^2 [ approx] = 21407557176262656

Tim did this some time ago
Tim wrote:
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

Interesting points to note here: This is a multiple of 5^2 but is not a multiple of 7^2

Brute forcing the entire grid ought to be feasible and would easily distribute.
Very rough ballpark estimate is 65000 CPU hours (allow a factor of 10 if you really want to go this path although I think there would be another factor of about 10 I could easily optimize out)

If anyone is interested in my code as it stands:

http://www.woodall.me.uk/sudoku_count_opt.c [not working]

Tim "


different nonzero solution-counts - upper limit 625 [maybe]

6,670,903,752,021,072,936,960 / 21411158320742400 = 311562 average solutions [assuming no zero solutions]

The B5689 [rather than the B12347] is going to be the more important variable I think

I await
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Gfroyles 17er secret

Postby coloin » Mon Aug 08, 2005 12:41 am

coloin wrote:Gfroyles 17er grid is starting to reveal itsself I fear
We need to do the 9 crunching exercises for it - I reckon one of them will be a very low combination
The tight box combinations will coincide with the "important" 6 boxes [which determine the grid"] in the 17er grid.

The "important" 6 -a formulation of these ones:
XX-
X-X
-XX

Do you follow ?



Follow this

Boxes
123
456
789

Aim for a lowest score in B1245 and a lowest score in B5689

put them together with the same box 5 and a valid box 3&7

This is the tightest grid - this is the Gfroyle 17 secret

In Gfroyles 17er grid
one of the 9 is 245952 [average is 311000]
It only needs one other low score [out of another four that intersect] to meld in and "autocomplete" the grid.


If Gfroyles 17 grid utilizes the two lowest B1245 / B5678 combinations - which combine - we are stuffed. If there is scope for improvement we have a fighting chance.

Rearranging the Boxes
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


We have 2 low solutions* intersecting - boxes 2187 & 7946

Rearranging again

132
798
465
we also have another low solution *1379 which intersects with 9865 [a below average count]

Rearranging again

123
789
456

1278 also intersects with 8956


I think this explains why the grid was so special -- Can we beat it ?

Is the 16er with 2 solutions better ?

I await the computation of the 6*6ers !

We will have the answer soon

Regards

Colin
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby dukuso » Mon Aug 08, 2005 9:22 am

>Yes each ganster will a significant expansion element - if
>they have the same number of solutions then that is ok. I
>might have thought it was as much as 6 ber B2 and 6 for B3 ie
>36 - obviously not thankfully.
>
>Are you allowing 3 permutations for the gangster in B1B4B7 ?

yes

>That would then be 3*3 permutations for each B12347

once we fix B123 we have lots of permutations

>I think the whole enumeration is possible this way - but the
>usefulness perhaps is if we can get the B12347 with the least
>number of solutions.

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




>find the 4 box [a four box
>square or the four corners - they are the same] with the
>minimum number of solutions.
>
>[If my program would do it I would guess the minimum might be
>4 392s !]

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

>Put them together and we have one tight mama !!!!! [Pairs not
>present ???]
>
>.............but the number of solutions for a corner box is
>more than 130000 [sadman stalls here][I see 300000 is your
>figure]
>.............of course if we really went for the knarliest
>grid we would do the big calculation first.........leave it
>for now[plan B]
>
>
>
>............this is not quite the final answer
>............every grid has 9 different "middle box" "crunching
>exercises" which are all different
>............so we are not quite there yet................
>
>I am glad we are making progress with this now - and we have
>got something out of it.............. .
>
>Gfroyles 17er grid is starting to reveal itsself I fear
>We need to do the 9 crunching exercises for it - I reckon one
>of them will be a very low combination.

you mean, we do the B12347 calculation 9 times for that grid,
with each of the boxes as B1 ?

>The tight box combinations will coincide with the "important"
>6 boxes [which determine the grid"] in the 17er grid.
>
>The 6 -a formulation of these ones:
>XX-
>X-X
>-XX
>
>Do you follow ?

why are they important ?


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


>dukuso wrote:
>there are essentially 2802 different B2B3B4B7
>sudokugrids
>with 1035 different nonzero solution-counts for the
>remaining
>6*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.
>
>
>
>Do you think this is useful in searching for a 16?
>
>And why?

I don't know. Note that I posted to the math-thread,
not the minimum-clue-thread.
It could be useful - see Coloins ideas.
But if I'd just only been interested in the 16,
then I'd probably gone another way.


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

>I hope it s useful
>
>We need to find the grid first.
>
>We need to know why Gfroyles 17ers have so many 17s in them -
>[I hope it isnt that he has just looked harder.]
>If they are special - we need to find out why - and then
>improve on it - to find a 16.

just speed up his calculation a bit by finding even more 17s ?!

>There are so many grids out there - I cant believe we have
>found the grid which has the best chance [but fails].

? just because there are so many, it's hard to find the best

>Anyhow - what we have done is to count the number of solutions
>for the following patterns
>
>X[X]X
>...X
>...X which is also

have we done

X.X
..X
..X

?

>...X
>X[X]X
>...X
>
>average 2693 solutions [middle box is forced if valid]

?

>and its opposite mate
>
>X...X
>......
>X...X

same as
XX.
XX.
...

>which has 320000 solutions approx [equiv to B5B6B7B8]




>By the way G - I cant open p files

what are p files ?

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

>Tim wrote:
>
>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

why 48*48 ? Well, 44*3 for B1+B2 are sufficient, and then I get
about 3.3 million extensions
We have to group these solutions into the 2802 classes to recompute N
this is possible, but I didn't do it.

>different nonzero solution-counts - upper limit 625 [maybe]
>
>6,670,903,752,021,072,936,960 / 21411158320742400 = 311562
>average solutions [assuming no zero solutions]
>
>The B5689 [rather than the B12347] is going to be the more
>important variable I think

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

>coloin wrote:
>
>Gfroyles 17er grid is starting to reveal itsself I fear
>We need to do the 9 crunching exercises for it - I
>reckon one of them will be a very low combination
>The tight box combinations will coincide with the
>"important" 6 boxes [which determine the grid"] in the
>17er grid.
>
>The "important" 6 -a formulation of these ones:
>XX-
>X-X
>-XX
>
>Do you follow ?
>
>
>
>Follow this - even better - a "Eureka" moment
>
>Boxes
>123
>456
>789
>
>lowest score in B1245 and a lowest score in B5678

you mean: B5689 ?

>put them together with the same box 5 and a valid box 3&7
>
>This is the tightest grid - this is the Gfroyle 17 secret

you can't just take 2802^2 combinations of B1245 and B5689 -
they interact. Well, we have at most 9! essentially different
B37s.


>In Gfroyles 17er grid
>one of the 9 is 245952 [average is 311000]
>It only needs one other low score [out of the four that
>intersect] to meld in and "autocomplete" the grid.
>The other boxes dont really matter - as long as they are valid
>- which they are.
>
>If Gfroyles 17 grid utilizes the two lowest B1245 / B5678
>combinations - which combine - we are stuffed. If there is
>scope for improvement we have a fighting chance.
>
>The other three intersecting 4 boxes are [solutions count]
>290744
>..........
>..........
>
>I await the computation !



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

>Follow this
>
>Boxes
>123
>456
>789
>
>Aim for a lowest score in B1245 and a lowest score in B5689
>
>put them together with the same box 5 and a valid box 3&7
>
>This is the tightest grid - this is the Gfroyle 17 secret
>
>In Gfroyles 17er grid
>one of the 9 is 245952 [average is 311000]
>It only needs one other low score [out of another four that
>intersect] to meld in and "autocomplete" the grid.
>
>
>If Gfroyles 17 grid utilizes the two lowest B1245 / B5678
>combinations - which combine - we are stuffed. If there is
>scope for improvement we have a fighting chance.
>
>Rearranging the Boxes
>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
>
>
>We have 2 low solutions* intersecting - boxes 2187 & 7946
>
>Rearranging again
>
>132
>798
>465
>we also have another low solution *1379 which intersects with
>9865 [a below average count]
>
>Rearranging again
>
>123
>789
>456
>
>1278 also intersects with 8956
>
>
>I think this explains why the grid was so special -- Can we
>beat it ?
>
>Is the 16er with 2 solutions better ?
>
>I await the computation of the 6*6ers !
>
>We will have the answer soon
>
>Regards
>
>Colin
>


you can give email and favourite file-format and I can send
files directly to you.

Guenter.
sterten@aol.com
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby coloin » Mon Aug 08, 2005 10:42 am

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 - we need to construct a similar but better one.
I will put a summary on the minimum thead.

This was the Plan A
"
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

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

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

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

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]

The boxes
12X
4X6
X89

The tight boxes unite around the central box
126X and X689 to define the grid.

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

Your tight 1960 grid probably has 8 other loose B1245s -I suppose we should prove that.
I will look at other average grids - but It takes my program half an hour each !

Have you the solution list for the 761 ?
That will be interesting.
Can we come up with a better combination of 9 ? That is all we have to do to get our grid.

Colin

txt files !
Last edited by coloin on Fri Aug 07, 2015 11:52 pm, edited 1 time in total.
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby Moschopulus » Mon Aug 08, 2005 1:36 pm

dukuso wrote:>Do you think this is useful in searching for a 16?
>
>And why?

I don't know. Note that I posted to the math-thread,
not the minimum-clue-thread.
It could be useful - see Coloins ideas.
But if I'd just only been interested in the 16,
then I'd probably gone another way.



I noted that you posted to math-thread.

What other way would you go if you were only interested in the 16?
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Mon Aug 08, 2005 3:32 pm

"you can't just take 2802^2 combinations of B1245 and B5689 -
they interact. Well, we have at most 9! essentially different
B37s. "

We are always dealing with valid completable sudoku grids.

There is a B12347 which has 1960 solutions

Take each of the 1960s of B5689 and find out which of these has the least solutions.

This is the one of the tightest grid looked at singularly. You have just done that !

But each grid has 9 of these computations
Each of these 9 has a different Box 5 when rearranged - so it is the combination of the 9 which is important in overall terms. Doesnt this help us in determining which grid to look in ?

Colin
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby Moschopulus » Mon Aug 08, 2005 3:39 pm

Why pick the partial grid with the fewest completions?

What makes you think this is more likely to have a 16?


Sorry if you said this already, I can't find it.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Mon Aug 08, 2005 4:32 pm

What we have done is attempted to answer why Gfroyles 17er grids have so many 17 grids in them.

Once we know why we will be able to attempt to come up with a "better" grid.

I have no idea if this is going to be possible - but I am sure Guenter [and Gfroyle and I] are going to try !

This is the first time anyone has come up with any sort of reason why Gfroyles grid is special - it looks no different from any other !

Analysis of "normal" grids of the combination of 9 solution totals will determine how close we are - and analysis of Guenter's 1960 combination tight grid will also be informative.

We should continue on the minimum posting.

Regards
Colin
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

PreviousNext

Return to General