The New Sudoku Players' Forum

[RW]

Still a bit curious on this matter, I spent this day checking out the online java tutorial, and now I have a simple (but probably quite clumsy) program that reads multiple grids from a file and outputs statistics about the entwining. Already found some interesting results. Here's 15 random grids by SudoCue:

Code: Select all

698415372517283496324697815972534168431876259865129734289351647156742983743968521
2-permutable sets: 20
4-permutable sets: 9
8-permutable sets: 6
16-permutable sets: 1
Total amount of 2-digit unavoidble sets: 60

675481329984372156312569478598146732423758961167923584736814295851297643249635817
2-permutable sets: 19
4-permutable sets: 13
8-permutable sets: 4
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 57

251398674463715298978462513197684352546123987382579461629837145714256839835941726
2-permutable sets: 21
4-permutable sets: 10
8-permutable sets: 5
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 56

842579136963124578571386249456291783128437965397865412615948327739612854284753691
2-permutable sets: 18
4-permutable sets: 16
8-permutable sets: 2
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 56

478592613612473859539618274751346982894725361326981745945837126183264597267159438
2-permutable sets: 19
4-permutable sets: 13
8-permutable sets: 4
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 57

536729841987514263124863759869132574713485692245697138498256317672341985351978426
2-permutable sets: 19
4-permutable sets: 14
8-permutable sets: 3
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 56

648923157195487236273165498827319564319546872564872319786251943431798625952634781
2-permutable sets: 25
4-permutable sets: 6
8-permutable sets: 5
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 52

279153648148976235653482197537649812891327564426815379362594781784261953915738426
2-permutable sets: 17
4-permutable sets: 14
8-permutable sets: 5
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 60

975321846468759321123864975891647532647532189532918764284175693716493258359286417
2-permutable sets: 24
4-permutable sets: 11
8-permutable sets: 1
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 49

614598372732641589598372641841736925359214867267985413475163298183429756926857134
2-permutable sets: 21
4-permutable sets: 12
8-permutable sets: 2
16-permutable sets: 1
Total amount of 2-digit unavoidble sets: 55

731698452958243617462175938579462183846351729213789546687524391325916874194837265
2-permutable sets: 22
4-permutable sets: 12
8-permutable sets: 1
16-permutable sets: 1
Total amount of 2-digit unavoidble sets: 53

439627185752198643618435279295784361187369452364251798523976814971843526846512937
2-permutable sets: 17
4-permutable sets: 16
8-permutable sets: 3
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 58

483725691196843527257691843729386415841952736365417982932564178578139264614278359
2-permutable sets: 22
4-permutable sets: 13
8-permutable sets: 1
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 51

451786329327945186896312745173528694564179238289634517915863472632497851748251963
2-permutable sets: 20
4-permutable sets: 9
8-permutable sets: 7
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 59

342798165517634982896512743764985231185326497239147856478253619651479328923861574
2-permutable sets: 20
4-permutable sets: 14
8-permutable sets: 2
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 54

To compare the 5 most fertile grids for 17s, found here:

Code: Select all

639241785284765193517983624123857946796432851458619237342178569861594372975326418
2-permutable sets: 28
4-permutable sets: 8
8-permutable sets: 0
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 44

873692451649517328521348976132976845498125637765483192954761283386254719217839564
2-permutable sets: 24
4-permutable sets: 9
8-permutable sets: 2
16-permutable sets: 1
Total amount of 2-digit unavoidble sets: 52

438926751796451382251738469123687945647593218589214673362175894914862537875349126
2-permutable sets: 21
4-permutable sets: 11
8-permutable sets: 4
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 55

236195478487263159591487632123759864759648321648321795314972586872516943965834217
2-permutable sets: 31
4-permutable sets: 3
8-permutable sets: 1
16-permutable sets: 1
Total amount of 2-digit unavoidble sets: 44

481972365296534178537168942123697584658241793749385216314726859965813427872459631
2-permutable sets: 25
4-permutable sets: 9
8-permutable sets: 2
16-permutable sets: 0
Total amount of 2-digit unavoidble sets: 49

It's quite obvious that the average amount of 2-perms is much higher for the grids with many 17s. Also, the average amount of 2-digit unavoidables is lower.

My problem now is that my little program only takes solved grids and the big collections available (gfroyle's known 17s, Ruud's 50k...) are unsolved grids. Is there a program available that reads multiple grids and outputs the solutions to a file? I'm not that interested in writing a brute force solver myself...

RW

[r.e.s.]

Is there a program available that reads multiple grids and outputs the solutions to a file?

