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   

Fishy Cycles
Goto page 1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Sun May 29, 2005 11:27 am    Post subject: Fishy Cycles Reply with quote

Edit: Following nick89's suggestion, I got the graphs to look pretty close to what I intended. Thanks nick89! Edit2: I have cleaned up more of the displays and some typos.


Below is a generalization of swordfish and x-wing. This result is an

algorithm which should run fast, at least for small puzzles, and

should give more information on some difficult puzzles. It extends

the set of logic rules discussed here.


Some nomenclature. (For the moment, until I get up to speed on the

standard terminology.) I will refer to the individual 81 squares as

"cells". I will refer to the 9x9 (Edit: I meant 3x3 here, thanks MadOverlord!) blocks as "blocks". I will refer to

individual rows, columns, or blocks as "houses". I will name the

houses by their column number, row number, or block number

(numbering blocks 1 through 9 in the usual way, left to right, top

to bottom.) For example, b3 is block 3, the third 9x9 (bah! I mean 3x3!) cell block on

the top right, and r2 refers to row 2, counting from top to bottom.

b3, r2, etc are refered to as the "names" of the houses.


The algorithm works by constructing for each of the numbers n (from

1-9) a multigraph "graph(n)" in which the vertices and edges are

labeled with certain house names. From graph(n), all possibilities

for the number n will be able to be removed from the houses which

label the edges of cycles in the graph. The construcion of graph(n)

is as follows:


The vertex set is the set of names of houses which contain n as a

possibility in exactly two of their cells.


An edge is drawn between two vertices if and only if there is a

house different from the houses of the two vertex sets which

contains exactly one possibility for n from each of the two vertex

houses.


The theorem (obvious extension of swordfish argument) states that

all other possibilities for n in the edge houses which are part of cycles in

the graph may be removed. ("Other" here meaning except for the pairs

that define the vertex

houses.) Here are two examples to illustrate the idea.


In the examples lower and upper case versions of the same letter in

the alphabet denote the unique pair of locations of possibilities

for the number n in a particular house.



Example 1

a**|**c|***
***|***|***
*A*|b**|***
---------------
***|B**|***
***|**C|***
***|***|***
---------------
***|***|***
***|***|***
***|***|***


The conclusion in this case is that the houses: r3,b5,r1, and b2 can

be cleared of n (excepting the locations a,A,b,B,c,C, of course).



The proof is as follows. Each location possibility x can be assigned

the value T or F according to whether or not n is in that location.

Now we chase the implications of the rules of Sudoku. Logical implications are denoted by ->.

Case 1. a=T -> c=F -> C=T -> B=F -> b=T -> A=F (consistent with

a=T).

Case 2. a=F -> A=T -> b=F -> B=T -> C=F -> c=T (consistent with

a=F).

Note that in either case, in the houses r3, b5, r1, and b2, there

will be locations for n with opposite values. (For example in Case

2, in b2, b=F and c=T; in Case 1, these values are reversed.). Thus,

in any case, there must be a T, and by the uniqueness of n in each

house, all other locations in those houses may have n eliminated

from them.


Point on the logic above. The implications from T to F follow from

the fact that in any house n can occupy only one cell. The

implications from F to T follow from the fact that the two locations

in question are always in a house with exactly two possible

locations for the number n.


The translation of this example into the graph language is as

follows:


Since a and A are the unique possibilities for the number n in the

house b1, there is a vertex labeled b1. Similarly there are vertices

labeled c4 and c6 (there are exactly two places that n can occur in

column 4 as well as two places n can occur in column 6).

Since the possible locations A and b both lie in (row) r3, (and

neither a nor B lie in that house), there is an edge in the graph

between the vertices b1 and c4. Similarly the edge b5 connects the

vertices c4 and c6. The edge r1 connects the vertex b1 to the vertex

c6. Finally, the house b2 also connects c4 to c6.


Accordingly, the graph has the following appearance:
Code:


                   r3
          b1-------------c4
           \        _____/|
          r1\    b5/     /
             \   /      /b2
               \|      /
               c6____/



[Edit: This graph has three vertices: vertices b1 and c6 are connected by edge r1, vertices b1 and c4 are connected by edge r3, and finally vertices c4 and c6 are connected by edges b5 and b2.]


The basic principle is that once graph(n) is constructed in the

above way, the labels of all edges, which are part of cycles in the

graph, constitute a set of houses for which n may be eliminated

(excepting vertex defining locations).


Example 2

***|**C|**d
***|*c*|***
**a|***|**D
---------------
**A|***|***
*b*|*B*|***
***|***|***
---------------
***|***|***
***|***|***
***|***|***

The vertex set is: {c3, r5, b2, b3}. The edge set for this case

is then (we denote edges of a multigraph (as usual) by labeled

unordered pairs.):


{{c3,r5} with label b4, {r5,b2} with label c5, {b2,b3} with label

r1, {c3,b3} with label r3}.


In this case there is no multiple edge.

Accordingly, with the exceptions of the possibilities for n in the

locations a,A,b,B,c,C,d, and D, n can not be a possibility in houses

b2,c5, r1, and r3 (excepting vertex defining possibilities).

A more detailed explanation of the first edge in this example: a and

