Assessing the difficulty of Sudoku puzzles provokes endless debate because there is no universally accepted scheme. Puzzles appearing elsewhere are often rated using terms like "easy", "medium", "hard", "fiendish", but SourGumdrop provides a numerical difficulty value. In this section I explain how SourGumdrop calculates its difficulty ratings and how users can tailor the program to closer approximate their own ideas on the subject. Note that as a byproduct, the flexibility of the SourGumdrop scheme provides a further way of obtaining hint information: users can get counts of the number of times each algorithm needs to be applied to complete the puzzle and can even select which algorithms are included in this process.
Before describing the rating scheme is is necessary to outline various strategies a program might use when applying its range of algorithms. The overall puzzle difficulty must depend on the number of times each algorithm is applied in finding its solution, and this number depends on the order in which the algorithms are selected for use. The order depends on the strategy used.
There are two features common to all the strategies used by SourGumdrop:
1. Simple filtering and setting singles is performed automatically as part of each algorithm.
2. Every search for the potential application of each algorithm finds ALL possibilities. An instance which removes the most candidates is remembered ready for use.
The algorithms are arranged into order according to their complexity: for example, first hidden_single,..., jellyfish last; and then the following procedure is used. Start with the simplest algorithm and keep applying it until it has no effect; then apply the next most complicated algorithm, if it has no effect try the next algorithm. As soon as an algorithm has an effect, apply it once and then go back to the simplest. Continue until the puzzle is finished or no progress can be made (in which case, give up). This strategy is designed to approximate that which might be used by a human solver who always considers the whole of the puzzle. The Simplest First strategy works out the easiest steps to the solution: it will never use a complex algorithm when a simpler one will also remove a candidate.
Coupled with difficulty scores for each algorithm, strategy "Simplest First" is the basis of the puzzle difficulty rating system used by SourGumdrop.
At any stage try all algorithms and apply the one that removes the most candidates. This is the one of the strategies used when the user asks for a general hint using the "?" button in the Toolbar (the other, "Simplest hint", is described below). Most effective is also used to solve puzzles read from files or entered by the user. However, in these cases, if the built in algorithms are unable to solve the puzzle, SourGumdrop also employs a directed guessing and backtacking algorithm to ensure it always has a working solution for the puzzle. "Direction" is provided by guessing for the unsolved cell with the lowest information content - for this cell the number of guesses is least.
This algorithm finds a hint with the lowest non-zero algorithm score and is hence closely related to the "Simplest first" strategy. Algorithms are applied in score order until a hint is found. This hint is then displayed.
The algorithms are applied in random order until the puzzle is solved or no progress can be made. This algorithm is not available in the standard version of the program but is used to gather statistics about the use of algorithms and for debugging.
A numerical value is assigned to each algorithm. This value is meant to represent the difficulty of recognising an instance of the algorithm's pattern and then applying it to particular cases. At the same time, the relative scores for each algorithm define the order in which algorithms are tried using the "Simplest First" and "Simplest Hint" strategies.
A possible set of scores is shown in Table 1. I am happy to set the default scores used in the program to any consensus arrived at by users. I mainly use them when generating new puzzles: I choose a set which will give me puzzles requiring particular algorithms. However, my choice does not really matter as SourGumdrop allows users to set their own algorithm scores and to use them to calculate puzzle scores.
Algorithm Score
Hidden single 1
Hidden pair 2
Hidden triple 2
Locked candidate 1 2
Locked candidate 2 2
Naked pair 3
Naked triple 4
Naked quad 7
Xwing 9
Swordfish 12
Jellyfish 20
Table 1. A possibly provocative set of algorithm scores.
The score for a puzzle is calculated as follows. Let Di be the difficulty rating for algorithm i, and Ni be the number of times algorithm i was applied in solving the puzzle (using the Simplest First strategy). The difficulty rating for the puzzle is then the sum of Ni x Di for all i.
For example, using the values in Table 1, if a puzzle required 2 applications of Naked quad and 1 Jellyfish and nothing else the difficulty rating would be 2 x 7 + 1 x 20 = 34
The File menu contains an option "Show difficulty/Set scores". This allows the scores for the individual algorithms to be set by the user. By setting algorithms scores the user is also automatically putting algorithms into groups. When the option is selected the window shown in Figure 1. appears. At the top is a row of algorithm labels; below this a row showing the number of times each algorithm needs applying to finish solving the current puzzle; below this a row of buttons showing the current scores for each algorithm. At the bottom the current puzzle "Total" score is given plus a "Recalculate" button and an "OK" button. By clicking on the algorithm score buttons the user can change their values. Clicking on "Recalculate" will show the score using the current set of algorithm scores. For these calculations the Simplest First strategy is used.
Note that any algorithm given a score of 0 will not be used to calculate the puzzle difficulty. This means that users can experiment with seeing which alternative routes there are for solving the puzzle. Figure 2. shows data for the same puzzle as that in Figure 1. But here we see the effect of zeroing the scores for the algorithms until only the hardest ones are used. If any more were zeroed the puzzle would not be solved.
Note also that it is the current state of the puzzle that is given a score and algorithm usage counts. This means that at any stage the user can employ this option to see what is still required.
If the puzzle cannot be solved using the current set of algorithms with non-zero score SourGumdrop will display the total score as "***". This can arise in two ways: if the user has set the scores for too many algorithms to zero, or if the user has entered a puzzle from a file or the Puzzle entry window and it is too hard for SourGumdrop's current algorithms. Note that in the latter case SourGumdrop can still solve the puzzle as is explained in the "Most effective" section but the guessing algorithm described is not used by the difficulty rating function.
