Yet another Sudoku solver

As if the net didn't have enough already, here is my version of a Sudoku solver written in Perl. The solver is currently capable of solving a range of puzzle geometries including nine value puzzles with blocks of three by three cells, sixteen value puzzles with blocks of four by four cells and nine value Samurai puzzles.

The solver should be capable of solving any puzzle of the supported geometries, for which there is a unique solution. Unfortunately, this is not yet the case. Some examples of puzzles which are beyond the solver's capability are on my Unsolved puzzles Page.

Latest version of the solver

The solver is being developed as time permits. Updates include new features and bug fixes. It was last updated on Saturday, 31st October 2009 11:04 GMT. The solver now includes limited support for working through the solution one step at a time.

Techniques used by the solver

The solver uses the following techniques, in sequence. If any technique results in a change to the grid, the solver falls back to the first technique.

Basic reduction

This is the basic technique of Sudoku. For each cell that contains only one value, remove that value from all of the cells in the same row, column and block. Any puzzle which can be solved by using only this technique is rated as easy.

Single candidate

Look at the possible values in the cells of a given row, column or block. If there is a value which can only exist in one of those cells, then it must exist in that cell. Remove all other possible values from that cell. Any puzzle which requires this technique is rated as intermediate.

Candidate line

This technique looks at intersections between rows or columns and blocks. If the only instances of a particular value within, for example, a row lie within one block, then that value cannot occur anywhere else in that block. Any other instances of that value in cells not in the particular row can be eliminated. Any puzzle which requires this technique is rated as intermediate.

Naked pairs, triples, etc.

If there are n cells within a particular row, column or block which contain only n different values, then those n values must occur in those n cells. It is not necessary for all n values to appear in each cell. Any other instances of those n values in other cells of that row, column or block can be eliminated. Any puzzle which requires this technique is rated as hard.

Hidden pairs, triples, etc.

If the only instances of n different values within a particular row, column or block are contained within exactly n different cells, then those n values are the only possible values which can exist in those n cells. It is not necessary for all n values to appear in each cell. Any other candidate values in those n cells can be eliminated. Any puzzle which requires this technique is rated as hard.

X-Wing

This technique is quite complicated and I will explain it some other time... There is a good description of this technique on the Sudoku of the day site. Any puzzle which requires this technique is rated as very hard.

Simple Coloring

If a group (row, column or block) has exactly two cells which could contain a particular value, then one of those cells must contain that value and the other must not. This is called a conjugate pair. Simple coloring identifies a chain of conjugate pairs. For example, there may be a pair in a row. One of those values may be one of a pair in a column and so on. Each cell in this chain is colored with alternate colors. Any cell which contains the value under consideration as a possible candidate, but which is not part of the chain, can have that value eliminated if both colors exist in the groups of which it is a member. Also, if one of the colors occurs twice in any group, all cells of that color can have the value under consideration eliminated. Any puzzle which requires this technique is rated as very hard.

Multi Coloring

This technique is similar to simple coloring, but uses multiple chains of the same value in combination. There is a good description of both simple and multi coloring at SadMan Software. Any puzzle which requires this technique is rated as very hard.

Forcing Chains

This technique looks for chains of values connecting cells which contain two candidate values. A cell is chosen and experimentally set to one of its two possible values. Every other cell which has two candidate values and is in the same row, column and group is then examined to see whether its value is forced to one of its two possible candidates. This process is repeated across the grid for each cell where a value was forced. The whole process is repeated for the other possible value in the originally chosen cell. There are three ways that this technique can eliminate values from the grid. Firstly, if during the process of forcing either chain, a cell would be forced to the opposite value to that which has allready been set, then the choice of value in the initial cell of the chain must be wrong and can be eliminated. Secondly, if a cell is forced to the same value in both chains, the value to which it is forced must be correct and the other value can be eliminated from that cell. Finally, any other cells in the grid which have the same value from both chains in some combination of their groups can have that value eliminated. Any puzzle which requires this technique is rated as very hard.

Nishio

This is a limited form of guessing. The idea is not to search for a solution, but to establish if one of the possible values in a cell would produce an invalid grid. An attempt is made to solve the puzzle with each possible value. If the value tested produces an invalid grid, then that value must be wrong and can be eliminated from that cell. Any puzzle which requires this technique is rated as diabolical.

Initial Grids

If you don't fancy entering the initial grid yourself, you may like to investigate this small database of grids, graded by difficulty.

Developments

In due course, I intend to develop this site further. Amongst other things, I plan to do the following:

Also in this section

Feedback

Please submit comments and questions about this site to

If you enjoyed this site, small donations towards running costs are always gratefully received (well, I can hope...). Joking aside, thank you for chosing to visit my website.