Sudoku page

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 rating	Sudoku instance
a	b	c
1	s01a.txt	s01b.txt	s01c.txt
2	s02a.txt	s02b.txt	s02c.txt
3	s03a.txt	s03b.txt	s03c.txt
4	s04a.txt	s04b.txt	s04c.txt
5	s05a.txt	s05b.txt	s05c.txt
E	s06a.txt	s06b.txt	s06c.txt
C	s07a.txt	s07b.txt	s07c.txt
D	s08a.txt	s08b.txt	s08c.txt
SD	s09a.txt	s09b.txt	s09c.txt
Easy	s10a.txt	s10b.txt	s10c.txt
Medium	s11a.txt	s11b.txt	s11c.txt
Hard	s12a.txt	s12b.txt	s12c.txt
GA-E	s13a.txt	s13b.txt	s13c.txt
GA-M	s14a.txt	s14b.txt	s14c.txt
GA-H	s15a.txt	s15b.txt	s15c.txt
AI Escargot	s16.txt

*Corresponding solutions for these Sudokus*
Difficulty rating	Sudoku instance
Difficulty rating	a	b	c
1	s01a_s.txt	s01b_s.txt	s01c_s.txt
2	s02a_s.txt	s02b_s.txt	s02c_s.txt
3	s03a_s.txt	s03b_s.txt	s03c_s.txt
4	s04a_s.txt	s04b_s.txt	s04c_s.txt
5	s05a_s.txt	s05b_s.txt	s05c_s.txt
E	s06a_s.txt	s06b_s.txt	s06c_s.txt
C	s07a_s.txt	s07b_s.txt	s07c_s.txt
D	s08a_s.txt	s08b_s.txt	s08c_s.txt
SD	s09a_s.txt	s09b_s.txt	s09c_s.txt
Easy	s10a_s.txt	s10b_s.txt	s10c_s.txt
Medium	s11a_s.txt	s11b_s.txt	s11c_s.txt
hard	s12a_s.txt	s12b_s.txt	s12c_s.txt
GA-E	s13a_s.txt	s13b_s.txt	s13c_s.txt
GA-M	s14a_s.txt	s14b_s.txt	s14c_s.txt
GA-H	s15a_s.txt	s15b_s.txt	s15c_s.txt
AI Escargot	s16_s.txt

Also available as in one zip file: solutions.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 rating	Genetic algorithm (GA)			Cultural algorithm (CA)			Ant colony optimization (ACO)
Difficulty rating	a	b	c	a	b	c	a	b	c
1	1264	634	4787	1141	665	4732	758	430	4054
2	8765	32618	12828	8187	33116	14515	26896	10564	6387
3	17841	70214	35450	17123	65068	42332	6910	37679	64497
4	47057	70994	71539	50083	67691	68229	143948	63508	62539
5	66813	49802	101691	62813	54625	114180	64800	287524	230263
E	535	252	600	553	271	549	406	144	391
C	24656	80486	50406	26330	84761	41034	250518	83608	71503
D	281519	90496	66810	250518	83608	71503	303063	92264	16486
SD	413450	241184	218102	422542	222883	207893	801755	248968	306955
Easy	11261	2976	3340	11109	2800	3520	2423	2009	2846
Medium	66183	191627	53365	63676	199871	53806	23436	307571	76084
Hard	1419023	90883	627091	1232282	81677	530257	3525663	175879	1247828
GA-E	4128	4523	3100	4065	4596	3057	2701	2963	2603
GA-M	36735	19186	32651	33808	17242	29536	24416	30124	107915
GA-H	163636	104389	785814	193622	104655	601404	288024	160301	1479323
Total average:	5680705			5187928			10317368

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 rating	Average			Maximum
Difficulty rating	a	b	c	a	b	c
1	0.055	0.026	0.179	0.290	0.100	1.365
2	0.308	1.058	0.424	1.492	7.633	1.967
3	0.606	2.109	1.292	2.511	8.471	8.171
4	1.632	2.814	2.168	5.667	19.527	15.743
5	2.759	2.010	3.988	13.959	15.510	22.062
E	0.022	0.011	0.021	0.084	0.031	0.085
C	0.762	2.348	1.691	4.414	8.702	8.160
D	7.616	3.489	2.135	26.326	35.222	10.932
SD	12.441	7.053	5.980	129.393	35.288	26.444
Easy	0.428	0.094	0.109	2.112	0.629	0.763
Medium	2.280	7.874	2.164	9.769	34.677	11.861
Hard	34.015	3.436	17.952	201.531	18.102	89.774
GA-E	0.158	0.196	0.151	1.112	0.928	0.951
GA-M	1.031	0.842	1.162	5.584	5.682	7.969
GA-H	6.405	3.693	24.441	28.152	28.357	145.364
Average \| Sum	3.810	171.428		22.286	1002.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).