|
| View previous topic :: View next topic |
| Author |
Message |
| Hakan
| | Joined: 09 Oct 2005 | | Posts: 10 | | : | |
Items |
|
 Posted: Thu Nov 17, 2005 10:14 pm Post subject: How do I find the forcing chain? |
 |
|
In another thread "retep" recently posted the following (partly solved) sudoku, where Simple Sudoku did not have a hint. Finally, I managed to find two forcing chains which solved the puzzle, but I regard this as pure luck!
Is there an easy way to find where to start (and finish) a successful forcing chain?
(I think I have seen an answer to this somewhere here, but I can't find it now.)
| Code: | *-----------*
|7.1|239|64.|
|6.2|145|..7|
|.49|867|.1.|
|---+---+---|
|4..|.5.|.7.|
|9..|.8.|.61|
|.6.|.2.|.53|
|---+---+---|
|.9.|.18|724|
|...|47.|5..|
|.74|59.|1.6|
*-----------*
*-----------*
|7.1|239|64.|
|6.2|145|..7|
|.49|867|.1.|
|---+---+---|
|4..|.5.|.7.|
|9..|.8.|.61|
|.6.|.2.|.53|
|---+---+---|
|.9.|.18|724|
|...|47.|5..|
|.74|59.|1.6|
*-----------*
*--------------------------------------------------*
| 7 58 1 | 2 3 9 | 6 4 58 |
| 6 38 2 | 1 4 5 | 389 89 7 |
| 35 4 9 | 8 6 7 | 23 1 25 |
|----------------+----------------+----------------|
| 4 123 38 | 369 5 136 | 289 7 289 |
| 9 235 357 | 37 8 34 | 24 6 1 |
| 18 6 78 | 79 2 14 | 489 5 3 |
|----------------+----------------+----------------|
| 35 9 356 | 36 1 8 | 7 2 4 |
| 128 13 368 | 4 7 236 | 5 389 89 |
| 28 7 4 | 5 9 23 | 1 38 6 |
*--------------------------------------------------* |
/Hakan |
|
| Back to top |
|
 |
| kranser
| | Joined: 18 Aug 2005 | | Posts: 35 | | : | |
Items |
|
| Posted: Fri Nov 18, 2005 9:38 am Post subject: Re: How do I find the forcing chain? |
|
|
| Hakan wrote: |
Is there an easy way to find where to start (and finish) a successful forcing chain?
/Hakan |
Well, it generally doesn't matter where you start. Just check each cell until you find one that produces an invalid chain for one of its candidates, or one where all of its candidates force another cell to a value.
However, best forcing chains are shorter ones, so it is probably best to search the whole grid for forching chains and then use the shortest one found (whichever cell this starts from) - though, this takes up processing time. My solver doesn't look for the shortest chains *yet*, and therefore find rather long ones!
A forcing chains finishes when:
1) You loop back to the start cell
2) You find a forced value that is invalid (thus an invalid chain is found)
3) Deadend - you cannot continue the chain based on forced moves
4) The chain completes the grid (puzzle)!
However, I don't nderstand when a forcing chain becomes tabling - so maybe someone else can say when a chain should end.
Kranser. |
|
| Back to top |
|
|
| Hakan
| | Joined: 09 Oct 2005 | | Posts: 10 | | : | |
Items |
|
| Posted: Fri Nov 18, 2005 5:46 pm Post subject: Re: How do I find the forcing chain? |
|
|
| kranser wrote: | | Hakan wrote: |
Is there an easy way to find where to start (and finish) a successful forcing chain?
/Hakan |
Well, it generally doesn't matter where you start. Just check each cell until you find one that produces an invalid chain for one of its candidates, or one where all of its candidates force another cell to a value.
However, best forcing chains are shorter ones... |
I am not programming a solver. I am using the Simple Sudoku program to highlight cells with just two candidates. Then I would like to try to find forcing chains "manually".
This is my (hopefully bad) strategy:
If I start with one of the two candidates in one selected starting cell, this candidate very often affects the value of more than one other cell. Thus, a chain could have many branches to follow and to keep in memory.
Then, I follow the other of the two candidates in the selected starting cell and this chain could also have a lot of branches.
If I am lucky and can keep some of these two branched chains in my head, I might find that some cell is forced to have a certain candidate.
Is there a better manual solving method to find forcing chains?
/Hakan |
|
| Back to top |
|
|
| arsoncupid
| | Joined: 22 Nov 2005 | | Posts: 10 | | : | |
Items |
|
| Posted: Wed Nov 23, 2005 3:18 am Post subject: Re: How do I find the forcing chain? |
|
|
| Hakan wrote: |
Is there a better manual solving method to find forcing chains?
/Hakan |
I've done some by hand. Here are the rules of thumb I've noticed, as obvious as they are ... maybe this helps.
1. select a starting cel that contains two numbers that are highly active in other sectors (rows, columns, squares) which have a low count of candidates.
2. Go a small ways into both of the two possibilities. Whichever direction leads to quicker resolution is (apparently) more likely to fail by contradiction.
3. If you're using the chain to find a contradiction, work North and South, or East and West. (Work means simplify, cancel candidates, and resolve numbers.) Then, once you're getting somewhere at the ends of those directions, work perpendicularly from there. Look for contradictions from the resolution in the destination areas.
Eg,
(3x3 boxes):
If starting in E, and B, H is easier than D, F ... work towards B and H. Then work towards A (if its easier than C of course) and G. And look for contradictions between A and G. |
|
| 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
