Solve Methods

These solve methods are run in order of complexity - if any change the solution grid then the solver goes back to solve method A and starts again.

Each time a particular solve method is used, it clocks up points of a 'difficulty score' to give an overall difficulty rating for the sudoku.  

Solve Method D UPDATED!

Revised method coded by Alan Chambers - thanks Al!

Look at a row in the solution grid to see if there is a group of N cells which contain only N possible numbers. If such a 'chain' exists, then those cells must contain these numbers, so we can eliminate these numbers from other cells in the row.

This is repeated for columns and blocks.

For example, in the row

1         2         3         4         5         6         7         8         9
---------------------------------------------------------------------------------
378       38        6789      37        458       2         34568     489       1

Columns 1,2 and 4 contain the numbers 3,7, and 8.

So we can eliminate [78] from column 3, [8] from column 5 and [38] from column 7 and [8] from column 8.

Afterwards the row looks like this:

1         2         3         4         5         6         7         8         9
---------------------------------------------------------------------------------
378       38        69        37        45        2         456       49        1

For a practical example, try this page.

Difficulty score=32, 48 or 64 for values N=2,3 and 4 respectively.

Solve Method E - not yet implemented

We've had a new Solve Method suggested to solve one of our Challenge Sudokus.. but haven't coded it yet. To see the new rule, or if you fancy a coding challenge, click here.

Solve Method F UPDATED!

This solve method gets progressively more complicated, as we will see.

But at its simplest: Look at a row to find instances where a number occurs in two cells only. If there are any other rows that satisfy the same rule with the same number, and the cell columns match in both cases, then that number must occur in two of those four cells. You can therefore eliminate any occurrences of that number in the matching columns. Repeat for columns.

This method is known by the gurus as X-wing.

There is also an equivalent for blocks as follows:

If, for each row, the two cells are in the same two blocks then you can eliminate other occurrences in the matching blocks. Repeat for columns relative to rows and columns relative to blocks. Then, repeat for blocks - if two blocks share either rows or columns and a single number occurs in just two cells in each block, in matching rows or columns, then other occurrences of the number can be eliminated from those rows or columns. (quite complicated, eh? not sure I understand it myself).

This gets even more complicated with a three-by-three cell equivalent call Swordfish.

Finally there are higher orders of this problem for four cells etc. Al Chambers has once again come to the fore and coded a generic version of Solve Method F which goes up to N cell complexity. Mind-blowing. He's named the version where N=4 Jellyfish, which I suppose is because it makes you go weak at the knees. Couldn't agree more, Al.

Difficulty score=48 (for X-wing) or 64 (Swordfish and above)

Other solve methods

Other solve rules can be seen at John Perry's website. These are pretty complicated but maybe you could be persuaded to have a go at writing the Javascript code!

What is 'allow Guess-and-Check'?

This implements what is known as an 'Ariadne's Thread'. If all the solve methods are exhausted, it takes a guess at the answer for a cell, and then tries to find an answer by reapplying the solve methods. If this results in an invalid Sudoku, it tries a different guess. If there are still options available, it carries on threading down until it finds an answer (or goes invalid). There's an argument as to whether this is 'logic', so we have made it an option using a tickbox.

Return First Possible Solution

If you're using the guess-and-check technique, it is always possible that there is more than one solution for a given Sudoku. Unticking the 'Return first possible solution' tickbox will check all possible threads to confirm that your solution is unique.

Acknowledgements

Many thanks to 'rubylips' at http://www.act365.com/sudoku/ for advice and help on the ariadne thread and other useful input.

Thanks also to r.e.s for supplying a link to the proof that Sudokus are NP-hard, and for testing the solver.

Thanks Pete Forman for the update to solve method B, looking in blocks.

Thanks Colin Hughes for spotting the bug in the set method.

Thanks Keven Cook for spotting the bug in the reporting pane.

Thanks Tim Lindsay for the unsolvable by logic example - the inspiration for the challenge page.

Thanks Bill Giles for the idea of the step-by-step solver.

Thanks Mark Summerville for providing the logic rules for solve methods E and F.

Thanks Kevin Lawson for suggesting the alternative challenge puzzle.

Thanks John MacLeod for the revised version of method D.

Thanks David Budgett and John MacLeod (again!) for the 'block' version explanation for method F.

Thanks Tim Nobel and Michael Lawrence for their new rule suggestions.

Thanks Al Chambers for his coding of the revised method D - good job!

Thanks to Craig Oakley for Swordfish.

Thanks to Al again for Method F as a generic.. it's beyond me!

Thanks to Nicolas Leoutre for translating the site into French.

Thanks to Sernin Van de Krol for translating the site into Dutch.

Thanks to Riccardo Riva for translating the site into Italian.

Thanks to Gordon Royle for hooking us up with his list of 17-digit sudokus.

Thanks to Pat Breniser for the tip on how to break out of the step by step solver.

Thanks to Mihai Vigariu for translating the site into Romanian.

Thanks to Elena Nellson for translating the site into Russian.