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   

Irrational cycles: Forcing chains meets hard logic

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Sun Sep 18, 2005 1:40 am    Post subject: Irrational cycles: Forcing chains meets hard logic Reply with quote

The other day I posted sort of a running thought on how to handle forcing chains in a manner that wasn't simply a form of trial and error. I have no idea if anyone has a similar logical approach, because I've seen nothing along those lines, but here's a technique I did find, that seems to be a limited subset of forcing chains following more logical rules. The following will build a cyclic graph using cells as vertices and constraints as edges, in a manner similar to fishy cycles.

First, go through all house-digit combinations (the latter 3/4 of the column set in dancing links): digit in box, digit in column, digit in row. For any such constraint that can be satisfied with only 2 positions, mark this constraint as a viable pair.

Now, go through the list of cells repeatedly and make eliminations until no more can be made. If a cell is a part of zero constraint pairs, or only one, eliminate that cell as a possible node in the graph. If for a particular digit, that cell has only one pair, remove that pair from consideration; this cell and the partner cell will have to be retested later. Then for any cell with 3 or more candidate digits, we need an additional rule: Each pair linked to this cell must have at least one other pair for the same digit. (I.e., if cell (6,4)=248 and 2 may be found in only one other cell in c4, but b5 and r6 are wide open, then c4 can be eliminated as a possible pair. If 4 can only be found in 2 places in both b5 and r6, both of those pairs will stay in play.) For such cells remove any pair from consideration which does not have another pair for the same digit.

Now, we'll be building a graph for which the vertices are the available cells, and the edges are the valid pairs found. This is a directed graph, meaning each edge can be drawn with an arrow, and each vertex will have one edge going in, and one out. The following rules apply:

- The lead vertex, a cell, must adjoin only edges which share the same digit. This vertex has a truth value of 1.
- Every other vertex must have only 2 candidates, unless it adjoins only edges with the same digit.
- For every vertex where the same digit appears on both adjoining edges, flip its truth value and carry that value forward for the following vertices.

The goal is to find a cycle in which the last vertex has a truth value of 1, which when reaching the first vertex will be flipped to 0. Since the truth value has to be pinned at 1, this is inconsistent and thus the cell for the lead vertex cannot contain the digit on both its edges.
Code:
    T/F  r4,d2   T
   (6,4)------>(1,4)
     ^           |
c6,d2|           |
     |           |
 T (6,9)         |c1,d9
     ^           |
r9,d5|           |
     |   b7,d3   V
   (3,9)<------(1,7)
     T           T

As illustrated in this graph, one of the candidates for (6,4) is 2. (1,4) can be only 2 or 9, (1,7) is only 3 or 9, (3,9) is only 3 or 5, and (6,9) is only 2 or 5. Upon reaching (6,4) again, since it has 2 edges with the same digit, the truth value flips from T (the value carried over from (6,9)) to F, which is inconsistent with its original setting of T.

This technique is based on the same principle as forcing chains but doesn't rely on following step-by-step deductions from a guess. It's also more limited because it can't find chains that guessing can. Because of that I'd prefer to call this technique irrational cycles.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Sep 18, 2005 2:56 pm    Post subject: Reply with quote

I don't understand exactly, what you are doing,
but it sound a like this:

http://arxiv.org/abs/cs.DS/0507053
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Sun Sep 18, 2005 7:55 pm    Post subject: Reply with quote

I don't think they're quite equivalent. That topic speaks to transforming a directed labeled graph to an unlabeled one, whereas on the contrary this technique is deliberately forming a labeled graph. Likely their approach is doing something similar to the puzzle but for different reasons or with a different expected result, in much the same way that fishy cycles and irrational chains are not identical in spite of both using graphs.

I know this is a variant of forcing chains, but it's a logical one which is what interests me. That is, it's a way of reforming the problem into a new domain to solve it, rather than guessing.
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Mon Sep 19, 2005 4:23 pm    Post subject: Reply with quote

Thinking over this algorithm some more, I suspect it can be upgraded to cover all or almost all forcing chains. The main modification of the rules is that you can use non-pair edges (houses with 3+ candidate positions for a digit). If you start out with a true value for a vertex, the outgoing edge may be any house-digit combination, not necessarily a pair. If the truth value at the vertex is false, however, the outgoing edge MUST be a pair; this will force the next vertex to have that digit as a value.

If it wasn't clear previously, this is what the truth value means:

True: This vertex has the digit used in the outgoing edge, and that digit will not be found in the next vertex.
False: This vertex does not have the digit used in the outgoing edge, so this edge must be a pair which will force the next vertex to have that digit.

Right now I'm still trying to get my implementation to work right in my solver. The technique however does work on paper, which is a good sign. This modified technique should cover all XY-wings just fine:
Code:
T   T   T   T   F
ZN->XZ->XY->YZ->ZN

The lead vertex starts true and leaves via a Z edge, meaning it is a Z. The next vertex is not Z, but is X. It leaves along an X edge, to get to XY. XY is not X but it is Y. It leaves along a Y edge to get to YZ; it is not a Y but is a Z. From YZ we move along the Z edge to ZN, which cannot be a Z because YZ was. Thus, Z is eliminated and only the digits left in N are valid. Because no false values are encountered until the end, any set of candidates for the houses is acceptable.

This upgraded rule may very well be a full logical equivalent to all forcing chains, unless it is considered legal in forcing chains (of this I'm not sure) to use something like 478 and use 4 and 8 set in the same house to force a 7. Cases like that could never be found with the simple cycles in this algorithm, although a version allowing for complex cycles (where one vertex can skip over several others to reach another, and therefore each vertex could have multiple incoming/outgoing edges) would definitely cover it. However this may find some things that forcing chains cannot, since forcing chains always assumes that it will be setting a firm value for each cell. Irrational cycles allows you to say of a cell that it may be a "not 6" rather than pegging it at a 2 or a 5.

So it's clear to me that this method is not equivalent to forcing chains, since it at least finds chains that the standard method would not, but I wonder if it could be considered a superset. It all depends on the legalities of the forcing chains method.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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