
View previous topic :: View next topic 
Author 
Message 
 PeteWake
 Joined: 31 May 2005  Posts: 6  :  Location: UK  Items 

Posted: Tue May 31, 2005 6:49 pm Post subject: Userfriendly internet only solver at sudokusolver.co.uk 


I've developed this with help from many people (including rubylips!)  it works using Javascript and will do things like stepbystep 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 sudokuing!
Pete Wake 

Back to top 


 PeteWake
 Joined: 31 May 2005  Posts: 6  :  Location: UK  Items 

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 remotelockedpairs 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 

Back to top 


 PeteWake
 Joined: 31 May 2005  Posts: 6  :  Location: UK  Items 

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. noone 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_ 

Back to top 


 scrose
 Joined: 01 Jun 2005  Posts: 23  :   Items 

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.
Code:  4 . .  . 9 .  . . 8 4 . .  . 9 1  . . 8
. . .  2 . 8  . . . . . .  2 . 8  . . .
. 1 .  . 5 .  . 6 . . 1 .  . 5 3  . 6 .
++ ++
. . 3  1 . 7  9 . . . . 3  1 . 7  9 . .
. . 1  . . .  7 . . reduces to . . 1  . . 9  7 . .
. . 7  5 . 2  3 . . . . 7  5 . 2  3 . .
++ ++
. 6 .  . 1 .  . 2 . . 6 4  . 1 5  8 2 .
. . .  9 . 4  . . . 1 . .  9 . 4  6 . .
5 . .  . 2 .  . . 4 5 . .  . 2 6  1 . 4
4___91__8+___2_8___+_1__53_6_+__31_79__+__1__97__+__75_23__+_64_1582_+1__9_46__+5___261_4 
Your solver correctly reduces r1c3 and r2c3 to {56} but then comes to a halt. Strangely, it was unable to see the gem lying in row 2: {379} {379} {56} [2] {467} [8] {45} {1379} {1379}. The candidates 4, 5, 6 only appear in columns 3, 5, and 7. Thus the candidate 7 can be removed from r2c5. The puzzle unravels from there.
I hope this puzzle helps you refine your solving methods. Your solver has been a great help in the past, and I really like your suggestamove implementation. 

Back to top 


 PeteWake
 Joined: 31 May 2005  Posts: 6  :  Location: UK  Items 

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 

Back to top 


 mathrec
 Joined: 15 Jul 2005  Posts: 10  :  Location: Carlsbad, CA  Items 

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 14, so the values 14 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 

Back to top 


 Nick70
 Joined: 08 Jun 2005  Posts: 160  :   Items 

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


mathrec wrote:  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. 
That's a very good observation, I had not thought of that.
It means that no problem can contain more than a naked or hidden quadruple. If it contained a quintuple, the complement would be at most a quadruple. Nice! 

Back to top 


 mathrec
 Joined: 15 Jul 2005  Posts: 10  :  Location: Carlsbad, CA  Items 

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. 

Back to top 


 PeteWake
 Joined: 31 May 2005  Posts: 6  :  Location: UK  Items 

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 

Back to top 


 Luns
 Joined: 25 Jul 2005  Posts: 1  :   Items 

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 restatement of what method B does. 

Back to top 


 mathrec
 Joined: 15 Jul 2005  Posts: 10  :  Location: Carlsbad, CA  Items 

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 

Back to top 


 ulfn
 Joined: 25 Jul 2005  Posts: 3  :   Items 

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 

Back to top 


 Nick70
 Joined: 08 Jun 2005  Posts: 160  :   Items 

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


ulfn wrote:  This is not very general, so I would be interested to hear suggestions on how to generalise it. 
It's just a XYWing. 

Back to top 


 mathrec
 Joined: 15 Jul 2005  Posts: 10  :  Location: Carlsbad, CA  Items 

Posted: Mon Jul 25, 2005 11:51 pm Post subject: XYWing 


Nick70,
The XYWing 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 XYWing 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 XYWing.
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 wxxyyz pivots at all.
Steve 

Back to top 


 ulfn
 Joined: 25 Jul 2005  Posts: 3  :   Items 

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


Thanks for clearing that up. I'll go away and implement xywings right away.
/ Ulf 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
