View previous topic :: View next topic |
Author |
Message |
| noeldillabough
| Joined: 12 Oct 2005 | Posts: 16 | : | | Items |
|
Posted: Wed Oct 12, 2005 1:26 am Post subject: Solving With Colors Algorithm |
|
|
I've noticed I have a major weakness in my solver, it does not handle "Solving With Colors".
Here's an example:
Code: |
317|5..|.49
685|941|372
429|...|1.5
---+---+---
153|..4|.9.
796|.5.|.14
842|619|537
---+---+---
271|435|9..
938|267|451
564|198|723 |
Anyway before I try to write this I wanted to get some input from other programmers; this should be fairly straightforward. Can anyone write up an english pseudo-code for recognizing this state and subsequently reducing the candidates in the affected cell(s)? |
|
Back to top |
|
|
| noeldillabough
| Joined: 12 Oct 2005 | Posts: 16 | : | | Items |
|
Posted: Wed Oct 12, 2005 1:31 am Post subject: Oops |
|
|
Just saw the post by Lummox JR with his C code for doing this. I'll read it now |
|
Back to top |
|
|
| noeldillabough
| Joined: 12 Oct 2005 | Posts: 16 | : | | Items |
|
Posted: Wed Oct 12, 2005 1:34 am Post subject: *code flies over my head* Ok question asked again |
|
|
Ok either I'm really sleepy or my head isn't working but I didn't get the algorithm behind coloring; english pseudo code anyone? |
|
Back to top |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
Posted: Wed Oct 12, 2005 7:07 am Post subject: |
|
|
Do a search (I'd suggest on both "colouring" and "coloring".) There are some great descriptions here if you can find them. _________________ Simes
www.sadmansoftware.com/sudoku |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Thu Oct 13, 2005 7:00 pm Post subject: |
|
|
My C coloring algorithm posted here is now a bit outdated, too. I practice complete coloring now, which uses exclusions to their full potential. Here's the algorithm as I initially read and understood it:
1) Search all rows for conjugates. Label the first pair a and A, the second b and B, and so on.
2) Search all columns for conjugates.
2a) If neither cell is colored, use the next color set.
2b) If only one cell is colored, color the other with its conjugate.
2c) If both cells are colored, replace the higher color with the lower one's conjugate. Make this replacement everywhere. E.g., if you see A and B together as conjugates, then make all B's into a's and all b's A's.
3) Search all boxes for conjugates, using the methods in step 2.
Now in the basic form, you can do the following: 1) If the same color appears twice in a box/column/row, it is false and you can eliminate it. 2) If two conjugates intersect at another choice, eliminate it.
You can also look for equivalent colors, such as where A and B appear together and a and b also appear together, you can tell that B=a and b=A.
However if you want to use complete simple coloring, it's not much harder and will find more:
4) Look for colors which exclude each other by appearing in the same box/column/row. I use the notation a!b here, meaning a excludes b; they cannot both be true.
5) Compute transitive exclusions according to this rule: If x!y and Y!z, then x!z. The logic is pretty straightforward: If x is true, y is false and Y is true, and if Y is true z is false. Therefore if x is true, z is false, so they're mutually exclusive.
6) Find any cells which intersect the conjugates of two mutually exclusive colors. If a!b, then either A or B or both must be true, so any choice that touches A and B must be false.
In the case of your grid, simple coloring on the 8's will clear the way. After that you can use an XY-wing to solve the rest. |
|
Back to top |
|
|
| noeldillabough
| Joined: 12 Oct 2005 | Posts: 16 | : | | Items |
|
Posted: Fri Oct 14, 2005 2:42 am Post subject: Thank you, now what's an XY-Wing? |
|
|
Thank you, you saved me much work! I've written the code that successfully colors the board; I'm going to have to figure out how to reduce the candidates given that information (I can do it manually, just to figure out how to programmatically do it)
However after removing the 8 from coloring and another 8 due to a locked pair, I get the following possibilities
Code: |
{3} {1} {7} {5} {28} {26} {68} {4} {9}
{6} {8} {5} {9} {4} {1} {3} {7} {2}
{4} {2} {9} {37} {78} {36} {1} {68} {5}
{1} {5} {3} {78} {27} {4} {268} {9} {68}
{7} {9} {6} {38} {5} {23} {28} {1} {4}
{8} {4} {2} {6} {1} {9} {5} {3} {7}
{2} {7} {1} {4} {3} {5} {9} {68} {68}
{9} {3} {8} {2} {6} {7} {4} {5} {1}
{5} {6} {4} {1} {9} {8} {7} {2} {3}
|
Anyway after trying it out in Simple Sudoku it says it needs an XY-Wing...my program can find XWings and Swordfish but I've never come across an XY-Wing...what is it?
Is there a general algorithm that finds X-Wings, Swordfish and XYWings? My current code that searches for these is quite lengthy and inefficient (but it mimics how a human would do it)
Thanks in advance,
-Noel |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Fri Oct 14, 2005 3:41 am Post subject: |
|
|
XY-wings are unrelated to X-wing and swordfish but are so named because of the candidates used. XY-wing is actually what I'd call a "pairwise" method, meaning it operates on cells that have just 2 candidates. Other worthy pairwise techniques include remote pairs and the versatile uniqueness test (which is known to occur in 7 distinct forms).
A good explanation of XY-wing is here.
It's worth noting that the technique can be extended further. XYZ-wing is less common but does come up. It handles cases where the XY cell can also contain Z, but then you must find an intersection between all three cells: XYZ, XZ, and YZ. In XYZ-wing the XZ cell must share a box with XYZ, and eliminations are done in that box along the line between XYZ and YZ. You can eliminate Z from the cells in that part of the box, except the XYZ cell.
There are also further versions like the difficult-to-spot WXYZ-wing, and more. Again the main criteria is that XZ shares a box with the "center" cell (WXYZ) and the others (YZ, WZ) line up together with the center. |
|
Back to top |
|
|
| noeldillabough
| Joined: 12 Oct 2005 | Posts: 16 | : | | Items |
|
Posted: Fri Oct 14, 2005 4:20 am Post subject: Ahh |
|
|
I do know what this is, I've actually (without knowing what it was) used this technique before when manually solving sudoku.
Now I can match the name to the technique and add some code to see this variation. Thanks again! |
|
Back to top |
|
|
| noeldillabough
| Joined: 12 Oct 2005 | Posts: 16 | : | | Items |
|
Posted: Fri Oct 14, 2005 7:01 pm Post subject: |
|
|
(quoted from above)
Now in the basic form, you can do the following: 1) If the same color appears twice in a box/column/row, it is false and you can eliminate it. 2) If two conjugates intersect at another choice, eliminate it.
-------------------------
I've gotten part 2 of this working, however I need to test part 1; does anyone happen to have an example Sudoku puzzle where coloring is required and where a pair of matching colors are in a row, col, or box? |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Thu Oct 27, 2005 12:52 am Post subject: |
|
|
noeldillabough wrote: | I need to test part 1; does anyone happen to have an example Sudoku puzzle where coloring is required and where a pair of matching colors are in a row, col, or box? |
For a row, Angus Johnson's multi-colors002.ss yields matching colors at r1c1 and r1c9 for digit 6. Using his Simple Sudoku solver, the puzzle state at the point of the match without remaining candidates is ... Code: |
*-----------*
|..2|79.|18.|
|391|.58|74.|
|87.|..1|..5|
|---+---+---|
|2..|.79|8..|
|.8.|136|...|
|..3|8..|..7|
|---+---+---|
|43.|98.|..1|
|.69|.1.|..8|
|128|.67|4..|
*-----------* |
... and with remaining candidates is ... Code: |
*-----------------------------------------------------------*
| 56 45 2 | 7 9 34 | 1 8 36 |
| 3 9 1 | 26 5 8 | 7 4 26 |
| 8 7 46 | 2346 24 1 | 2369 2369 5 |
|-------------------+-------------------+-------------------|
| 2 145 456 | 45 7 9 | 8 1356 346 |
| 579 8 457 | 1 3 6 | 259 259 249 |
| 569 145 3 | 8 24 245 | 569 1569 7 |
|-------------------+-------------------+-------------------|
| 4 3 57 | 9 8 25 | 256 2567 1 |
| 57 6 9 | 2345 1 2345 | 235 2357 8 |
| 1 2 8 | 35 6 7 | 4 359 39 |
*-----------------------------------------------------------* |
For a column, Angus' multi-colors069.ss yields matching colors at r1c7 and r4c7 for digit 7. The state of the puzzle without remaining candidates is ... Code: |
*-----------*
|31.|982|.64|
|689|7.4|3..|
|.24|3.6|98.|
|---+---+---|
|.96|543|.18|
|158|279|643|
|43.|861|.9.|
|---+---+---|
|86.|497|13.|
|.71|638|4.9|
|943|125|876|
*-----------* |
... and with candidates is ... Code: |
*--------------------------------------------------*
| 3 1 57 | 9 8 2 | 57 6 4 |
| 6 8 9 | 7 15 4 | 3 25 12 |
| 57 2 4 | 3 15 6 | 9 8 17 |
|----------------+----------------+----------------|
| 27 9 6 | 5 4 3 | 27 1 8 |
| 1 5 8 | 2 7 9 | 6 4 3 |
| 4 3 27 | 8 6 1 | 257 9 57 |
|----------------+----------------+----------------|
| 8 6 25 | 4 9 7 | 1 3 25 |
| 25 7 1 | 6 3 8 | 4 25 9 |
| 9 4 3 | 1 2 5 | 8 7 6 |
*--------------------------------------------------* |
Matching (false) colors also exist in a row at r6c3 and r6c9 and your solver may find that first instead.
I don't have an example for a matching color in a box. |
|
Back to top |
|
|
|