|
| View previous topic :: View next topic |
| Author |
Message |
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
 Posted: Sat Oct 08, 2005 6:29 pm Post subject: Best starting location for Coloring & Forced Chains |
 |
|
So far, I've been trying to avoid the "try this and see what happens" techniques, such as coloring, forced chains, trial & error.
I'm just not pleased with the kind of feedback my solver would have to give. However, using DLX as a last resort doesn't give me much feedback either.
In the UI, I've built the option to color the marks (or small numbers, if you prefer) and that seems to work best for me (as a human). I'd like to build a routine in the solver that does this multi-coloring, but the question is: where should it start?
I know I should look for conjugate pairs or cells with only 2 candidates, but in the endgame, the puzzle is just crowded with these. From my manual exercises, I found that it's better to avoid naked pairs, because they rarely form a larger chain.
Another issue is the feedback. The user is likely to ask for a hint at this point in the puzzle. I want the solver to give some feedback that makes a little more sense than: r1c1=8 => r2c2!=8 => r2c2=6 etc...
Your help is appreciated.
Ruud |
|
| Back to top |
|
 |
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Sat Oct 08, 2005 8:53 pm Post subject: Re: Best starting location for Coloring & Forced Chains |
|
|
| Ruud wrote: | | So far, I've been trying to avoid the "try this and see what happens" techniques, such as coloring, forced chains, trial & error. |
Forcing chains is more or less a try-and-see method, although there are ways of mapping it logically. Coloring on the other hand is not; it's pure logic.
| Quote: | In the UI, I've built the option to color the marks (or small numbers, if you prefer) and that seems to work best for me (as a human). I'd like to build a routine in the solver that does this multi-coloring, but the question is: where should it start?
I know I should look for conjugate pairs or cells with only 2 candidates, but in the endgame, the puzzle is just crowded with these. From my manual exercises, I found that it's better to avoid naked pairs, because they rarely form a larger chain. |
Although naked pairs are probably not going to help much with forcing chains, I'd definitely include them in coloring because they're a guaranteed conjuate.
| Quote: | | Another issue is the feedback. The user is likely to ask for a hint at this point in the puzzle. I want the solver to give some feedback that makes a little more sense than: r1c1=8 => r2c2!=8 => r2c2=6 etc... |
This sort of thing is quite difficult. For forcing chains I'd say it's not so easy to give useful feedback that doesn't look like the solver is just guessing. For coloring it's easy in simple cases, but not in hard ones. For example, you could say this in some cases:
"Coloring conjugates for the digit 2 shows that (1,1) and (6,1) have the same truth value. Therefore these choices must be false, and the alternate choices are true. The alternate choices are at (1,4) and (6,5), so a 2 is placed in both cells."
Another simple case is when you can find the intersection between one conjugate and another.
"Coloring conjugates for the digit 8 shows that either (5,5) or (9,8) must be 8. Therefore (5,8) cannot be 8."
In complete simple coloring, exclusions are used and full transitivity is calculated, so it's a lot more difficult to explain the color combinations. You'd pretty much have to say that color A is in certain cells, !A is in others, B is in others, etc. You'd do this only for cells involved in the elimination. Then you'd say things like: "Since A and !C both appear in row 3, they cannot both be true. Since C and F both appear in column 9, they cannot both be true. If A is true, !C is false, C is true, and F is false. Therefore A and F may not both be true. Since at least one of their conjugates !A and !F must be true, and !A is at (4,7) and !F is in (6,1), the digit 3 can be eliminated from cell (4,1)."
While it's possible to say such things, you'll have to figure out how. Calculating transitive exclusions is easy. Calculating the shortest path--or one of them at least--from one to another is not necessarily simple. If you have kept on hand a copy of the original exclusion matrix, then you can build a chain and follow it back once the exclusion you're looking for is deduced. I.e.:
Looking for the logic behind A!g:
A!B,c,f
b!e and C!D
A!B,c,D,e,f
E!g
A!B,c,D,e,f,g
You can take the E!g step and follow it back to the step that excludes e, whcih is b!e. Following that back leads you to the original exclusions. Therefore:
A!B and b!e -> A!e
A!e and E!g -> A!g
If you're going to try explaining that I'd recommend simply saving the original exclusion matrix and doing this calculation each time, rather than trying to follow along when transitive decuctions are made. Alternatively if you used a linked list to manage exclusions, I suppose you could always include a link that leads back to "what proved this". A potential problem in that case is that since transitivity works both ways, the logic wouldn't necessarily have a simple path from start to finish and you'd need to include multiple starting points. |
|
| 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