A occur in c3. b and B occur in R5. These pairs are unique in these

houses (by assumption). Now A and b occur in b4. Niether a nor B

occur in this house. Thus b4 forms an edge between c3 and r5.

The graph in this example is:
Code:


              b4
          c3------r5
           |       |
         r3|       |c5
           |       |
          c9------b2
              r1


[Edit: The graph here is a square: The vertices are c3, r5, b2, and c9. The label of the edge between c3 and r5 is b4, the label of the edge between r5 and b2 is c5, the label of the edge between b2 and c9 is r1.]



The algorithm "Fishy Cycle" that arises from this is rather easy to

describe, and I think program.



-----------------------Algorithm "Fishy Cycle"--------------------------

For n ranging from 1 to 9 do:


1) Create the vertex set by searching through the 27 houses for

those with exactly two possibilities for n.


2) For each pair of vertices, check if there is a house containing

exactly one possibility from each pair. (For each pair of vertices,

there are four possibilities to check: For example, in the first

example above, when considering the pair of vertices b1 and c4, one

needs to check and see if there are houses containing the four

combinations a and b, a and B, A and b, as well as A and B. (This

is how multiple edges can arise in the graph.) Note that if a house

contains ,say a and b, then an edge is not formed if it also

contains either A or B.


3) With the graph constructed, one uses standard algorithms to find

all cycles in the graph. (Given the sizes of the graphs likely to

occur here, this will be very fast, as with the rest of this

algorithm.)


4) From the houses labeling the edges of cycles one now removes

possibilities for n which are not elements of the pairs which define

the vertices in the cycle under consideration.


Next n



The name "Fishy cycle" comes from swordfish, jellyfist, etc that

have been discussed here. Cycle from the fact that cycles in graphs

is the basis for the algorithm.

------------------------------------------

Remarks.

Swordfish, for example will only eliminate candidates for n which

are in a set of rows. This algorithm generalizes it, and will

eliminate candidates that are in rows, columns, as well as blocks

for each n.


Both x-wings and swordfish and the extensions that I've seen discussed here are special cases.


The algorithm should take almost no time typically as in most Sudoku

pubbles I've worked through, there are few vertices in the sense of the

algorithm above.


The algorithm can be done by hand.


I am not a programmer, but I would be delighted if anyone is

interersted in implementing this algorithm. I would be happy to try

out the results and look forward to more exploration with Sudoku. I

think the problem of finding computer solutions that are human

comprehensible to these puzzles is quite fun. Backtracking is so not

amusing by hand. :/


I only found out about Sudoku two days ago from a news website! This

forum seems to have a really fun spirit! Nice to meet everyone! =)


Please forgive me and don't hesitate to point out my mistakes etc.

No offense will be taken.


On that note, I have no skill programming, so this algorithm hasn't

been fire tested. Perhaps there is some glaring fault with what I

written above. If so, please forgive me for wasting your time. If this is the

case, most likely, there are missing hypothesis for certain situations

where this can be applied or something to that effect.


Peace,


PS My appologies, I can't seem to make the graphs come out right. Bah!

Hopefully the vertex and edge descriptions will sufice.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage


Last edited by Doug on Thu Jun 02, 2005 4:08 am; edited 12 times in total
Back to top
View user's profile Send private message Send e-mail
nick89

Joined: 26 May 2005
Posts: 2
:

Items
PostPosted: Mon May 30, 2005 12:00 pm    Post subject: Reply with quote

Using the code tags in your post will force a fixed width font for your diagrams.

IE:
Your 1st digram-
Code:

 r3
b1-------------c4
\ _____//
r1\ b5/ /
\ / /b2
\| /
c6____/


Your 2nd Diagram-
Code:
 b4
c3------r5
| |
r3| |c5
| |
c9------b2
r1
Back to top
View user's profile Send private message MSN Messenger
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Wed Jun 01, 2005 3:21 am    Post subject: Hmmm... Found a counterexample or more likely, don't suss it Reply with quote

I've been writing a Macintosh Sudoku solver for my kids and for giggles.

The Fishy Cycles algorithm looks really interesting, so I took a stab at it.

However, the recommendations it generates on complex puzzles are incorrect, so either it's not correct, or my implementation is bad (much more likely).

AFAICT it is properly computing the vertexes (easy).

However, when I compute the edges and cycles, I get a lot of weird cycles, such as:

1) cycles that repeatedly pass through the same house via different vertexes (ie: going from r1 to r2 through b2, then r2 to c5 through b2, and so on.

2) cycles that contain vertexes in the edges (an edge that is also a vertex).

Even after restricting things so that these conditions cannot occur (ie: a cycle with unique vertexes and edges, where no edge can be a vertex), I still get results that would lead me to incorrectly set squares. So clearly I'm not understanding things properly.

So questions:

1) can a vertex be an edge in a cycle that doesn't contain it as a vertex? Or are vertexes not permitted to even be considered as edges?

2) What restrictions on cycles are there? I would appreciate a more specific definition of what you consider a cycle to be.

Much obliged for any help you can provide.
R
Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Wed Jun 01, 2005 5:32 am    Post subject: Fishy Cycles Reply with quote

