Posted: Sun May 29, 2005 11:27 am Post subject: Fishy Cycles

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

[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

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

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

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.

Posted: Wed Jun 01, 2005 5:32 am Post subject: Fishy Cycles

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

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.

Posted: Wed Jun 01, 2005 1:30 pm Post subject: Re: Fishy Cycles

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?

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.

Posted: Thu Jun 02, 2005 12:23 am Post subject: I implemented Fishy Cycles.

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

// 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.

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))

// 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)

// 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

// 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))

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

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.

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

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

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