Sudoku research page

Timo Mantere & Janne Koljonen
University of Vaasa


The test Sudoku instances used in the paper:
[1] Mantere, Timo and Janne Koljonen (2008). Solving and Analyzing Sudokus with Cultural Algorithms. In Proceedings of 2008 IEEE World Congress on Computational Intelligence (WCCI 2008), 1-6 June, Hong Kong, China, pages 4054-4061.(Presentation slides).

Benchmark Sudokus in tables 2 & 4 [1]
Difficulty ratingSudoku instance
abc
1s01a.txts01b.txts01c.txt
2s02a.txts02b.txts02c.txt
3s03a.txts03b.txts03c.txt
4s04a.txts04b.txts04c.txt
5s05a.txts05b.txts05c.txt
Es06a.txts06b.txts06c.txt
Cs07a.txts07b.txts07c.txt
Ds08a.txts08b.txts08c.txt
SDs09a.txts09b.txts09c.txt
Easys10a.txts10b.txts10c.txt
Mediums11a.txts11b.txts11c.txt
Hards12a.txts12b.txts12c.txt
GA-Es13a.txts13b.txts13c.txt
GA-Ms14a.txts14b.txts14c.txt
GA-Hs15a.txts15b.txts15c.txt
AI Escargots16.txt
Also available as zip file: sudokus.zip

Note that Sudokus named as Easy 1, Easy 2, Easy 3, Medium, Hard in the table 3 of [1] are respectively the same as s10a.txt, s10b.txt, s10c.txt, s11a.txt and s12a.txt in the previous tables.


The best results with the previous benchmark Sudokus with different methods:

Average number of trials needed (in 300 runs) to Solve benchmark Sudokus with different Evolutionary Algorithm methods
Difficulty ratingGenetic algorithm (GA)Cultural algorithm (CA)Ant colony optimization (ACO)
abcabcabc
112646344787 11416654732 7584304054
287653261812828 8187331161451526896105646387
3178417021435450 17123650684233269103767964497
4470577099471539 5008367691682291439486350862539
56681349802101691 628135462511418064800287524230263
E535252600 553271549406144391
C246568048650406 2633084761410342505188360871503
D281519904966681025051883608715033030639226416486
SD413450241184218102 422542222883207893801755248968306955
Easy11261297633401110928003520242320092846
Medium661831916275336563676199871538062343630757176084
Hard14190239088362709112322828167753025735256631758791247828
GA-E412845233100406545963057270129632603
GA-M3673519186326513380817242295362441630124107915
GA-H1636361043897858141936221046556014042880241603011479323
Total average:5680705518792810317368

Note! These numbers are with our program versions 15.3.2008 (GA and CA) and 30.4.2008 (ACO). The current versions are slightly more effective, e.g. ACO total with the latest version is approx. 8700000 trials (the version mentioned in the HK presentation slides above). Updated mumbers will appear here after they are published in some conference etc.


The time that Cultural algorithm needs previous benchmark Sudokus, average and maximum of 100 runs:

Average and maximum times [seconds] needed (of 100 runs) to Solve benchmark Sudokus with our latest CA version (16.6.2008)
Difficulty ratingAverageMaximum
abcabc
10.0550.0260.179 0.2900.1001.365
20.3081.0580.424 1.4927.6331.967
30.6062.1091.292 2.5118.4718.171
41.6322.8142.168 5.66719.52715.743
52.7592.0103.988 13.95915.51022.062
E0.0220.0110.021 0.0840.0310.085
C0.7622.3481.691 4.4148.7028.160
D7.6163.4892.135 26.32635.22210.932
SD12.4417.0535.980 129.39335.28826.444
Easy0.4280.0940.109 2.1120.6290.763
Medium2.2807.8742.164 9.76934.67711.861
Hard34.0153.43617.952 201.53118.10289.774
GA-E0.1580.1960.151 1.1120.9280.951
GA-M1.0310.8421.162 5.5845.6827.969
GA-H6.4053.69324.441 28.15228.357145.364
Average | Sum3.810171.428 22.2861002.866
Times are with 2.8 GHz quad-core 64-bit Intel Xeon processor (no parallel processing, only one core used). As a comparison 3.0 GHz Pentium4 needed approx. 50% more time.

Note! The minimum times are not so interesting, because the algorithm is heuristic and sometimes by luck it finds the solution even for the difficult Sudokus extremely fast. The longest minimum time was measured to be 0.075 seconds.

Our Java program runs with different Sudokus with slightly different speeds, Sudoku 1b runs slowest as 23557 trial/second and 8c runs fastest as 30265 trials/s. We think it due that, if there is less givens, the program is able to make swaps faster: 1b has 36 givens, the third largest number of the test set, and the other two are also among slow running Sudokus, 8c has 22 givens, which is tied lowest number in the test set. Average speed for solving all Sudokus above was 29133 trials/s (4994219 trials / 171.43s).

AI Escargot: This Sudoku proved to be most difficult for our method. It needed {18253, 1761291, 8514029} trials and {0.605, 59.911, 292.292} seconds to be solved as {min, mean, max}. Add it's times to the other 45 benchmark Sudokus and the total times needed for all 46 Sudokus would be in average 5.03 seconds (sum 231.4s) and sum of maximum times 1295s (avg. 28.2s). Unlike all the other benchmark Sudokus, this was never solved extremely fast.


The test Sudoku instances used in the paper:
[2] Mantere, Timo and Janne Koljonen (2007). Solving, Rating and Generating Sudoku Puzzles with GA. In 2007 IEEE Congress on Evolutionary computation – CEC2007, 25-28 September, Singapore, pages 1382-1389.

In table 1 they are the same as s01a.txt to s09a.txt above (9 instances, 1 to 9 only a:s).
In table 2 they are the same as s01a.txt to s09c.txt above (27 instances, 1 to 9, each a, b and c).
in table 5 Easy 1, Easy 2, Easy 3, Medium, Hard are respectively the same as s10a.txt, s10b.txt, s10c.txt, s11a.txt and s12a.txt above.


The test Sudoku instances used in the paper:
[3] Mantere, Timo and Janne Koljonen (2006). Solving and rating Sudoku puzzles with genetic algorithms. In E. Hyvönen, T. Kauppinen, J. Kortela, M. Laukkanen, T. Raiko, and K. Viljanen (eds.) New Developments in Artificial Intellingence and the Semantic Web - Proceedings of the 12th Finnish Artificial Conference STeP 2006, Helsinki University of Technology, Espoo, Finland, October 26-27, 2006, pp. 86-92.

In table 1 and figure 5 they are the same as s01a.txt to s09a.txt above (9 instances, 1 to 9 only a:s).


LINKS

Evolutionary algorithms course project work about Sudokus

Sudoku in Wikipedia

Automation engineering research group

Department of Electrical Engineering and Production Automation

University of Vaasa.



Updated 17.06.2008