cycles that repeatedly pass through the same house via different vertexes (ie: going from r1 to r2 through b2, then r2 to c5 through b2, and so on.

The example you gave and others like it need to be excluded. One
cannot allow a 3-cycle with the same house on all edges.

Example:

abc
A**
*B*
**C

gives a 3-cycle with common edge r1. In this situation, one cannot conclude that r1 can be cleared.

I believe the fix is to restrict the edges to using the cells shared by the vertices only one time in the cycle. (Each of the two cells forming the pair of cells defining the vertex must be part of the two different edges connecting the vertex to the cycle. This is required for the algorithm and was not spelled out in my first post.

Let me know if that fixes the problems!

In answer to 1) I allow vertices to be edges of other cycles.

Now when an edge occurs that is also a vertex, that edge gives no elimination information since one cannot eliminate the locations which define the vertices. (There are only two possibilities in that house already!) However, it might be needed for forming a larger cycle and eliminating elsewhere.

2) I was thinking of simple cycles which contain vertices only once, forming a "loop".
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage


Last edited by Doug on Wed Jun 01, 2005 12:19 pm; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Wed Jun 01, 2005 11:11 am    Post subject: Reply with quote

Doug - this is very interesting. (And thanks for your patience - I notice that the posting has been edited ten times!) First, I'd like to point out that Swordfish, as implemented at http://act365.com/sudoku, isn't limited to rows - though several postings have suggested that it is. Here's a copy of a definition I posted to the Puzzles: plain text / Puzzle 5 (from Swordfish compendium) topic.

Quote:
Here's an attempt at a more precise definition of a Swordfish:

A sector is the generic term for a row, column or box.

A unit-length string comprises two cells within a single sector that are the only possible candidate positions for some given value within that sector.

Two strings are connected if they share a common-cell and have been defined using the same value. Of course, connected strings will have to occur across different sector types - e.g., one string in a column could connect to another in a box.

An n-leg string comprises n connected unit-length stings.

Some logical observations:

Provided that a string has an odd number of legs, exactly one of its end cells must contain the given value.

When we find two strings, each with an odd number of legs, such that their end points lie on the same row (or column), we know that exactly one of the two end-points on each row (or column) must contain the given value. This allows us to eliminate the given value as a candidate for the remaining cells in each row (or column).

More definitions:

When the two strings are of unit length, the pattern is called an X-Wings.

When one or more of the strings has length greater than one, the pattern is known as a Swordfish.


However, since Swordfish doesn't consider cyclic patterns as elegantly as your algorithm, I'll look to update my implementation for the next release. Should anyone be interested in how I locate Swordfish patterns, download the source from http://sf.net/projects/sudoku and look in the file LeastCandidatesHybrid.java, particularly the function LeastCandidatesHybrid.swordfish(StringBuffer). I believe that the code addresses some of the issues discussed by MadOverlord.
Back to top
View user's profile Send private message Visit poster's website
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Wed Jun 01, 2005 1:30 pm    Post subject: Re: Fishy Cycles Reply with quote

Doug,

I'll start coding up your changes ASAP.

One question: Each vertex house has the two special squares (ie: aA in your examples). Consider that two vertexes might share one or both special squares (say, aA and bB where a=b, or consider the intersection between a row and a block, where the two special squares are in the block). Is it legal to form an edge between these two vertexes.

Thinking about it, the only case that really applies is a row and column sharing a single special square; the question is, can the block they intersect in form an edge between them?
Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Thu Jun 02, 2005 12:17 am    Post subject: Fishy Cycles Reply with quote

MadOverlord--

I believe that is ok. Here is an example and the logic works:

***|***|***
*B*|***|***
**a|A**|***
----------------
*bA|***|***
***|***|***
***|***|***

Here the graph has the following structure:

Vertex set: {r3,c3,c2}

Edge set: {Edge {r3,c3} labeled with b1, Edge {c3,c2} labeled with b4, Edge {c3,c2} labeled with r4, Edge {c3,c2} labeled with b1, Edge {c2,r3} labeled with b1}

Notice the parallel edges between c3 and c2. (Three edges in this case!)

In this instance, anyway, it is legitimate to clear houses b1, b4 and r4.

The proof is as follows:

A=F (in r3) -> a=T -> B=F -> b=T -> A=F (in c3) (consistant with a=T and A=F)

A=T (in r3) -> a=F -> A=T (in c3) -> b=F -> B=T (consistant with a=F and A=T).

In either case there is a True in the houses b1,b4, and r4, and so these houses may be cleared.

The point here is that the A in r3 is actually irrelevent. It can be ignored. The triple parallel edges between c3 and c2 give all that is needed for elimination. The extra A in r3 just means that we know the two cells in r3 that have n as a possibility. The A certainly doesn't interfere with the triple edges between c2 and c3 which comprises three different 2-cycles between vertices c2 and c3, depending which pair of edges are chosen to make a cycle, eg, edges b1 and b4 making a 2-cycle, or edges b1 and r4 making a 2-cycle, or edges b4 and r4 making a 2-cycle. Each of these cycles gives elimination information and at least two of them need to be considered to milk all the elimination information. The A in r3 doesn't do any harm. Of course the computer will find it as well as the 3-cycle which has two edges labeled with b1, but the b1 here is redundant. In some cases, of course, the 3-cycles will give new information. "Swordfish" cases, for instance.

