Table of Contents
Regression testing is always a difficult and demanding task if it cannot be fully automated. One problem when testing for a great number of techniques is to find a great variation of test cases that can be handled automatically.
Some effort has been made in the past to collect libraries of test cases (or libraries that can be used as test cases), e.g. Ruud's Benchmark Sudoku List, Mike Barker's zoo, RW's The Effortless Extremes thread or tarek's A Pure Jellyfish Collection (and this list is of course incomplete).
Most of them cannot be used for autmated testing however, because they depend on solver strategy or because they are in different formats. I have therefore collected my own set of test cases and developed a simple format, that allows easy testing. Most test cases have been found using HoDoKu, but many have been taken from forums and libraries all over the internet. Since there are so many (over 1000 in version 1.0 of the regression test library) references are not supplied for every sudoku.
The purpose of this library is to collect as many test cases for different human style solving techniques as possible. Every test case uses exactly one line and tests one technique for a given set of candidates. The only restriction for a valid test case is, that no other instance of the tested technique for that set of candidates exists, that leads to a different placement or to different eliminations.
The library format has the additional advantage that it contains a PM that preserves the difference between givens and set cells (and all in one line).
Special thanks to MaNik-e Team for their help in coding the actual test routine.
HoDoKu Library Format
A test case consists of one line with seven fields enclosed and seperated by ":". Format:
- An alphanumeric string denoting the technique (values see the library file itself). For some techniques variants are defined. A variant starts with a dash after the code for the base technique followed by a number. Variants can of course be ignored. If the variant consist of a single 'x', the test case is a fail case: No instance of that technique must be found.
- The candidate (or candidates), for which the technique is applied (see below)
- The givens of the sudoku; a '+' sign before a digit means, that that value is not a given, but has already been placed (optional)
- <deleted candidates>
- Candidates, that have to be deleted after placing the givens; <givens> and <deleted candidates> together are equivalent to a PM, but with the advantage, that the difference between givens and placed cells can be preserved (format see below)
- Candidates, that are eliminated by <technique> in the test PM, if any (format see below)
- Cells that can be placed by <technique> in the test PM, if any (format see below)
- Can contain additional information specific to a step. The following extra values are defined:
- Chains/Loops: The length of the chain/loop in number of inferences
Format for candidates/eliminations/placements
<line> and <col> are in the range of 1 to 9; if an entry contains more that one instance, they are separated by blanks.
Example: ":436 257:" means "r3c6<>4, r5c7<>2"
<eliminations> and <placements> can't be set in the same test case.
The contents of <candidates> depends on the technique:
- For Singles, Forcing Chain/Net Verities: The candidate, that can be placed
- Nice Loops/AIC, Forcing Chain/Net Contradictions, ALS, SDC: The candidates that can be eliminated
- All other moves: the candidates used in the move
Create a grid from the string
(everything from <givens>, that has no '+' sign - the real givens) Now place the cells, that are given by the following string:
(everything from <givens> with a '+' sign); optionally you can just ignore the signs and place:
there are no additional candidates to delete;
now look for a Naked Single for candidate 8 in the PM given by <givens> and <deleted candidates>; you should be able to find one that places 8 in r2c9.
Example 2 (the string below must go on one line only)
:0603:3:14+8..+9+72+5.+3...89.697+6....38.+61......3+2.8.56...9......2.5+9+186....+8+3....61+6+1...35+89:224 524 225 525 135 455 755 458 758 165 168 771 284 484 784 285 485 785:364 365::
Place all digits from <givens> as described above; after that eliminate:
r2c4<>25, r2c5 <>25, r3c5<>1, r5c5<>47, r5c8<>47, r6c5<>1, r6c8<>1, r7c1<>7, r4c8<>247, r5c8<>247;
now look for a Uniqueness Test Type 4 in the given PM, that eliminates candidates for digit 3; you should find one, that eliminates 3 from r6c4 and r6c5.
The complete library:
The HoDoKu exemplar library is a loose collection of sudokus, that exemplify specific techniques. Most of these puzzls have been calculated using HoDoKu's batch creation mode (see Batch creation of sudokus in the User Manual).
Some examples only work if the solver options or the step hierarchy is changed, very few examples are broken and dont work at all.
Copyright © 2008-12 by Bernhard Hobiger
All material on this page is licensed under the GNU FDLv1.3.