gsf's program will do that ...

http://www.research.att.com/~gsf/sudoku/sudoku.html
http://www.research.att.com/~gsf/man/man1/sudoku.html

EDIT: See the related posting below by gsf.

[Moschopulus]

My problem now is that my little program only takes solved grids and the big collections available (gfroyle's known 17s, Ruud's 50k...) are unsolved grids. Is there a program available that reads multiple grids and outputs the solutions to a file? I'm not that interested in writing a brute force solver myself...

There is a solver program (named "solver") you can download here
http://www.maths.nuim.ie/staff/gmg/sudoku/

Go about half way down the page to see the syntax, or type solver with no parameters. This solver was written by dukuso.

Interesting data.

[r.e.s.]

[cancelled]

[daj95376]

gsf posted a great little backtracking solver to the Programmer's Forum. It's simple to use ... and ... will also check a puzzle for multiple solutions. It's written in C and runs in command-line mode. It can be located here .

I have a tweaked version of the source that allows me to use its core routines in my puzzle generator to check for uniqueness.

[r.e.s.]

gsf posted a great little backtracking solver to the Programmer's Forum. It's simple to use ... and ... will also check a puzzle for multiple solutions. It's written in C and runs in command-line mode.

Is it different than gsf's program that I linked to above?

[daj95376]

gsf posted a great little backtracking solver to the Programmer's Forum. It's simple to use ... and ... will also check a puzzle for multiple solutions. It's written in C and runs in command-line mode.

Is it different than the one I gave links to above?

Yes, much simpler and probably tons quicker!

[r.e.s.]

Thanks, but I'd rather not have to compile it. Also, it would be nice to know for sure beforehand that it's much faster than his compiled version that I linked to, which likewise handles multiple solutions, etc.

[gsf]

Thanks, but I'd rather not have to compile it. Also, it would be nice to know for sure beforehand that it's much faster than his compiled version that I linked to, which likewise handles multiple solutions, etc.

sudoku(1) --man has this section:

Code: Select all

PERFORMANCE
  The solution rate for the best on average options -dqFN on a collection
  of posted and generated puzzles is ~1000 puzzles/second/Ghz, the -g full
  grid (81 clues) generation rate is ~1400 puzzles/second/Ghz, and the
  -g -m1 -qFN generation rate is ~75 puzzles/second/Ghz.  sudocoup(1),
  coded for speed, solves ~7000 puzzles/second/Ghz.  sudocoo(1), coded for
  simplicity, is in between and is more sensitive to input grid variations.


sudoku(1) is technique based -- by default will run slower than brute force
attempting to apply techniques instead of the typically faster backtracking
(at least for 9x9 sudoku); so use -d -qFN for best performance, especially
when you don't care how the solution is obtained

sudocoup(1) is an NxN, N<=64 forward checking backtrack solver
it has a different grid data structure that propagates singles with each
placement and/or elimination

sudocoo(1) is the tiny backtracker that does well on most 9x9, but
deteriorates quickly for higher order sudoku

the timings may vary wildly for specially constructed collections

[r.e.s.]

gsf,