Anyway, this degenerate case is ok. Maybe there are some that are not, but I can't think of any.

Remark. If the b were one cell lower, one could not clear r4, but otherwise the logic still would work and b1 and b4 could still be cleared.

Hope that helps.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Thu Jun 02, 2005 12:23 am    Post subject: I implemented Fishy Cycles. Reply with quote

Hey everyone, I got the implementation of Fishy Cycles working. It turns out to be quite straight-forward once you add in the extra constraints that Doug clarified last night.

Here is the code that implements it in RealBasic. I took a quick stab at commenting it so it should be easy to port to Javascript or whatever other language you are using.

I have tested it against the Swordfish and X-Wings samples and it handles them easily.

I'll be releasing my Macintosh solve-assistant in the next few days and will post a link when it's ready; I want to clean some things up first.

BTW, anyone got a link to a place where I can download lots of puzzles in a machine-readable format?

Note: edited to make a minor change suggested by Doug.

Code:

Function deduce_rule8(puzzle() as Integer) As moveList
 
  // Fishy cycles.  See http://www.setbb.com/phpbb/viewtopic.php?t=35&mforum=sudoku
 
  // vertex and edge arrays are declared as globals
  // so they can be accessed during recursion
 
  // vertex() is the list of groups that form vertexes of the graph
  // vSquare(,1) contains the two important squares in the vertex
  // edge(,) is the list of edges (from vertex,to vertex,via edge,into_edge_square,
  //   outof_edge_square)
  //   the vertex and edge numbers are group numbers, not references to vertex()
  //   the into and outof squares define the squares that connect the from vertex
  //   into the edge, and outof the edge to the to vertex
  //
  // cEdge() is the list of edges in the cycle we are trying to build.  It contains
  //   indexes into the edge() array -- not the group number of the edge.
 
  // This code is a little crufty, because it's been modified and hacked at as I
  // learned more details of the Fishy Cycles heuristic.  I will hopefully have
  // the time to clean it up later.
 
  // Some comments for realbasic novices:
  //
  // all arrays are 0-based.
  // my code stores the puzzle() as a list of 81 elements (0-80)
  // internally, all the row/cols/groups are counted from 0.
  // the state of a square is a bitmap of its possibilities (bit 0 = a 1, bit 1 a 2, etc)
  //
  // I have added extra comments to explain realbasic concepts and
  // globals.
 
  Dim i,j,k,l,m,n,o As Integer
  Dim s As String
  Dim ml As new moveList
 
  Dim pSet(26,8) As Integer
  Dim vSquare(-1,1) As Integer
  Dim cEdge(0) As Integer
 
  // debug counter, to limit what we check
 
  tCount = 5
 
  // for each group, count the number of times each possibility occurs
 
  for i = 0 to 26
   
    // clear the array
   
    for j = 0 to 8 // the bit positions 0-8 = possibilities 1-9
      pSet(i,j) = 0
    next j
   
    // for each position in the group.
    // global theGroups(26,8) contains the list of squares in each
    // of the 27 groups (rows/cols/blocks)
   
    for j = 0 to 8
     
      n = puzzle(theGroups(i,j))
     
      // for each bit position
     
      for k = 0 to 8
       
        // if the bit is set, increment the count for that bit position
        // bits(8) contains masks for each bit position (bit(0)=1, bit(1)=3, etc)
       
        if bitwise.bitAnd(n,bits(k)) <> 0 then
         
          pSet(i,k) = pSet(i,k) + 1
         
        end if
       
      next k
     
    next j
   
  next i
 
  // next, for each possibility, create a list of the groups that
  // contain this possibility exactly twice.  These are the vertexes;
  // the two squares are the "special squares"
 
  for i = 0 to 8
   
    // redim changes the size of an array.  redim(-1) sets an array
    // to be empty (no elements).  redim(0) would set it to a single
    // element, since everything is 0-based.
   
    redim vertex(-1)
   
    for j = 0 to 26
     
      // append adds an element to the end of an array, making it
      // one unit larger
     
      if pSet(j,i) = 2 then
        vertex.append j
      end if
     
    next j
   
    // we need only check further if we have found at least 3 vertexes,
    // since that is the minimum you need to get a cycle.  uBound() returns
    // the topmost bound of an array, which because it's 0-based, is
    // one less than the number of elements in the array.
   
    if uBound(vertex) > 1 then
     
      // find the squares in the vertex that match
     
      redim vSquare(uBound(vertex),1)
     
      // logmsg writes a line onto my progress log.  I have commented
      // out a lot of these in the production code
     
      // logmsg "Fishy Cycle : Possibility <" + str(i+1) + ">."
     
      for j = 0 to uBound(vertex)
       
        // rcorb is a little utilty function that takes the number of a group
        // and returns what it is, a row, col or block.  0-8=row,9-17=col,18-26=block
        // theSquare takes a square number (0-80) and returns it in [x=#,y=#] format.
        // showBits returns a string showing the what bits are set in the input.  These
        // are all just output functions.
       
        // s = " Vertex(" + str(j) + ") : " + rcorb(vertex(j)) + " " + groupNum(vertex(j)) + " "
       
        n = 0
        m = bits(i)
        o = vertex(j)
       
        for k = 0 to 8
          if bitwise.bitAnd(puzzle(theGroups(o,k)),m) <> 0 then
            vSquare(j,n) = theGroups(o,k)
            n = n + 1
            // s = s + theSquare(theGroups(o,k)) + "<" + showBits(puzzle(theGroups(o,k))) + "> "
          end if
        next k
       
        // logmsg RTrim(s) + "."
       
      next j
     
      // now we need to find the edges of the graph.  An edge between
      // any two vertexes is any group that contains exactly 1 "special
      // square" from the first vertex and one from the second.
     
      redim edge(-1,4)
     
      // we loop through all the vertexes against each other so we will
      // also generate the backlinks
     
      for j = 0 to uBound(vertex)
        for k = 0 to uBound(vertex)
         
          // obviously, we don't compare a vertex against itself
         
          if j <> k then
           
            // we then look at all of the groups
           
            for l = 0 to 26
             
              // except the two vertex groups, since we need to find one different
              // from them
             
              if (l <> vertex(j)) and (l <> vertex(k)) then
               
                // it is important to recognise that an edge is defined
                // not just by the vertexes and the edge group, but also
                // by the squares used to move between them.  Consider
                // the case of a row vertex linked by a block edge to
                // a column.  Either of the two special squares of the
                // row vertex might get us into the block, and either
                // of the two special squares of the column vertex
                // might get us out.  And if only one gets us in and
                // the same one gets us out, we can't count it.
                // So there could be from 0 to 4 edges to be found.
               
                // the reason we need to go to these lengths is that
                // a cycle (a) cannot revisit any vertices, (b)
                // cannot revisit any special squares [so must use one
                // of each vertex's special squares to get into the
                // vertex, and the other to get out], and (c) cannot
                // use any block as an edge that is being used as
                // a vertex in the cycle.
               
                // whew!
               
                // so, for each of the two special squares in the two
                // vertexes, we check to see if they are also in the
                // group we're considering.  Fortunately, I've precomputed
                // an array isInGroup(square,group) that tells me this
                // info in a single reference.  Can you tell I'm a big
                // fan of precomputing stuff?
               
                // for each of the two special squares in the first vertex
               
                for m = 0 to 1
                 
                  // if that square is in the edge group I am considering
                 
                  if isInGroup(vSquare(j,m),l) then
                   
                    // then check the two possible squares we can exit the
                    // edge via
                   
                    for n = 0 to 1
                     
                      // and if that square is also in the group
                     
                      if isInGroup(vSquare(k,n),l) then
                       
                        // and if they are not the same square
                       
                        if vSquare(j,m) <> vSquare(k,n) then
                         
                          // we have found an edge we need to add
                         
                          o = uBound(edge,1) + 1
                          redim edge(o,4)
                         
                          edge(o,0) = vertex(j) // from this vertex
                          edge(o,1) = vertex(k) // to this vertex
                          edge(o,2) = l // via this edge group
                          edge(o,3) = vSquare(j,m) // entering via this square
                          edge(o,4) = vSquare(k,n) // and leaving via this one
                         
                          // s = " Edge(" + str(o) + ") : " + rcorb(edge(o,0)) + " " + groupNum(edge(o,0)) + " -- "
                          // s = s + theSquare(edge(o,3)) + " -- ("
                          // s = s + rcorb(edge(o,2)) + " " + groupNum(edge(o,2)) + ") -- "
                          // s = s + theSquare(edge(o,4)) + " -- "
                          // s = s + rcorb(edge(o,1)) + " " + groupNum(edge(o,1))
                         
                          // logmsg s
                          // logmsg "  Squares : " + theSquare(edge(m,3)) + " " + theSquare(edge(m,4)) + " " + theSquare(vSquare(k,0)) + " " + theSquare(vSquare(k,1))
                         
                        end if
                       
                      end if
                     
                    next n
                   
                  end if
                 
                next m
               
              end if
             
            next l
           
          end if
         
        next k
      next j
     
      // ok, now we need to have at least 2 edges in order to find cycles.
      // to find the cycles, we just recursively search the set of edges
      // until we find a set that meets our criteria.
     
      // thanks to the structure of our edge list, this turns out to be
      // pretty simple
     
      if uBound(edge) > 0 then
       
        for j = 0 to uBound(edge)
         
          // start with one of the edges
         
          cEdge(0) = j
         
          // find a cycle that does something
         
          ml = deduce_rule8_cycle(puzzle,cEdge,i)
         
          // and return the result if we got one.  ml is a moveList object.
          // it contains a description of the changes that need to be made
          // to the puzzle.  the foundMoves element of moveList is true if
          // we've found something to do.
         
          if ml.foundMoves then
            return ml
          end if
         
        next j
       
      end if
     
    end if
   
  next i
 
  // fail (when the moveList was declared at the top of the function, it was
  // instantiated with foundMoves=false, so this will result in a failure
 
  return ml
 
 
