User-friendly internet only solver at sudokusolver.co.uk

PeteWake

I've developed this with help from many people (including rubylips!) - it works using Javascript and will do things like step-by-step solving, as well as storing the top sudokus of the day (the idea is to save typing in the Times or Telegraph etc grids) and the top 30 sudokus of all time.

http://www.sudokusolver.co.uk

I have developed the code as open source so any contributions to new solve methods etc. are much appreciated.

Happy sudoku-ing!

Pete Wake

PeteWake · Posted: Tue May 31, 2005 7:14 pm Post subject:

Message from Robert W:
===============================
Peter,

Just wanted to give you an update.

I've now got a solver that is just as good (or bad) on your two
challenge problems as yours is, though I don't implement all your
methods.

Some comments:

First, I think there's a rule that may be a superset of your methods
C and D, or at least equivalent to their union; it's not quite clear
from your description.

I call it "Comprehensive Locked Sets"

For each row/col/block, make a list of all the unsolved squares in
the group. Then run through all the permutations of the unsolved
squares with 2 or more squares in it, looking for a permutation of N
squares which have a total of N possible solutions.

ie: 12,23,13 or 12,123,13 or 12,234,14,13

If you can find one, you can then remove all those possibilities from
the other squares in the group.

I think it's easier to understand it this way than as described as
number chains.

You may also find it useful to implement the remote-locked-pairs test
that you can find at http://www.scanraid.com/remotepairs.htm

Your solver can't solve his example puzzle that demonstrates the
method; the code to load that puzzle is:

2581_4_37+936827514+47153_28_+7152_3_4_+849675321+36241__75+1249__753+593742168+687351492

PeteWake · Posted: Tue May 31, 2005 7:18 pm Post subject:

Message from Sandra Rose:
======================

This is unsolvable by your methods it needed a 4 in G8 at the start. The only method is guess each number. no-one could logically work this out without guesswork

Start Sudoku:

_2_______
___6____3
_74_8____
_____3__2
_8__4__1_
6__5_____
____1_78_
5____9___
_______4_

Cookie String: _2_______+___6____3+_74_8____+_____3__2+_8__4__1_+6__5_____+____1_78_+5____9
___+_______4_

scrose · Posted: Thu Jun 16, 2005 8:05 am Post subject:

Unlike Robert W's example (which requires Nishio) or Sandra Rose's example (which requires pure guesswork), I stumbled upon a puzzle that can be solved by logic, but which stumps your solver.

PeteWake · Posted: Sun Jul 10, 2005 9:21 pm Post subject:

Thanks for your comments scrose.. this should certainly be a relatively easy 'programming' task. When I get some time I will implement this.. although if anyone feels like writing some Javascript feel free to email me through this forum or through the site.

Thanks
Pete Wake

mathrec · Posted: Fri Jul 15, 2005 7:37 pm Post subject: "Comprehensive Locked Sets"

I wanted to expand on Robert W's generalization of "Comprehensive Locked Sets". There are two versions of the generalized rule:

A set of N squares in a unit (row, column, block) that have only N possible solutions within those squares. Generalizing RW's example:

12,234,14,13, 156,256

The first four squares contain only 1-4, so the values 1-4 cannot appear elsewhere. This reduces to:
12,234,14,13, 56,56

The complement of this is to have a set of N values that occur in only N squares of a unit. Here's the same example:

156,256, 12,234,14,13

The values 5 and 6 are only found in the first two squares, so no other values can appear in those squares. This reduces to:
56,56, 12,234,14,13

Note that these are true complements. If one version of the rule applies, then the complement form also applies. However, I find it simpler to recognize the 56 requirement than the 1234 requirement.

When I'm solving puzzles by hand, I look for both types of patterns, and when I'm stuck and searching, I search through permutations involving up to half of the unsolved cells. For example, if there are seven unsolved cells in a row, then I look for permutations of up to three cells with only three possible solutions, and I look for permutations of up to three values that can only be placed in three cells. Because these requirements are complements, there is no need to look for permutations of four or five cells (or values).

-Steve

Nick70 · Posted: Fri Jul 15, 2005 9:50 pm Post subject: Re: "Comprehensive Locked Sets"

mathrec · Posted: Sat Jul 16, 2005 2:12 am Post subject: Simple Loops

I suppose this will lead to a discussion of whether the technique is trial and error or logic. I argue that it is logic if the method identifies the loop, rather than simply finding a dead end.

Looking at the challenge puzzle at http://www.sudokusolver.co.uk/challenge.html, I count (by hand) nine different values that can be eliminated because of simple loops:

A1 is not 3 (A5,C6,C1)
C1 is not 1 (A1,A5,C6)
C4 is not 3 (A5,C6,C1)
C7 is not 9 (C4,A5,A8)
C8 is not 9 (C4,A5,A8)
C9 is not 9 (C4,A5,A8)
H9 is not 6 (H5,G4,G6,G9)
I5 is not 6 (H5,G4,G6,G9,G2,I2)
H7 is not 1 (B7,B6,C6,G6,G4,G2,G9,H9)

Note that the direction of the loop does not matter...

Obviously any choice that eventually leads to a contradiction can be eliminated. In this case, I've restricted the search to loops that only depend on simple elimination -- Not even using Solve Method A. For example, when considering loops originating from a choice of A4=9, I only considered that it would force C4 to be 3 and A8 to be 5. I didn't apply Solve Method A to consider that A7 would be 4. That would have led to a contradiction through (A7,B7,C6,G6,C6,C1,C4).

