|
| View previous topic :: View next topic |
| Author |
Message |
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
 Posted: Wed Aug 17, 2005 7:52 pm Post subject: Four-sing chains |
 |
|
Does this seem a reasonable implementation of forcing chains?
| Code: |
/*
* Try forcing chains analysis, as described here:
* http://www.simes.clara.co.uk/programs/sudokutechnique7.htm
*
* An extended form of the Y-wing analysis from here:
* http://www.simes.clara.co.uk/programs/sudokutechnique11.htm
*
* It's similar to forcing chains except that it only affects the
* cells in the chain, rather than any cells that are outside of
* the chain like Y-wing.
*
* 1. Build a list of cells that have only 2 candidates, {c}
*
* 2. Create a list of chains that we have created {CH}.
*
* 3. For each cell in our set, {c:X}, and provided {c:X} isn't
* in use in a chain already:
*
* 3.1 Create a new chain {CH:X}. Add {c:X} to {CH:X}
* to the chain.
*
* 3.2 The candidates in {c:X} are labelled A and B
*
* 3.3 Look for a cell in the same row, col or block as {c:X}
* that contains either number A or B, and any other number
*
* 3.4 If we find a cell that isn't already in this chain:
*
* 3.4.1 Add this cell to the {CH:X}
*
* 3.4.2 There are two numbers in this cell, the number
* we found and another number, which we call Z
*
* 3.4.3 Starting from this cell, look for another cell in
* the same row, col or block that holds number Z and
* another number.
*
* 3.4.4 If one is found that we haven't visited before,
* then goto 3.4.1
*
* 3.4.5 If none is found, go back to 3.
*
* 3.5 No matching cell was found, this is the end of the chain.
* We can continue to 3, unless we've run out of cells, in
* which case, continue to 4.
*
* 4. For each chains in {CH}, which we'll call {CH:n}:
*
* 4.1 For each cell in the chain {CH:n}, try each possible
* value at that cell (there's only 2)
*
* 4.2 Note down the consequences of each possible value
* that we can put into {CH:n}
*
* 4.3 If there are any common occurrences between both
* possible values, then we can be certain that they are
* the case, so we can remove that candidate or set that
* value.
*
*/
function try_forcing_chains ( ) {
|
Does this seem reasonable? I can be accused of being a little verbose in my descriptions, but I am thinking in terms of code that I'm going to write...
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
 |
| Nick70
| | Joined: 08 Jun 2005 | | Posts: 160 | | : | |
Items |
|
| Posted: Thu Aug 18, 2005 8:20 am Post subject: |
|
|
A description of an efficient algorithm to find forcing chains is here.
That description limits to double forcing chains, but it's trivially extended to any number of concurrent forcing chains.
It also finds ALL possible forcing chains. If you want to limit to e.g. xy-chains (chains where the conjugate possibles are always in the same cell) you can add the restriction when you select the possibles for the next level in the search tree. |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Wed Aug 24, 2005 6:05 pm Post subject: |
|
|
I've got a recursive implementation of forcing chains, and I've run it against the first puzzle here:
http://www.simes.clara.co.uk/programs/sudokutechnique7.htm
It gets most of the way through but the recursive algorithm finds 3817 chains, and takes a little longer than I'd like to do it. As of yet, I haven't begun to calculate the implications of each of the chains, so this might take even longer to run, and perform the analysis. The chains in the example puzzle run somewhere between 8 and 12 cells.
I reckon my error came in trying to think of forcing chains in terms of graph theory, which has resulted in some nice code that covers every possible chain, but takes a while to run as a result.
I'm considering an implication tree instead, which will generate less data. Say I have 20 cells with 2 possibe values in, and on average each cell has 3 other 2-value cells in the same row/column/block. So I have optionally 40 possible implications to calculate, each involving 3 further implications, so I end up with about 120 prepositions in 40 or so initial states.
This will take much less time to process than 3000-odd chains, and their associated implications. I'm going to have a crack at implementing this and see how it runs.
Anyone who's coded implication chains, it's effectively the same as forcing chains, no? What's the optimal number of steps to calculate the implication for at the initial stage?
(/me dons flameproof suit)
I don't think this is, but this has elements of trial and error behind it...
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| kranser
| | Joined: 18 Aug 2005 | | Posts: 35 | | : | |
Items |
|
| Posted: Wed Aug 24, 2005 10:26 pm Post subject: |
|
|
| Would completing the puzzle as much as possible using other methods and only using the Forcing Chain when the other methods are exhausted help? Or is the forcing chain required to be solved early on in the puzzle in order to solve the rest of it? |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Wed Aug 24, 2005 10:32 pm Post subject: |
|
|
I have practically every other possible method, bar colouring. I've got a brute force, swordfish, subsets (number chains), nishio, y-wing, all the standard stuff, and now I've got forcing chains too.
Some of my test puzzles aren't solved by all of the deductive logic steps so I'm resorting to the slightly less brute-force like approaches. I'd love to implement colouring but I'm having a hard time wrapping my head round the logistics of it. If anybody is willing to put it in words of less than 3 syllables, I'd be grateful... 
My initial forcing chains implementation was a recursive algorithm, which was very thorough, but took ages to run. My new implication-tree based method is smaller, simpler, and runs in a fraction of the time.
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Fri Aug 26, 2005 1:35 pm Post subject: |
|
|
ok, something isn't quite right in my algorithm. My algorithm either generates bad recommendations, or clashes with Y-Wing. I can't find the source of the problem.
Y-wing works, I've pretty much tested that to death. I've examined all the recommendations that it generates and they're all valid, for the test puzzles also.
So it has to be number chains. Here's the starting point:
| Code: | -125-487-
---------
75---6-23
--41-87--
-2--5--4-
--34-95--
48-----17
---------
2357-169- |
And here's the sequence of moves up to but not including the forcing chains:
| Code: | 2 -> [1,9] One number possible in cell
6 -> [6,3] One number possible in cell
4 -> [7,3] Candidate appears once in r3
5 -> [1,4] Candidate appears once in r4
5 -> [6,7] Candidate appears once in r7
4 -> [2,2] Candidate appears once in c2
1 -> [5,3] Candidate appears once in r3
2 <- [5,2] b5 only has 2 in c5
2 <- [5,7] b5 only has 2 in c5
2 <- [5,8] b5 only has 2 in c5
2 <- [9,8] b6 only has 2 in c9
2 <- [4,8] Number chain in r7 {2,3}, in {[6,8][7,8]}
3 <- [4,8] Number chain in r7 {2,3}, in {[6,8][7,8]}
3 <- [5,8] Number chain in r7 {2,3}, in {[6,8][7,8]}
3 <- [8,8] Number chain in r7 {2,3}, in {[6,8][7,8]}
6 <- [3,5] Number chain in c2 {6,8,9}, in {[3,2][3,3][3,7]}
6 <- [3,8] Number chain in c2 {6,8,9}, in {[3,2][3,3][3,7]}
8 <- [3,5] Number chain in c2 {6,8,9}, in {[3,2][3,3][3,7]}
9 <- [3,5] Number chain in c2 {6,8,9}, in {[3,2][3,3][3,7]}
9 <- [3,8] Number chain in c2 {6,8,9}, in {[3,2][3,3][3,7]}
3 <- [7,5] Number chain in c6 {2,3}, in {[7,7][7,8]}
6 <- [8,4] Number chain in c7 {5,6,8}, in {[8,2][8,6][8,8]}
3 -> [8,4] One number possible in cell
8 <- [1,2] b4 only has 8 in c1 |
I then get into this short sequence where the problem lies:
| Code: | 9 <- [3,3] Forcing chain result
8 <- [4,3] Forcing chain result
8 -> [3,3] One number possible in cell
9 -> [4,3] One number possible in cell
3 -> [5,1] One number possible in cell
3 -> [1,2] Candidate appears once in r2
6 <- [4,7] Number chain in r6 {6,9}, in {[3,7][5,7]}
6 <- [3,2] Forcing chain result
9 <- [1,1] Forcing chain result
9 <- [3,7] Forcing chain result
9 <- [7,2] Forcing chain result
9 <- [3,2] Forcing chain result
6 <- [1,1] Forcing chain result
6 <- [5,7] Forcing chain result
1 <- [7,5] Forcing chain result |
At which point I'm left with no possible candidates in r1,c1 and r2,c3. I think the problem is a flaw in my thinking, but I can't be sure if the recommendations are correct.
For the first forcing chain attack, the initial implications are:
| Code: | If 6,1 is 1: 6,4!1, 6,4=9
Expanded: 6,1 is 1: 6,4!1, 6,4=9, 2,2!9, 2,2=8, 6,1!9, 6,1=1, 3,2!8, 3,2=9, 6,4!1, 6,4=9, 2,2!9, 2,2=8
Un-contradicted: 6,1 is 1: 6,4!1, 6,4=9, 2,2!9, 2,2=8, 6,1!9, 6,1=1, 3,2!8, 3,2=9
If 8,1 is 1: 6,1!1, 6,1=9
Expanded: 8,1 is 1: 6,1!1, 6,1=9, 2,2!9, 2,2=8, 6,4!9, 6,4=1, 3,2!8, 3,2=9, 2,4!1, 2,4=7, 6,1!1, 6,1=9, 2,2!9, 2,2=8, 2,7!7, 2,7=1, 5,4!7, 5,4=3, 2,4!1, 2,4=7, 3,4!3, 3,4=6, 5,7!3, 5,7=2, 6,7!2, 6,7=3, 5,7!3, 5,7=2, 6,6!3, 6,6=2, 6,7!2, 6,7=3
Un-contradicted: 8,1 is 1: 6,1!1, 6,1=9, 2,2!9, 2,2=8, 6,4!9, 6,4=1, 3,2!8, 3,2=9, 2,4!1, 2,4=7, 2,7!7, 2,7=1, 5,4!7, 5,4=3, 3,4!3, 3,4=6, 5,7!3, 5,7=2, 6,7!2, 6,7=3, 6,6!3, 6,6=2
|
Which results in these removals (I'm only doing the candidate removals, rather than setting values:
| Code: |
Common between outcomes: 2,2!9, 2,2=8, 3,2!8, 3,2=9
9 <- [3,3] Forcing chain result
8 <- [4,3] Forcing chain result
|
The next forcing chain block is this:
| Code: | If 0,0 is 6: 2,1!6, 2,1=9, 8,0!6, 8,0=9
Expanded: 0,0 is 6: 2,1!6, 2,1=9, 8,0!6, 8,0=9, 0,0!9, 0,0=6, 2,6!9, 2,6=6, 6,1!9, 6,1=1, 0,0!9, 0,0=6, 2,1!9, 2,1=6, 2,1!6, 2,1=9, 8,0!6, 8,0=9, 0,0!6, 0,0=9, 2,1!6, 2,1=9, 4,6!6, 4,6=9, 6,4!1, 6,4=9, 0,0!9, 0,0=6, 2,1!9, 2,1=6, 2,6!9, 2,6=6, 0,0!9, 0,0=6, 2,1!9, 2,1=6, 6,1!9, 6,1=1
Un-contradicted: 0,0 is 6: 2,1!6, 2,1=9, 8,0!6, 8,0=9, 0,0!9, 0,0=6, 2,6!9, 2,6=6, 6,1!9, 6,1=1, 2,1!9, 2,1=6, 0,0!6, 0,0=9, 4,6!6, 4,6=9, 6,4!1, 6,4=9
If 8,0 is 6: 0,0!6, 0,0=9, 2,1!6, 2,1=9
Expanded: 8,0 is 6: 0,0!6, 0,0=9, 2,1!6, 2,1=9, 2,1!9, 2,1=6, 8,0!9, 8,0=6, 0,0!9, 0,0=6, 2,6!9, 2,6=6, 6,1!9, 6,1=1, 0,0!6, 0,0=9, 2,1!6, 2,1=9, 0,0!6, 0,0=9, 2,1!6, 2,1=9, 4,6!6, 4,6=9, 6,4!1, 6,4=9, 0,0!9, 0,0=6, 2,1!9, 2,1=6, 2,6!9, 2,6=6, 0,0!9, 0,0=6, 2,1!9, 2,1=6, 6,1!9, 6,1=1
Un-contradicted: 8,0 is 6: 0,0!6, 0,0=9, 2,1!6, 2,1=9, 2,1!9, 2,1=6, 8,0!9, 8,0=6, 0,0!9, 0,0=6, 2,6!9, 2,6=6, 6,1!9, 6,1=1, 4,6!6, 4,6=9, 6,4!1, 6,4=9
Common between outcomes: 2,1!6, 2,1=9, 0,0!9, 0,0=6, 2,6!9, 2,6=6, 6,1!9, 6,1=1, 2,1!9, 2,1=6, 0,0!6, 0,0=9, 4,6!6, 4,6=9, 6,4!1, 6,4=9
6 <- [3,2] Forcing chain result
9 <- [1,1] Forcing chain result
9 <- [3,7] Forcing chain result
9 <- [7,2] Forcing chain result
9 <- [3,2] Forcing chain result
6 <- [1,1] Forcing chain result
6 <- [5,7] Forcing chain result
1 <- [7,5] Forcing chain result
|
My forcing chains method follows this pattern. In the end it was more of an implication tree approach, because the initial approach was more recursive that I wanted.
| Code: | * The implication approach:
*
* Build a complete list of cells that only contain 2 values.
* For each of the cells in the set, work out what would happen
* to the cells in the same row, column and block if we set the
* that cell to each value. Only consider the cells in the same
* row, column or block. These are referred to as the first order
* implications.
*
* We are storing inferences that we know about. For example,
* assume cells A and B have two numbers in, and cell C has three.
* If we set A to value N, then we can say that B!=N, but because
* B has only two numbers in, if B!=N then B must contain it's
* other number, W. However, we can't say the same of cell C, as
* there are more than two possible numbers in it. So all we can
* say about A=N is this:
*
* A=N
* B!=N
* B=W
* C!=N
*
* This is carried out for both values of each cell.
*
* Once we have a complete set of implications, we can start
* chaining them together. Look at each cell in the puzzle again
* and calculate the full set of implications. If setting cell
* X to value N X affects cells A, B, and C, then we can add
* the implications of cells A, B, and C to the list. If cell C
* also affects cell D, we can add that on as well.
*
* We only add each cell's implications once. If cell C affects
* cell A, we don't need to add cell A, and it's implications as
* we've already added it to the chain and considered it's outcome.
*
* Then we remove contradictions. If, somewhere in the chain of
* implications we have something like A=N and A!=N, then this can
* clearly not be the case, so we throw this information away.
*
* Now, starting at a given square that has two possible start
* values, and two implication trees from each value, we compare
* the two possible outcomes. If there are any common outcomes
* between the two, then they will be the case whatever number
* goes in to the cell in question, so they must be true. |
Whenever implications are removed from the puzzle, we recalculate the implication tree from scratch, as the implications that we have are now invalid.
My questions: am I right to remove contradictions? Or should I add the two implications together, then remove contradictions, and whatever's left over is good?
Should I consider only cells that have 2 possible values in the implication tree, or should I consider all the cells that are affected by setting a cell to a given value?
Should I only examine implications from conjugate pairs, or from any cell that only holds two numbers?
What about looking at every possible implication, adding them all together, removing contradictions then playing with what's left over?
If a chain has contradictions in it, then can I reason that the chain is invalid, as it will result in an invalid board? Surely that can't be the case, as at least one arm of the chain should have a valid outcome...
If anyone wants the code as well, I'll gladly post it.
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| angusj
Site Admin
 | | Joined: 18 Jun 2005 | | Posts: 406 | | : | |
Items |
|
| Posted: Fri Aug 26, 2005 1:47 pm Post subject: |
|
|
| gaby wrote: | | ok, something isn't quite right in my algorithm. |
I haven't had a close look but your rows and cols seem mixed up in places. |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Fri Aug 26, 2005 2:29 pm Post subject: |
|
|
Sorry, I should have mentioned, all the coordinates I use are in an X,Y coordinate system, with 0,0 being top left, 8,0 being top right, 0,8 bottom left, etc.
The coordinates in the backtrace have been normalised to human-friendly output (starting at 1,1 instead of 0,0) but the internal information in the expanded, un-contradicted, etc lists is all in 0,0 format.
Sorry if this caused confusion...
In the meantime, I've found that if, in the common list, values are set and candidates are removed, I was only removing candidates. If I do both (remove candidates and set values) then it solves some more puzzles.
I'm also pretty sure it's the forcing chains code. I ran the solver against the 200 hardest puzzles from antother post. With forcing chains on, lots of the unsolved puzzles end up in invalid states. With it turned off, they remain unsolved but in valid states. I think my understanding of forcing chains is what's borked here...
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Fri Aug 26, 2005 3:09 pm Post subject: |
|
|
Well, doing some more testing against forcing chains versus Y-wing, I have the following results:
| Code: | Forcing chains, no Y-wing, 109 puzzles, solved: 39, unsolved: 70
Completed cells: 6380
Incomplete cells: 2449
Candidates left: 7344
Y-wing, no forcing chains, 109 puzzles, solved: 31, unsolved: 78
Completed cells: 5183
Incomplete cells: 3646
Candidates left: 11946
Both, 109 puzzles, solved: 39, unsolved: 70
Completed cells: 6200
Incomplete cells: 2629
Candidates left: 8054 |
It seems that forcing chains does help, but I don't know by how much. Unsolved does include unsolved and invalid outcomes. Perhaps it's only applicable to puzzles where there are single solutions?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| 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 |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
