Structures of the solution grid

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

Postby RW » Thu Aug 03, 2006 7:11 pm

Thank you gsf for the instructions!

This is really easy, generating and analyzing 1.4million grids in less than 30 minutes!:) Here's my output:
[Edit: 17min actually.]

Code: Select all
1400000 grids processed

         2-perm: 4-perm: 8-perm: 16-perm:
0:       0       20      37619   1032392
1:       0       93      147400  312434
2:       0       364     285009  49373
3:       0       1029    344518  5355
4:       0       3048    289232  416
5:       0       8144    177977  28
6:       0       19655   80939   2
7:       0       42041   27746   0
8:       0       78005   7573    0
9:       0       124475  1615    0
10:      1       171319  311     0
11:      1       204269  49      0
12:      78      210873  11      0
13:      474     187698  1       0
14:      2220    145691  0       0
15:      8660    98007   0       0
16:      26166   57091   0       0
17:      63678   28591   0       0
18:      124287  12632   0       0
19:      194303  4864    0       0
20:      243157  1557    0       0
21:      244787  428     0       0
22:      200878  86      0       0
23:      137661  16      0       0
24:      80342   4       0       0
25:      41813   0       0       0
26:      19003   0       0       0
27:      8055    0       0       0
28:      2947    0       0       0
29:      1059    0       0       0
30:      302     0       0       0
31:      99      0       0       0
32:      25      0       0       0
33:      2       0       0       0
34:      2       0       0       0
35:      0       0       0       0
36:      0       0       0       0

Average: 20.71   11.73   3.25    0.31

Average amount of 2-digit unavoidable sets: 55.0

Smallest amount of 2-digit unavoidable sets (38) was found in grid #1365508:
538941627912367458746285931374128596281596374659734812897452163163879245425613789

Largest amount of 2-digit unavoidable sets (73) was found in grid #1380741:
234576198596281734178349562412765983965832417783194625347918256821657349659423871

Smallest amount of 2-permutable sets (10) was found in grid #1082570:
239168745518472693647953218926345871153827469784691352875216934391784526462539187

Largest amount of 2-permutable sets (34) was found in grid #664700:
658174923947532816132968457283416579416795238579823164724381695891657342365249781

Largest amount of 4-permutable sets (24) was found in grid #893768:
863249715197563482425187396251398647976412538384675129742936851619854273538721964

Largest amount of 8-permutable sets (13) was found in grid #1146479:
697258413538416297412739658285697341164583729973124865729341586341865972856972134

Largest amount of 16-permutable sets (6) was found in grid #310236:
739124586562873419184695372647519823813742695925368147451237968298456731376981254


Notice the nice triangular shape!:)

The average value is a bit lower than in Ruud's 50k, could this be because of some differences in the generating process? This time only 2.2% of the grids have >25 2-permutable sets. I'll try to compare the grids with >30 2-perms to the 17-grids to see if some of them can be found there.

The collection also has a 11 and a 10, but still no randomly created 9, they seem to be very rare... so does the 35s and the 36s.

RW
Last edited by RW on Fri Aug 04, 2006 11:29 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby RW » Thu Aug 03, 2006 8:24 pm

And the next 1.4M broke some records. This time there was sixteen 11s, three 10s, no 9s but one 8!! Also found one with 25 4-permutable pairs and one with seven 16-permutables:

Code: Select all
Smallest amount of 2-permutable sets (8) was found in grid #772251:
958147326467293815213568794549781632826359147371426958195874263732615489684932571

Largest amount of 4-permutable sets (25) was found in grid #1270790:
324681975876539124591427638687142593913875246245396781132958467459763812768214359

Largest amount of 16-permutable sets (7) was found in grid #948667:
693845127578126349124793856985671432346582791712934685251468973439217568867359214


Let's see how low we can go with the 2-perms.

I should also mention that the average amounts of the different permutables was exactly the same (with 2 decimals) for the first 1.4M as for the second 1.4M created by gsf's program. Confirms that at least gsf's method produces that average.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Fri Aug 04, 2006 11:15 am

Great work........

we had 4 grids with 27 unentwined pairs [non-2-perms] plus 9 2-perms

This
Code: Select all
Smallest amount of 2-permutable sets (8) was found in grid #772251:
958147326467293815213568794549781632826359147371426958195874263732615489684932571
This of course breaks the record at 28 unentwined pairs.
Code: Select all
958147326
467293815
213568794
549781632
826359147
371426958
195874263
732615489
684932571

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


Regards C
coloin
 
Posts: 1715
Joined: 05 May 2005

Postby RW » Fri Aug 04, 2006 4:04 pm

Thanks coloin. After looking at 18.2 million grids I've found only 6 grids with less than ten 2-perms. Four 9s and one more 8:

Code: Select all
981274635326859471475613982718432596632985147594167328263598714857341269149726853