This search for loops is not random. It only pivots on doublets, and you only try choices that fix the value of more than one doublet. You can code some of the simple loops in descriptive terms, such as the one for (A1,A5,C6,C1), but it's just a logical loop.

PeteWake · Posted: Tue Jul 19, 2005 4:57 pm Post subject: Simple Loops

mathrec and Nick70,

I would definitely say that your method(s) are logic not "trial and error". They tie in (I think) with suggested update to solve method D from John MacLeod (see http://www.sudokusolver.co.uk/codeit.html). While the methods are mutually exclusive it would be good to code them both as I think as a principle the solver code should match human logic as far as possible

I would love to code up these methods and incorporate them into the solver - but it takes a while; it's a shame as I developed the site as 'open source' hoping lots of people would submit their own Javascript code to take it to the next level, and nobody has so far!

If I do get the time to put the new code in I will post another message to the site - but in the meantime if anyone feels inclined please take the plunge!

Pete Wake
sudokusolver.co.uk

Luns · Posted: Mon Jul 25, 2005 9:53 am Post subject:

I'm new here, having played with sudoku only for the last week or so, but thought I'd point out some observations I have from coding my own solver over the last few days.

Your methods C, D and F are actually all variants of the same method, just applied to different slices of the number/row/column array. I'll start with a way to look at method C and grow it into F:

Take a row from the solution grid, and for each cell, write a column of 9 squares of T/F for whether or not the digits 1 through 9 are in the respective cell - this is a 9x9 grid of T/F, which can be thought of as a chessboard on which we want to find the location of 9 rooks that can't attack each other in one move.

Method C amounts to finding two rows who have T in the same two columns. The four cells defined by this set of rows and columns has two rooks in it, so any other cells in the same columns can be cleared.

Method D expands this to three (or more) rows, who collectively have T's only in three (or correspondingly more) columns.

Method F basically applies C to a different grid: instead of making a grid of all values on a particular row/column/block, it just takes T/F for a particular digit across the rows/columns of the sudoku puzzle.

Method F doesn't need to be limited to two rows of this grid, and can be extended the same way that method D extends C. The "repeat for [2] columns [instead of rows]" in the description actually is equivalent to this being extended to 7 rows (including among the 7, rows with possibly only one T) instead.

Actually, another observation is that method D, if as well as extending it to sets of >2 rows, also includes looking for sets of only 1 row [with only one column containing T], then effecitvely takes over for method A.

So, methods A,C,D and F are actually just different incarnations of the same algorithm. My solver has just one function to do the work of C,D and F into which I pass a function pointer for one of four functions that picks out slices of the solution table (row/column/block/number).

The other thing I wanted to point out is that the 'block equivalent' presently given in the description of method F at http://www.sudokusolver.co.uk/solvemethods.html is actually just a re-statement of what method B does.

mathrec · Posted: Mon Jul 25, 2005 6:40 pm Post subject: Re: Equivalence of Slices

Very cool. I had not yet noticed that the roles of values, rows and columns could be exactly interchanged, although I'd realized that there were equivalences.

That implies that Solve Method F must also show a true complement between rows and columns. And it does! IF, in two rows a value appears only in two columns, THEN in the other seven columns the value appears only in the other seven rows. So only permutations of up to 4 columns/rows need to be considered.

I agree that the 'block equivalent' for Solve Method F does nothing beyond Solve Method B. I'd already come to that conclusion.

-Steve

ulfn · Posted: Mon Jul 25, 2005 9:10 pm Post subject:

I have method to solve challenge 1 (http://www.sudokusolver.co.uk/challenge.html):

Look at the locked pair A1,C1 - {13}. Furthermore look at the cells A5 - {35} and C6 - {15}. Obviously we can't have A1 - 3 and C1 - 1, since that would mean that both A5 and C6 would have to be 5, so we have to set A1 - 1 and C1 - 3. After this the rest of the puzzle is trivial.

In general:
- Find a locked pair {xy}.
- Find two cells forming a square with the locked pair, one containing {zx} and one {zy}.
- Set the cell of the pair next to {zy} to {x} and the other one to {y}.

This is not very general, so I would be interested to hear suggestions on how to generalise it.

/ Ulf

Nick70 · Posted: Mon Jul 25, 2005 9:45 pm Post subject:

mathrec · Posted: Mon Jul 25, 2005 11:51 pm Post subject: XY-Wing

Nick70,

The XY-Wing is a particularly easy logical loop to search for by hand. I appreciate that you've given it a name. I'm not sure that it will change how I code my solver, but it will certainly affect how I solve puzzles by hand. (So I suppose it should change how I code my solver...)

The XY-Wing is a special case of the exposed loop, depending only on simple elimination. In the challenge puzzle, A1, C1, C4, C7, C8 and C9 are all elimination points in some XY-Wing.

As I noted above, there are other exposed loops in the challenge puzzle, and still other logical loops that are not "exposed". The challenge2 puzzle is not so kind. There are no exposed loops in that puzzle, since there are no wx-xy-yz pivots at all.

-Steve

ulfn · Posted: Tue Jul 26, 2005 1:53 am Post subject:

Thanks for clearing that up. I'll go away and implement xy-wings right away.

/ Ulf