Chapter 3: Configuring the Solver

Table of Contents

Solver strategy

HoDoKu uses the same solver strategy as most other computer solvers. All available techniques are ordered. The solver tries one technique after the other until it finds a possible step. That step is applied to the sudoku and the search starts again with the first technique.

The order of the techniques is based on their difficulty (easier steps before more difficult ones). "Difficulty" very often is of course a matter of taste, which is why you can change the order of techniques to your liking (see below).

This strategy means that the solver never uses a complicated step if an easy one is possible. It also means that the solver very seldom finds the shortest possible solution, it finds the one with the easiest steps regardless of their number.

The standard solver order can be seen under "Edit|Preferences|Solver" after pressing "Reset to Defaults". As of version 2.0 the dialog lists 91 different steps, some of which belong to the same family (e.g. 42 different kinds of fish). Other steps take only one entry in the list but can produce slightly different techniques (e.g. "Nice Loops/AIC" can result in "Discontinuous Nice Loops", "Continuous Nice Loops", and "AICs").

Enabling/Disabling techniques

Screenshot: Standard order of solver steps

Steps can be enabled or disabled. A disabled step is not searched for by the solver.

Some techniques take a long time to compute and are therefore disabled by default (e.g. all the larger or more complicated fish types). Enabling them can have a serious impact on the time the solver needs to process a sudoku.

If you don't like specific steps you can disable them as well. Enabling or disabling techniques is a two step process: First click on the technique to highlight it. HoDoKu fills the "Step properties" panel with the step's attributes. If the step is highlighted clicking the step toggles the check box.

All changes made in the dialog are automatically saved at program exit. Alternatively they can be stored in a configuration file (see Saving/Loading configurations and sudokus).

Pressing the tree button above the step list switches the list into category display mode. Steps are shown in a tree organized by solution categories. This makes it easy to disable a whole group of techniques with one click (e.g. all Chains, or all Mutant Fish). Step reordering (see below) is not possible while in tree mode.

Changing order of techniques

To change the order, in which the techniques are processed by the solver, click a step to highlight it and use the "Up" and "Down" buttons to change the technique's location in the list or use drag and drop.

Please note that changing the order of techniques can result in completely different solutions for one and the same sudoku and can lead to a different rating (see Rating and difficulty levels).

The order of techniques not only affects the solver but the hint system as well. If you prefer certain techniques, put them further up in the list. If you don't like techniques at all, disable them. If you want them only as a last resort, put them further down the list.

Duplicities and examples

Many techniques exist under different names. A Skyscraper for example is also a Turbot Fish and an X-Chain. It can also be seen as a combination of two Sashimi X-Wings. 2-String-Kites and Empty Rectangles can also be Turbot Fishes or Finned Mutant X-Wings.

Step ordering and enabling/disabling can therefore be used to list certain steps only under a specific name. Take for example the following steps in their default search order:

Empty Rectangles are only shown if the box with the ER holds at least three candidates. Finding Empty Rectangles with two candidates can be enabled via an option, but since Turbot Fish comes before Empty Rectangle these steps will always be listed as Turbot Fish and the option seamingly has no effect at all. If you really want to see 2 candidate Empty Rectangles listed as Empty Rectangles, you have to either disable Turbot Fish or move Empty Rectangle before Turbot Fish. Likewise if you move Turbot Fish before 2-String-Kite or Skyscraper you will never see any of those anymore (they will be caught by the Turbot Fish code).

Progress measurement

Terms and definitions

Screenshot: Progress measure

Steps can be classified by how far they advance a sudoku. This is called the "progress measure" of a step. To compute the progress measure the sudoku is solved using a configurable set of techniques, the "progress steps". The screenshot shows the configuration panel for progress steps in category view. Steps can only be chosen if their difficulty level is at most "Hard". If you absolutely have to include an step that is "Unfair" or greater you have to change its difficulty level first.

If the list view is chosen, a step order can be defined for progress steps as well. This step order is completely independent from the normal solver step order.

To make configuring the progress steps easier various default configurations are available:

The progress measure for a step consists of three independent scores:

Solve up to

The progress definitions are also used by the "Solve up to" button in the hint area. If that button is pressed, the normal solver strategy is applied. If the next step found is defined as a progress step, it is executed and the search is repeated. The automatic solving stops at the first non progress step.

Backdoor searcher

Screenshot: Backdoor search dialog

Most sudokus, even very hard ones, have one or more backdoors: A backdoor is a cell or a combination of cells, that when set, reduces the sudoku to Singles only. Most sudokus have backdoors consisting of one cell only. Extremly hard ones need a pair of cells to become easy. The famous Easter Monster (posted by JPF one the Sudoku Player's Forum in April 2007) even needs three specific cells set before it yields to Singles.

HoDoKu can calculate various types of backdoors: Backdoors for cells only (using Singles as well as progress steps as measure) and backdoors for candidates or combinations of candidates.

When searching for backdoors in cells single cells are tried (for Singles and for progress steps). If no backdoors could be found the search continues for pairs of cells and if necessary for cell triples. Please note that these computations can take a long time to be completed.

When searching for candidate backdoors the maximum search depth can be chosen with a combo box ("Number of candidates"). As with cells the search stops as soon as backdoors have been found. Since a sudoku has a lot more candidates than cells a search depth of 3 means that HoDoKu has to try an enormous amount of candidate combinations which of course needs a long time to complete.

Options for solver steps

Every solver step has a level and a score besides his order in the solver hierarchie. These attributes are discussed in detail in Chapter 4: Rating and difficulty levels. The behaviour of some of the other techniques can be changed with the options available in "Edit|Preferences|Steps":

Screenshot: Solver step options

Fish general (options affect all types of fishes except Kraken Fish):

Kraken Fish:

Chains (options affect X-Chains, XY-Chains and Remote Pairs):

Tabling general (options affect Nice Loops, AICs, Forcing Chains/Nets and Kraken Fish):


ALS general:

Copyright © 2008-12 by Bernhard Hobiger
All material on this page is licensed under the GNU FDLv1.3.