The puzzle I mentioned with seven 16-perms is still the only one that has reached that amount. Btw it's a MCN 16. I've noticed that high MCNs are usually connected with high amounts of 16-perms (as expected), I found several MCN 15 grids among the grids with six 16-perms.

I've found only one grid so far that has a higher total amount of 2-digit unavoidables than the 9-entwiner that I created earlier, this grid has 74 2-digit unavoidables:

Code: Select all
384217965512936478967458321841672593725349186693185247259763814136894752478521639


Also found some new records, two grids with 14 8-permutable pairs:

Code: Select all
852971436437628951169435728974152683618743592523896147295317864746289315381564279
564132789317896524289475316743281695691357842825964173156749238978523461432618957


I've found only six grids so far with 25 4-permutable pairs and none with 26 4-perms, so this one came as a real suprise in the last 1.4M set I analyzed: 27 4-permutable pairs!

Code: Select all
153496278267831549894572631789213456432658197615947823521369784978124365346785912


This makes me believe even more that there should be grids with less than 8 2-perms. Also, the 18.2 million grids have contained only 10 grids with 34 2-perms and none with more, but we know that there is at least one 35 and one 36 (both have 17 clue puzzles).

I've analyzed the grids in sets of 1.4 million puzzles. The average amount of two perms has been between 20.71 and 20.72 for all sets. The average amount of >30 2-perms in a set is around 120 grids and the average amount of <13 2-perms is also around 120.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby RW » Sat Aug 05, 2006 6:55 pm

I made a little modification to my program so that it collects grids with MCN 16. It's quite simple, whenever there's four or more 16-perms it checks if there's four disjoint sets, if there is then it has a minimum MCN of 16. Turned out they're not very rare, have over 600 of them already. From this I do believe that there's several grids with no 19s, might even be some grid with no 20, or is this already proven impossible?

I also have a nice collection of a few thousand grids with 31 or more 2-perms. I think these could be a good source for finding more 17s, if I had a good and fast way to search them.

And here comes the 7!

Code: Select all
159764283378219546642835971425387169936142758817596324264953817783421695591678432


I'll let you know if I find anything else interesting.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Wed Aug 09, 2006 10:12 pm

Probing search........just reaffirming to all the vast amount of grids out there.....
RW wrote:I made a little modification to my program so that it collects grids with MCN 16. It's quite simple, whenever there's four or more 16-perms it checks if there's four disjoint sets, if there is then it has a minimum MCN of 16. Turned out they're not very rare, have over 600 of them already. From this I do believe that there's several grids with no 19s, might even be some grid with no 20, or is this already proven impossible?

There may well be some grids without a 19 in the 600.....which increases the likeihood of an MCN 17 - if one can possibly exist. I dont think there is a grid without a 20 [not proven]....in the grids [3 so far !] which dont have a 19,20s wernt difficult to find.
RW wrote:I also have a nice collection of a few thousand grids with 31 or more 2-perms. I think these could be a good source for finding more 17s, if I had a good and fast way to search them.


Indeed if we were to find a 17 in one of these it would be a turnup, Before I would start looking I would check it was definitely a different grid from one from Gfroyles list. Post your best shot !

RW wrote:And here comes the 7!


remarkable.......C
coloin
 
Posts: 1715
Joined: 05 May 2005

Postby RW » Thu Aug 10, 2006 9:35 pm

coloin wrote:Indeed if we were to find a 17 in one of these it would be a turnup, Before I would start looking I would check it was definitely a different grid from one from Gfroyles list. Post your best shot !


I haven't quite managed to sort out duplicates yet, for some reason the '-u' parameter gsf suggested doesn't work. But I've sorted the grids with 17s in canonical form and filtered out the 6 grids with 34 or 35 2-perms, and none of them match any of the puzzles I found. In 25 million grids there's been only one 35 and twenty 34s:

Code: Select all
34 2-permutable pairs:
123456789456789123789132546238975461594621378671843952367294815815367294942518637
123456789456789123789132564274918635615243897938675412367824951591367248842591376
123456789456789123789132564294861357537924618861573492372695841648217935915348276
123456789456789123789231564235148697678592431914673258367824915591367842842915376
123456789456789123789231564248173695637925841915648237374562918592814376861397452
123456789456789132789213645215378496637945821894621357378562914561894273942137568
123456789456789132789213645237194856594867321618532497375941268862375914941628573
123456789456789132789213645241578396638194527975632418317925864594861273862347951
123456789456789132789213645247391856861572394935864217378925461514637928692148573
123456789456789132789213645248567913375194268691832574537628491862941357914375826
123456789456789132789213645267894513534162978891537264375628491618945327942371856
123456789456789132789213645268375914375194268941862573537941826612538497894627351
123456789456789132789213645271538496345697821698124357537941268862375914914862573
123456789456789132789213645294537816537861294861942357342175968678394521915628473
123456789456789132789213645295864371374192568861537924537928416612345897948671253
123456789456789132789213654237195468591864273648327915375941826814632597962578341
123456789456789132789231546234178695567392814891564327348627951615943278972815463
123456789456789132789231546268317954347592618915648273572863491631974825894125367
123456789456789231789132465248513976315967824967824153592348617671295348834671592
123456789456798213789213564234581976598367421617924835345672198862149357971835642

