View previous topic :: View next topic |
Author |
Message |
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Fri Oct 21, 2005 1:16 am Post subject: XY-Wings and Coloring, could they be merged? |
|
|
I have been experimenting with the combination of different techniques, to see whether some of these combinations can yield a better result than the techniques separately.
Here is a case that might be useful:
When an XY-Wing is found, either the XZ or the YZ cell must contain the Z-digit. They could also both contain that digit.
In multicoloring, where 2 conjugate pairs (A-a) and (B-b) are found, and A shares a house with B, either a or b must contain the digit you are coloring. They could also both contain that digit.
Sounds familiar?
This lead me to explore the possibility to combine (under certain circumstances) these 2 techniques.
This is the part I'm pretty sure of:
Quote: | When A and B are the XZ and YZ cells of an XY-Wing, and A is part of a conjugate pair (A-a) for digit Z, and B is part of a conjugate pair (B-b) for digit Z, a and b can never both contain digit Z. |
Would it be safe to draw the following conclusion?
Quote: | because a and b can never both be true, they are mutually exclusive for digit Z, so a!b. |
Of course, the a!b is useless when these are the only 2 conjugate pairs for digit Z. Since I've implemented multicoloring, I see lots of chains that are missing that vital connection to do some serious damage. This addition might be the trigger you need to solve a hard Sudoku.
Some notes:
There are 2 ways to deal with the shared peers of the A and B cells. Either they are taken care of by the XY-Wing routine, or just leave them to be detected and cleared by the coloring routine.
Even a "clean" XY-Wing (where nothing can be eliminated) can still be used in coloring.
If my logic is flawed, please tell me ASAP, because I've already started coding this...
Ruud |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Fri Oct 21, 2005 2:29 am Post subject: |
|
|
Programming did not take that long...
It works!
Found out that one more condition is required: When the XZ and the YZ cells are already conjugates for color Z, it is useless to pass them to coloring. Should have known that.
I found a few Sudokus where this method finds a solution faster than with multicoloring alone.
Need to do some mass testing with/without to see if more Sudokus can be solved with this.
Ruud |
|
Back to top |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Fri Oct 21, 2005 3:22 am Post subject: |
|
|
It's certainly valid logic, it's something that would happen automatically with "advanced colouring" (when colouring single pencilmarks instead of whole cells). |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Fri Oct 21, 2005 11:17 am Post subject: |
|
|
Nick70 wrote: | It's certainly valid logic. |
Thanks. I am pleased with this confirmation.
Nick70 wrote: | it's something that would happen automatically with "advanced colouring" (when colouring single pencilmarks instead of whole cells). |
That is true for a lot of techniques that subsume the "lower" ones.
Programming advanced coloring is a bit more complicated than merging the results of 2 existing techniques, as I did in this case.
Next combination: Remote Locked Pairs & Coloring |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Fri Oct 21, 2005 2:56 pm Post subject: |
|
|
Remote pairs is a lot easier to combine with coloring, since regular coloring already covers that case. With remote pairs you're working with a chain of conjugates already, one that exists for both candidates of the pair. |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Fri Oct 21, 2005 4:13 pm Post subject: |
|
|
Lummox JR wrote: | Remote pairs is a lot easier to combine with coloring, since regular coloring already covers that case. With remote pairs you're working with a chain of conjugates already, one that exists for both candidates of the pair. |
True. But that is also the downside. It means that I gain nothing except a little performance improvement.
Hmmm... What other options do we have? |
|
Back to top |
|
|
|