Thanks for correcting my poor understanding of the command-line usage -- I should have simply pointed to your pages. (I'll edit my previous posts accordingly.)

[gsf]

Thanks for correcting my poor understanding of the command-line usage -- I should have simply pointed to your pages. (I'll edit my previous posts accordingly.)

--man is not an easy read
all the info is there, but it takes work to match options with semantics
in the grand unix style I stopped adding features when the option letters ran out
so now the casual reader can catch up

there are some neat things in there
you can program the rating expression on the command line
you can pick and choose techniques in any grouping/order
there are option combinations to match inferior and ulterior thread step counts
you can filter puzzles by command line expressions on techniques applied
and like others mentioned, it can batch process and reformat

[RW]

Thanks for the suggested programs. I used gsf's program to solve some collections and ran them through my program. Found some confirmations and a few suprises also. First Ruud's 50k:

Code: Select all

50000 grids processed

         2-perm: 4-perm: 8-perm: 16-perm:
0:       0       1       1675    39014
1:       0       6       6253    9653
2:       0       12      11035   1231
3:       0       35      12512   92
4:       0       141     9722    10
5:       0       313     5396    0
6:       0       770     2399    0
7:       0       1521    768     0
8:       0       2787    210     0
9:       0       4590    25      0
10:      0       6234    4       0
11:      0       7357    1       0
12:      0       7608    0       0
13:      20      6551    0       0
14:      57      5147    0       0
15:      240     3399    0       0
16:      665     1951    0       0
17:      1859    931     0       0
18:      3751    417     0       0
19:      6256    156     0       0
20:      8192    51      0       0
21:      8772    18      0       0
22:      7615    4       0       0
23:      5602    0       0       0
24:      3464    0       0       0
25:      1890    0       0       0
26:      941     0       0       0
27:      423     0       0       0
28:      156     0       0       0
29:      65      0       0       0
30:      21      0       0       0
31:      8       0       0       0
32:      3       0       0       0
33:      0       0       0       0
34:      0       0       0       0
35:      0       0       0       0
36:      0       0       0       0

Average: 21.02   11.66   3.07    0.25

Average amount of 2-digit unavoidable sets: 54.0

From the table you can read how many puzzles had the different amounts of 2-, 4-, 8- and 16-permutable pairs (20 puzzles had exactly 13 2-permutable sets, 57 had 14 2-permutable sets etc.).Then gfroyle's 17s:

Code: Select all

36628 grids processed

         2-perm: 4-perm: 8-perm: 16-perm:
0:       0       3       4305    33192
1:       0       6       9206    3274
2:       0       32      10373   157
3:       0       109     7315    4
4:       0       200     3599    1
5:       0       564     1382    0
6:       0       1130    359     0
7:       0       2063    82      0
8:       0       3184    7       0
9:       0       4428    0       0
10:      0       5126    0       0
11:      0       5337    0       0
12:      0       4925    0       0
13:      0       3803    0       0
14:      2       2754    0       0
15:      17      1635    0       0
16:      80      794     0       0
17:      265     353     0       0
18:      798     128     0       0
19:      1803    44      0       0
20:      3211    9       0       0
21:      4508    1       0       0
22:      5335    0       0       0
23:      5268    0       0       0
24:      4827    0       0       0
25:      3943    0       0       0
26:      2780    0       0       0
27:      1783    0       0       0
28:      1047    0       0       0
29:      525     0       0       0
30:      275     0       0       0
31:      105     0       0       0
32:      43      0       0       0
33:      4       0       0       0
34:      5       0       0       0
35:      1       0       0       0
36:      3       0       0       0

Average: 23.06   10.76   2.07    0.10

Average amount of 2-digit unavoidable sets: 51.0

Note that I did not remove duplicate grids, certain grids have been counted several times.

The average amount of 2-permutable sets is higher for the 17s, but not as much as I had expected. I was suprised that 2 different grids with only 14 2-permutable sets had 17s in them (first of these #2185). It's also interesting to see a grid with four 16-permutable sets and a 17 (#36567). Looking at the amount of grids with 26 or more 2-permutable sets, it's quite obvious that 17s are more common in those grids, 1617/50000 = 3.5% of the random grids are in that area, while 6571/36628 = 18% of the 17s can be found there.

Among the 50000 random grids the lowest amount of fully entwined pairs is 13 - the grids we found in this thread with 9 such pairs seem to be extremely rare. A good thing with searching for these is that it's very fast, even though I haven't made any effort to maximize the efficiensy of my program, it calculated the data for 50000 puzzles in a few seconds. I'm now trying to figure out how I could have gsf's program create a file with a few million random grids and search for more extreme values within these grids. But, like r.e.s., I have some problems with the command line usage as well... any help? If someone can tell me how to get rid of the duplicates among the 17s I would also appreciate it.

Any other thoughts about these results?

btw. I also scanned the top1465 and the results were very similar to Ruud's50k:

Code: Select all

         2-perm: 4-perm: 8-perm: 16-perm:
50k:
Average: 21.02   11.66   3.07    0.25
top1465:
Average: 21.20   11.54   3.01    0.24

The minimum amount of 2-permutables in top 1465 was 14 (2 grids), maximum 32 (1 grid).

RW

[gsf]

I'm now trying to figure out how I could have gsf's program create a file with a few million random grids and search for more extreme values within these grids. But, like r.e.s., I have some problems with the command line usage as well... any help? If someone can tell me how to get rid of the duplicates among the 17s I would also appreciate it.

do you want solution grids (no holes) or puzzles?

you can convert to (a) canonical form to get rid of dups and just work on the canonical forms

Code: Select all

sudoku -f%#0c sudoku17.dat | sort -u > sudoku17.can


[RW]

do you want solution grids (no holes) or puzzles?

Solution grids. I don't wanna have to solve the few million puzzles...

RW

[gsf]

Solution grids. I don't wanna have to solve the few million puzzles...

for 1,000,000:

Code: Select all

sudoku -g -n1000000 -T0x80 -f%v > sol.dat