35 2-permutable pairs:
123456789456789132789213645264835917537194826891627453378561294615942378942378561


The grids have mcn 8-10. As I said, I don't know any good way to search them for 17s. Checker is of no use, even with two clues selected it estimates 144 days for an exhaustive search on (part of) the 35. I did some manual clue removing on the 35 and easily found several 19s (!), I've never before even managed to make a 20 manually...

Any good programs out there that can search given grids for 17s while I drink coffee and play the piano?

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Thu Aug 10, 2006 10:42 pm

RW wrote:I haven't quite managed to sort out duplicates yet, for some reason the '-u' parameter gsf suggested doesn't work.

-u verifies that there is one solution
I may have misread the meaning of "duplicate" or was mixing guitar and typing
remind me again of the problem statement (removing duplicates)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Thu Aug 10, 2006 11:01 pm

gsf wrote:remind me again of the problem statement (removing duplicates)


I have a big collection of solved grids and I wish to verify that no grid appears several times in that collection. And if there would be multiple instances of equivalent grids, I wish to remove all but one.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Thu Aug 10, 2006 11:26 pm

RW wrote:
gsf wrote:remind me again of the problem statement (removing duplicates)

I have a big collection of solved grids and I wish to verify that no grid appears several times in that collection. And if there would be multiple instances of equivalent grids, I wish to remove all but one.

aha, the -u might have been for sort, not sudoku
if you don't mind working with (a, not the) canonical grids
Code: Select all
sudoku -f%c *.dat | sort -u > unique.can

if you want to retain the original grids
Code: Select all
sudoku -f'%c %v' *.dat |  sort -k1,1 -u | sed 's/.* //' > unique.dat
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Fri Aug 11, 2006 12:35 pm

RW wrote:
Code: Select all
35 2-permutable pairs:
123456789456789132789213645264835917537194826891627453378561294615942378942378561
Code: Select all
Two 18s:
000400009056700000000003000060000000007000800000020403300001090000000070000008060
000400009056700000000003000060000900007000800000020403300001000000000070000008060
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby RW » Fri Aug 11, 2006 6:36 pm

gsf wrote:aha, the -u might have been for sort, not sudoku
if you don't mind working with (a, not the) canonical grids
Code: Select all
sudoku -f%c *.dat | sort -u > unique.can

Yes, I've tried that before but I only get:
Code: Select all
-uThe sysem cannot find the file specified.

and an empty file named "unique.can". If I leave the '-u' I get the grids sorted in canonical form, no duplicates removed.

Ocean wrote:Two 18s:

Good work, here's two more 35s to try your luck on:
Code: Select all
123456789456789123789132564275364918638591472914278356392617845561843297847925631
123456789456789132789231645291864573347915268568327914632578491814692357975143826


RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Sat Aug 12, 2006 5:22 am

RW wrote:
gsf wrote:aha, the -u might have been for sort, not sudoku
if you don't mind working with (a, not the) canonical grids
Code: Select all
sudoku -f%c *.dat | sort -u > unique.can

Yes, I've tried that before but I only get:
Code: Select all
-uThe sysem cannot find the file specified.

and an empty file named "unique.can". If I leave the '-u' I get the grids sorted in canonical form, no duplicates removed.

running a windows command line I presume
-u is the unix unique option
just check the windows man ... rats no man ... google ... aha /option ... no unique option ... no uniq command
well, anyone know if out of the box windows can uniq a sorted file?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby daj95376 » Sat Aug 12, 2006 8:29 am

Windows does not support Unix utilities. However, there are a few freeware locations where they can be obtained. If you go here, then you'll find a freeware set of basic Unix utilities -- Cons109.exe (a self-extracting ZIP file) -- for Windows 95/98 (and probably higher). They run in command-line mode and are perfect for the examples you use.

Note #1: Windows does have a sort routine but it isn't compatible with Unix arguments. I renamed sort.exe (from Cons109.exe) to sortunix.exe and use it all the time.

Note #2: I updated my PATH declaration in Autoexec.bat to include the folder where I stored these utilities. I'm not sure if Windows XP supports Autoexec.bat anymore.

Good luck!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Sat Aug 12, 2006 12:42 pm

daj95376 wrote:Windows does not support Unix utilities.

I hope my sans smileys sarcasim wasn't too subtle
too bad they stopped at stealing pipe, io redirection and more(1)
grab this unique.exe
and add it to the sort pipeline (assuming windows can handle pipeline order > 2)
Code: Select all
sudoku ... | sort | unique > unique.can

check uwin for a thourough treatment of unix on windows
there's also cygwin, but I can't vouch for that (more sarcasim)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General