End Function

SudokuSolve.deduce_rule8_cycle:
Function deduce_rule8_cycle(puzzle() As Integer,cE() As Integer,thePossibility As Integer) As moveList
 
  // Fishy cycles.  See http://www.setbb.com/phpbb/viewtopic.php?t=35&mforum=sudoku
 
  Dim i,j,k,m,n,o,p,fVertex,lVertex As Integer
  Dim s As String
  Dim ml As new moveList
  Dim b As Boolean
 
  Dim cEdge(-1),usedGroups(-1),usedSquares(-1),candidates(-1) As Integer
 
  // copy the cEdge info into local variables.  We do this because RealBasic
  // doesn't have call-by-value for array arguments.  We add an extra slot
  // into the array because we're going to need it if we find a completed
  // cycle, or have to recurse.
 
  // for ease of checking and code clarity, we will also build a list of
  // all the edges and vertex groups we have used so far.  No sense passing
  // them down recursively because we'd just have to copy them anyway!
 
  // and by the same token, we'll build a list of the squares we've used so
  // far to connect the edges
 
  // remember, cEdge is an index into the edge array, which is a global
 
  redim cEdge(uBound(cE)+1)
 
  for i = 0 to uBound(cE)
    cEdge(i) = cE(i)
    usedGroups.append edge(cEdge(i),0)
    usedGroups.append edge(cEdge(i),2)
    usedSquares.append edge(cEdge(i),3)
    usedSquares.append edge(cEdge(i),4)
  next i
 
  // the to-vertex of an edge is always the from-vertex of the
  // next edge, so we only have to add the last edge's to-vertex
 
  usedGroups.append edge(cEdge(uBound(cE)),1)
 
  // to make life easier for ourselves in the final "is it a useful
  // cycle?" test, add 2 slots to usedSquares with invalid numbers
  // in them.
 
  usedSquares.append -1
  usedSquares.append -1
 
  // We are looking for cycles such that
  //
  // 1) a group can only appear once in the cycle, either as a vertex or an edge
  // 2) both the special squares in each vertex must be used only once,
  //    to exit and enter the vertex
 
  // keep copies of the first and last vertexes in the chain handy.
  // note that since we incremented the size of cEdge, use uBound(cE)
 
  fVertex = edge(cEdge(0),0)
  lVertex = edge(cEdge(uBound(cE)),1)
 
  // loop through the edges, looking for those that have a from vertex
  // that matches the to vertex of the edge at the end of our current
  // chain
 
  for i = 0 to uBound(edge,1)
   
    // Is the from vertex of the new candidate edge the same
    // as the to vertex of the current last edge?
   
    if edge(i,0) = lVertex then
     
      // Has the special square used to go from the from-vertex
      // of the new edge to the egde group already been used
      // in the construction of the cycle?  If it has, we
      // cannot continue.
     
      // indexOf searches an array and returns the index value
      // of the matching element, or -1 if it can't be found.
      // Since we don't want to find it...
     
      if usedSquares.indexOf(edge(i,3)) = -1 then
       
        // similarly, if the special squarae used to go from
        // the new edge to its to-vertex has already been used,
        // we can give up
       
        if usedSquares.indexOf(edge(i,4)) = -1 then
         
          // Has the edge group of the candidate edge already
          // been used either as an edge or vertex?  If not,
          // then we might be able to add it
         
          if usedGroups.indexOf(edge(i,2)) = -1 then
           
            // Has the new candidate to-vertex already been
            // used either as an edge or vertex?  If not,
            // then we can add it, and recurse to try and
            // complete the cycle.  But if it has, and it
            // happens to point to the first vertex, then
            // have a complete cycle!
           
            if usedGroups.indexOf(edge(i,1)) = -1 then
             
              // We have an edge that meets our restrictions.
              // Add it to the cEdge array (which we thoughtfully
              // expanded above) and recurse to try and complete
              // the chain.
             
              cEdge(uBound(cEdge)) = i
             
              ml = deduce_rule8_cycle(puzzle,cEdge,thePossibility)
             
              // If we get a completed movelist back, immediately
              // return a success
             
              if ml.foundMoves then
                return ml
              end if
             
            else
             
              // at this point, we have a to-vertex that points back
              // into the chain somewhere.  If it happens to point to
              // the first vertex, we've got a valid chain.
             
              if edge(i,1) = fVertex then
               
                // Note that since we already know that the outof_edge
                // special square in our new edge hasn't been used yet,
                // it must by definition be the unused special square
                // in the first vertex.  So now we have a valid
                // cycle.
               
                // however, we are only interested in cycles that
                // have at least three edges in them
               
                if uBound(cEdge) > 1 then
                 
                  cEdge(uBound(cEdge)) = i
                 
                  // Alas, finding a cycle is not enough.  We need to find
                  // a cycle that has edge groups that contain squares that
                  // are not part of the usedSquares but contain thePossibility
                  // This is where those two extra usedSquares slots come in.
                  // We use them to store the two new usedSquares added by our
                  // final edge
                 
                  usedSquares(uBound(usedSquares)-1) = edge(i,3)
                  usedSquares(uBound(usedSquares)) = edge(i,4)
                 
                  // set a flag so we can detect when we find the first
                  // valid clear, so we can output an appropriate message
                  // and return a moveList
                 
                  b = false
                 
                  // So, for each edge group in the cycle
                 
                  for j = 0 to uBound(cEdge)
                   
                    // Find the group of the edge
                   
                    k = edge(cEdge(j),2)
                   
                    // Then for each square in the group.
                   
                    for m = 0 to 8
                     
                      // If the square isn't a special square...
                     
                      n = theGroups(k,m) // the square number
                      o = bits(thePossibility) // bitmask to use to search
                     
                      if usedSquares.indexOf(n) = -1 then
                       
                        // And it's not already solved (technically I don't need this check because
                        // we can't have a solved thePossibility square in any group that is a
                        // edge or vertex, but I'm paranoid and it makes things clearer.
                       
                        if bitCount(puzzle(n)) > 1 then
                         
                          // And the square contains thePossibility as one of its possibilities
                         
                          if bitwise.bitAnd(puzzle(n),o) <> 0 then
                           
                            // We've got a winner!
                           
                            // initialze the moveList
                           
                            if not b then
                             
                              b = true
                             
                              // we've found at least one move, but since they are likely
                              // to be reductions in possibilities and not extra solutions,
                              // we don't trigger a reconstrain - this is my term for
                              // recomputing all the possibilities once we have a new set
                              // of solved squares.
                             
                              ml.foundMoves = true
                              ml.reconstrain = false
                             
                              // generate some nice output for the user
                             
                              s = " Rule 8 : Found a ""Fishy Cycle"" in the puzzle, as follows:" + chr(13) + chr(13)
                             
                              for j = 0 to uBound(cEdge)
                                k = cEdge(j)
                                s = s + "   " + shortGroupName(edge(k,0)) + " -- "
                                s = s + theSquare(edge(k,3)) + " -- ("
                                s = s + shortGroupName(edge(k,2)) + ") -- "
                                s = s + theSquare(edge(k,4)) + " -- "
                                s = s + shortGroupName(edge(k,1)) + chr(13)
                              next j
                             
                              ml.comment = s + chr(13) + "  This lets us remove some possibilities from the edge groups, as follows:" + chr(13) + chr(13)
                             
                            end if
                           
                            // add to the moveList the square (s) and new value (v)
                            // mask() has all bits set except position n, the inverse
                            // of bits()
                           
                            p = bitwise.bitAnd(puzzle(n),mask(thePossibility))
                           
                            ml.s.append n
                            ml.v.append p
                           
                            ml.comment = ml.comment + "  " + theSquare(n) + " - removing <"+ showbits(bitwise.bitAnd(puzzle(n),o)) + "> from <" + showbits(puzzle(n)) + "> leaving <" + showbits(p) + ">." + chr(13)
                           
                            // if the new value results in only one possibility, then
                            // we reconstrain
                           
                            ml.reconstrain = ml.reconstrain or (bitCount(p) = 1)
                           
                          end if
                         
                        end if
                       
                      end if
                     
                    next m
                   
                  next j
                 
                  // if we found a solution, then return it
                 
                  if b then
                    return ml
                  end if
                 
                  // To prevent screwing things up, we need the last two usedSquares
                  // back to -1 before continuing
                 
                  usedSquares(uBound(usedSquares)-1) = -1
                  usedSquares(uBound(usedSquares)) = -1
                 
                 
                end if
               
              end if
             
            end if
           
          end if
        end if
      end if
    end if
  next i
 
  // fail
 
  return ml
 
End Function


Last edited by MadOverlord on Thu Jun 02, 2005 12:53 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Thu Jun 02, 2005 12:46 am    Post subject: Fishy Cycles Reply with quote

Looking through your documentation I noticed:

"// however, we are only interested in cycles that
// have at least three edges in them "

I am not a coder, so maybe I misunderstand, but cycles with two edges are legitimate and give information. See:

http://www.setbb.com/phpbb/viewtopic.php?t=37&start=0&postdays=0&postorder=asc&highlight=&mforum=sudoku

Did I miss something?
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Thu Jun 02, 2005 12:52 am    Post subject: Re: Fishy Cycles Reply with quote

Doug wrote:
I am not a coder, so maybe I misunderstand, but cycles with two edges are legitimate and give information.?


Ok, then I misunderstood. It's easy enough to fix. taptaptap.. okay, doesn't seem to break the code. I'll update my posting with the corrected code.

BTW, I think in your original posting, where you say 9X9 you mean 3X3... (grin)
Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Thu Jun 02, 2005 1:09 am    Post subject: Fishy Cycles Reply with quote

MadOverlord-

Here are a few links to places with puzzles to test against:

Follow the links to the technique descriptions for X-wing and Swordfish here and after the descriptions are some sample puzzles:

http://www.simes.clara.co.uk/programs/sudokutechniques.htm

Also, there are challenge puzzles here:

http://www.sudokusolver.co.uk/challenge.html
and
http://www.sudokusolver.co.uk/challenge2.html

I have another post on this board

http://www.setbb.com/phpbb/viewtopic.php?t=40&mforum=sudoku

which gives an algorithm which resolves the first challenge puzzle above. (When I say resolves, I mean when used with established techniques, say those listed on the first link above along with extensions found here:
http://www.sudokusolver.co.uk/solvemethods.html
and
http://www.sudokusolver.co.uk/codeit.html

I don't know if my second algorithm (linked above), maybe combined with Fishy Cycles, can get the second one, though. I also don't know if Fishy Cycles combined with standard techniques can get the first challenge problem. I kind of doubt it, but I haven't tried it by hand.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Thu Jun 02, 2005 2:39 am    Post subject: Re: Fishy Cycles Reply with quote

Doug wrote:
Also, there are challenge puzzles here:

http://www.sudokusolver.co.uk/challenge.html
and
http://www.sudokusolver.co.uk/challenge2.html

I have another post on this board

http://www.setbb.com/phpbb/viewtopic.php?t=40&mforum=sudoku

which gives an algorithm which resolves the first challenge puzzle above.


I'd already found those challenge problems. Fishy Cycles (plus other standard techniques) doesn't resolve them, but I'll try implementing your implication trees technique next.

Looking at the simes.clara.co.uk stuff, it looks like I'm implementing everything except perhaps his "reducing, part 2" concept (http://www.simes.clara.co.uk/programs/sudokutechnique4.htm).

However, this may be subsumed by other heuristics I'm using.

So far I've implemented:

"It can't be anything else"
"It's the only square in a group that can have that value"

"Simple locked set"

If a set of N squares in a group all have the same set of N possibilities, then we can eliminate those possibilities from the other squares in the group.

Example: if there are 3 squares with possibilities 1, 2 and 3, then one must be 1, one 2 and the other 3; so none of the other 6 squares in the group can be 1, 2 or 3.

A set of two squares with the same two possibilities is referred to as a "locked pair"; a set of three squares with the same three possibilities would be a "locked triplet", and so on.

"Possibility Reduction"

Remove extra possibilities on groups of squares that share the same subset of unique possibilities.

Example: if there are two squares with possibilities 12 and 123, and no other squares have possibilities 1 or 2, then the second square cannot be a 3 (because one square must be a 1, and the other must be the 2).

"Intersection Removal"

Rows and columns intersect with blocks.

If the squares in a row that have a given possibility only intersect a single block, then that possibility must occur in the 3-square intersection of the row and the block, and can be removed from the constraints of the other 6 squares in the block.

Example: consider the first row and the top-left block. If the possibility 1 only appears in the first 3 squares of the row (and is not a possible solution for the other 6 squares), then it must be in those first 3 squares, and therefore cannot be in the other 6 squares of the top-left block.

The same removal can be done with columns vs. blocks, blocks vs. rows, and blocks vs. columns.

"Remote Locked Pairs"

Okay, this is a tough one.

Consider two squares A and B in a row, column or block that have the same two possibilities; these form a "locked pair", and if you find out what A is, you'll know what B is.

Now consider two locked pairs B and C in an intersecting row, column or block. Now A and C form a "complimentary pair"; if you know A, you know C must be same.

Finally, consider two locked pairs C and D in yet another intersecting row, column or block. Now A and D form a "remote locked pair"; they will be in different rows, columns and blocks.

If you can find A and D, they will form two corners of a box, and you can eliminate their possibilities from the squares at the other two corners of the box.

This can be extended further; if you can find locked pairs DE and EF, you have found a remote pair AF, and so on.

"Comprehensive Locked Set"

For each row, column and block, look for a set of N squares that have exactly N possible solutions. Then those solutions must be in the N squares, and can be removed from the other squares of the group.

Since there are many possible sets of N squares, this one is computationally intensive.

This test is a more general version of Simple Locked Set.

and of course,

"Fishy Cycles"

This one I'm not going to even attempt to explain, as it involves enough graph theory to give you a nosebleed.

Any basics that I've missed?
Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Thu Jun 02, 2005 3:42 am    Post subject: Fishy Cycles Reply with quote

If I'm reading you correctly, your method "Comprehensive Locked Sets" is "Expanding Method D" described at:

http://www.sudokusolver.co.uk/codeit.html

Also, the "Removing Candidates II" method you mention is a special case of Fishy Cycles, it arises from 2-cycles. in fact! This is discussed here:

http://www.setbb.com/phpbb/viewtopic.php?t=37&mforum=sudoku

So it is indeed subsumed!

I added a note to my post on the Limited Implication Trees heuristic explaining how I believe Nishio is subsumed by it as well.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Thu Jun 02, 2005 4:29 am    Post subject: Fishy Cycles Reply with quote

MadOverlord--

Looking at the thread:

http://www.setbb.com/phpbb/viewtopic.php?t=12&postdays=0&postorder=asc&start=15&mforum=sudoku

It looks like your "Remote Locked Pairs" algorithm is the same as AMcK's coloring algorithm.

Edit: Oops! Not quite. His definition of "conjugate pair" is a bit different it seems from your "locked pairs". You might want to have a look at his algorithm, well example, anyway.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Thu Jun 02, 2005 5:13 am    Post subject: Re: Fishy Cycles Reply with quote

Doug wrote:
His definition of "conjugate pair" is a bit different it seems from your "locked pairs"


I looked in the thread and also did a search but couldn't find an explanation of the algorithm. Can you point my tired eyes to it?

In case I didn't mention it, I learned about remote locked pairs from

http://www.scanraid.com/remotepairs.htm
Back to top
View user's profile Send private message Visit poster's website AIM Address
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page 1, 2, 3  Next
Page 1 of 3

 
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