Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Solving With Colors Algorithm

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
noeldillabough

Joined: 12 Oct 2005
Posts: 16
:

Items
PostPosted: Wed Oct 12, 2005 1:26 am    Post subject: Solving With Colors Algorithm Reply with quote

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
View user's profile Send private message
noeldillabough

Joined: 12 Oct 2005
Posts: 16
:

Items
PostPosted: Wed Oct 12, 2005 1:31 am    Post subject: Oops Reply with quote

Just saw the post by Lummox JR with his C code for doing this. I'll read it now Smile
Back to top
View user's profile Send private message
noeldillabough

Joined: 12 Oct 2005
Posts: 16
:

Items
PostPosted: Wed Oct 12, 2005 1:34 am    Post subject: *code flies over my head* Ok question asked again Reply with quote

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
View user's profile Send private message
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Wed Oct 12, 2005 7:07 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Thu Oct 13, 2005 7:00 pm    Post subject: Reply with quote

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
View user's profile Send private message
noeldillabough

Joined: 12 Oct 2005
Posts: 16
:

Items
PostPosted: Fri Oct 14, 2005 2:42 am    Post subject: Thank you, now what's an XY-Wing? Reply with quote

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
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Fri Oct 14, 2005 3:41 am    Post subject: Reply with quote

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
View user's profile Send private message
noeldillabough

Joined: 12 Oct 2005
Posts: 16
:

Items
PostPosted: Fri Oct 14, 2005 4:20 am    Post subject: Ahh Reply with quote

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
View user's profile Send private message
noeldillabough

Joined: 12 Oct 2005
Posts: 16
:

Items
PostPosted: Fri Oct 14, 2005 7:01 pm    Post subject: Reply with quote

(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
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Thu Oct 27, 2005 12:52 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron