/*****************************************************************************
**
** Soo.cs
**
*****************************************************************************/
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
class Soo
{ public enum Difficulty
{ UNKNOWN = 0,
EASY,
NORMAL,
HARD,
FIENDISH,
DIABOLICAL,
IMPOSSIBLE
};
private const int MAX_CHAIN = Grid.Size;
private const int MAX_FISH = (Grid.Size / 2) + 1;
private const int MAX_SUBSET = Grid.Size - Grid.BoxSize;
/* -----------------------------------------------------------------------
VARIABLES
----------------------------------------------------------------------- */
#region "VARIABLES"
protected Difficulty _difficulty;
protected Grid _grid;
protected List<Hint> _hints;
protected bool? _possible;
protected bool? _solved;
protected string _strDetails;
protected House[] _housesBox = new House[ Grid.Size ];
protected House[] _housesColumn = new House[ Grid.Size ];
protected House[] _housesRow = new House[ Grid.Size ];
#endregion
/* -----------------------------------------------------------------------
CONSTRUCTOR
----------------------------------------------------------------------- */
#region "Constructor"
public
Soo()
{ _grid = new Grid();
_hints = new List<Hint>();
for (int idx = 0; idx < Grid.Size; ++idx)
{ _housesBox[ idx ] = new House( this, idx, Grid.House.Box );
_housesColumn[ idx ] = new House( this, idx, Grid.House.Column );
_housesRow[ idx ] = new House( this, idx, Grid.House.Row );
}
Reset();
} /* end of Soo::Soo() */
#endregion
/* -----------------------------------------------------------------------
PUBLIC METHODS
----------------------------------------------------------------------- */
public String
DisplaySolution()
{ StringBuilder sb = new StringBuilder( _hints.Count * 64 );
foreach (Hint hint in _hints)
{ switch (hint.type)
{ case Hint.HintType.SET_VALUE:
sb.AppendFormat( "{0} => {1}\t\t{2}\n", Grid.SqName( hint.index ),
hint.iValue,
hint.strWhy );
break;
case Hint.HintType.ELIMINATE_CANDIDATE:
sb.AppendFormat( "{0} => not {1}\t\t{2}\n", Grid.SqName( hint.index ),
hint.iValue,
hint.strWhy );
break;
}
}
if (Solved)
sb.Append( _grid.Display() );
else
{ sb.Append( _grid.DisplayMarks() );
sb.Append("\n"); sb.Append( _grid.DisplayShortForm('.') ); }
sb.AppendFormat("\nDifficulty: {0}\n", _difficulty.ToString() );
return sb.ToString();
} /* end of Soo::DisplaySolution() */
///
/// <summary>
/// Eliminates a candidate for a given square
/// </summary>
/// <returns>TRUE if candidate eliminated, FALSE otherwise</returns>
/// <param name="index">Index of square</param>
/// <param name="iValue">Value to be eliminated</param>
///
public bool
EliminateCandidate( int index, int iValue )
{ if (_grid[ index ].ClearCandidate( iValue ))
{ Hint hint;
#if TRACE_SOLVE
Console.WriteLine( _grid.DisplayMarks() );
Console.WriteLine( "{0} => not {1}\t\t{2}", Grid.SqName( index ), iValue, _strDetails );
#endif
hint.type = Hint.HintType.ELIMINATE_CANDIDATE;
hint.index = index;
hint.iValue = iValue;
hint.strWhy = _strDetails;
_hints.Add( hint );
return true;
}
return false;
} /* end of Soo::EliminateCandidate() */
///
/// <summary>
/// Parses a string and attempts to build a valid grid from it
/// </summary>
/// <returns>TRUE if parsed successfully, FALSE otherwise</returns>
/// <param name="strRaw">Raw string to parse</param>
///
public bool
Parse( string strRaw )
{ Reset();
if (_grid.Parse(strRaw, out _strDetails) &&
isSolvable())
{ //
// Make sure the solution is unique
//
if (_grid.EmptyCount == 0)
return true; // already solved?
DancingLinks dlx = new DancingLinks( );
if (dlx.Solve( _grid, false ) == 1)
return true;
_strDetails = (dlx.Solutions == 0) ?
"Does not have a solution." :
"Does not have a unique solution.";
}
return false;
} /* end of Soo::Parse() */
///
/// <summary>
/// Resets the game to it's initial (blank) state
/// </summary>
///
public void
Reset()
{ _difficulty = Difficulty.UNKNOWN;
_possible = null;
_solved = null;
_strDetails = "";
_hints.Clear();
_grid.Reset();
} /* end of Soo::Reset() */
///
/// <summary>
/// Assigns a value to a square
/// </summary>
/// <param name="index">Index of square</param>
/// <param name="iValue">Value to be assigned</param>
///
public void
SetSquare( int index, int iValue )
{ if (_grid.Set( index, iValue ))
{ Hint hint;
#if TRACE_SOLVE
Console.WriteLine( _grid.DisplayMarks() );
Console.WriteLine( "{0} => {1}\t\t{2}", Grid.SqName( index ), iValue, _strDetails );
#endif
hint.type = Hint.HintType.SET_VALUE;
hint.index = index;
hint.iValue = iValue;
hint.strWhy = _strDetails;
_hints.Add( hint );
//
// Grid has changed, so the solvable/solved state is now unknown.
//
_possible = null;
_solved = null;
}
} /* end of Soo::SetSquare() */
///
/// <summary>
/// Attempts to solve the puzzle
/// </summary>
/// <returns>TRUE if solved, FALSE otherwise</returns>
///
public bool
Solve()
{ _hints.Clear();
try
{ while (!isSolved() && SolveStep())
{ /* EMPTY LOOP */ } }
catch (IllegalValueException ex)
{ _difficulty = Difficulty.IMPOSSIBLE;
_possible = false;
_strDetails = String.Format( "The value '{0}' at square {1} is illegal.", ex.iValue, Grid.SqName( ex.index ) );
throw new ApplicationException(_strDetails);
}
catch (UnsolvableSquareException ex)
{ _difficulty = Difficulty.IMPOSSIBLE;
_possible = false;
_strDetails = String.Format( "Square {0} has no possible value.", Grid.SqName( ex.index ) );
throw new ApplicationException(_strDetails);
}
return Solved;
} /* end of Soo::Solve() */
///
/// <summary>
/// Solves the puzzle
/// </summary>
/// <returns>TRUE if solved, FALSE otherwise</returns>
///
public bool
SolveStep()
{ int iHouse;
if (findNakedSingles())
{ if (_difficulty < Difficulty.EASY)
_difficulty = Difficulty.EASY;
return true;
}
for (iHouse = 0; iHouse < Grid.Size; ++iHouse)
if (_housesBox[ iHouse ].FindHiddenSingles() ||
_housesColumn[ iHouse ].FindHiddenSingles() ||
_housesRow[ iHouse ].FindHiddenSingles())
{ if (_difficulty < Difficulty.EASY)
_difficulty = Difficulty.EASY;
return true;
}
for (iHouse = 0; iHouse < Grid.Size; ++iHouse)
if (_housesBox[ iHouse ].FindNakedPairs() ||
_housesColumn[ iHouse ].FindNakedPairs() ||
_housesRow[ iHouse ].FindNakedPairs() ||
_housesBox[ iHouse ].FindBoxLineReductions() ||
_housesColumn[ iHouse ].FindBoxLineReductions() ||
_housesRow[ iHouse ].FindBoxLineReductions())
{ if (_difficulty < Difficulty.NORMAL)
_difficulty = Difficulty.NORMAL;
return true;
}
for (iHouse = 0; iHouse < Grid.Size; ++iHouse)
if (_housesBox[ iHouse ].FindSubsets( MAX_SUBSET ) ||
_housesColumn[ iHouse ].FindSubsets( MAX_SUBSET ) ||
_housesRow[ iHouse ].FindSubsets( MAX_SUBSET ))
{ if (_difficulty < Difficulty.HARD)
_difficulty = Difficulty.HARD;
return true;
}
if (findFish() ||
findWings() ||
findColors() ||
findChains() ||
findRectangles())
{ if (_difficulty < Difficulty.FIENDISH)
_difficulty = Difficulty.FIENDISH;
return true;
}
if (_difficulty < Difficulty.DIABOLICAL)
_difficulty = Difficulty.DIABOLICAL;
return false;
} /* end of Soo::SolveStep() */
/* -----------------------------------------------------------------------
PRIVATE METHODS
----------------------------------------------------------------------- */
#region "PRIVATE METHODS"
///
/// <summary>
/// Eliminate candidates based on "XY-Chains" strategy
/// </summary>
/// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
///
private bool
findChains()
{ Square sq;
int iPeer,
iSecond;
uint uLink;
int[] iList = new int[ MAX_CHAIN ];
for (int iFirst = 0; iFirst < Grid.Squares; ++iFirst)
{ sq = _grid[ iFirst ];
if (sq.CandidateCount != 2)
continue;
for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
{ iSecond = Grid.NthPeer( iFirst, iPeer );
if (_grid[ iSecond ].IsEmpty &&
_grid[ iSecond ].CandidateCount == 2)
{ uLink = _grid.SharedCandidates( iFirst, iSecond );
if (uLink != 0 &&
BitSet.CountBits(uLink) == 1)
{ iList[ 0 ] = iFirst;
iList[ 1 ] = iSecond;
if (goChaining( uLink, 2, iList ))
return true;
}
}
}
}
return false;
}
///
/// <summary>
/// Eliminate candidates based on "Simple Coloring" strategy
/// </summary>
/// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
///
private bool
findColors()
{ int index,
iHere,
iPeer,
iValue;
bool bFound = false;
int[] iColors = new int[ Grid.Squares ];
for (iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
{ if (_grid.CountValues( iValue ) >= (Grid.Size - 1))
continue;
for (index = 0; index < Grid.Squares; ++index)
{ if (!_grid[ index ].Candidates.Test( iValue ))
continue;
for (int idx = 0; idx < Grid.Squares; ++idx)
iColors[idx] = 0;
iColors[index] = 1;
if (goColoring(iValue, 1, index, iColors))
{ int iSeen,
iTarget;
for (iHere = 0; iHere < Grid.Squares; ++iHere)
{ if ((iSeen = iColors[iHere]) == 0)
{ if (_grid[ iHere ].IsEmpty &&
_grid[ iHere ].Candidates.Test( iValue ))
{ for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
{ iTarget = Grid.NthPeer( iHere, iPeer );
if (iColors[ iTarget ] != 0 &&
iColors[ iTarget ] != iSeen)
{ if (iSeen == 0)
iSeen = iColors[ iTarget ];
else
{ _strDetails = "SIMPLE COLORING";
if (EliminateCandidate(iHere, iValue))
bFound = true;
}
}
}
if (bFound)
return true;
}
}
else
{ //
// Look for two squares of the same color that share the
// same box, row, or column. If we find this, then all of
// the squares of the OTHER color can be set to the current
// value.
//
for (Grid.House house = Grid.House.Box; house <= Grid.House.Row; ++house)
{ iTarget = iHere;
while ((iTarget = Grid.NextSq(iTarget, house)) != iHere)
if (iColors[iTarget] == iSeen)
{ for (int iTrue = 0; iTrue < Grid.Squares; ++iTrue)
if (iColors[iTrue] != 0 && iColors[iTrue] != iSeen)
{ _strDetails = "SIMPLE COLORING (EXCLUSION)";
SetSquare(iTrue, iValue);
bFound = true;
}
if (bFound)
return true;
}
}
}
}
}
}
}
return bFound;
} /* end of findColors() */
///
/// <summary>
/// Eliminate candidates based on "Swordfish" or "Jellyfish" strategies
/// </summary>
/// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
/// <remarks>
/// SWORDFISH: three columns with only two candidates for a given digit.
/// If these fall on exactly three common rows, and each of those rows has
/// at least two candidate cells, then all three rows can be cleared of
/// that digit - except in the defining cells. This is the original,
/// "restrictive" definition. It has since been realised that a more
/// relaxed definition is possible, in that the three columns can each
/// have two or three candidates for the given digit -- as long as they
/// fall on the three common rows.
/// </remarks>
///
private bool
findFish()
{ int iCount,
iLine;
uint uSquare;
int[] iLines = new int[ MAX_FISH ];
uint[] uSquares = new uint[ MAX_FISH ];
for (int iMaxDepth = 2; iMaxDepth < MAX_FISH; ++iMaxDepth)
for (int iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
{ for (iLine = 0; iLine < (Grid.Size - iMaxDepth); ++iLine)
{ iCount = _housesRow[ iLine ].GetCandidateSquares( iValue, out uSquare );
if (iCount >= 2 && iCount <= iMaxDepth)
{ iLines[ 0 ] = iLine;
uSquares[ 0 ] = uSquare;
if (goFishing( iValue, 1, iMaxDepth, iLines, uSquare, uSquares, ref _housesRow ))
return true;
}
iCount = _housesColumn[ iLine ].GetCandidateSquares( iValue, out uSquare );
if (iCount >= 2 && iCount <= (Grid.Size - iMaxDepth))
{ iLines[ 0 ] = iLine;
uSquares[ 0 ] = uSquare;
if (goFishing( iValue, 1, iMaxDepth, iLines, uSquare, uSquares, ref _housesColumn ))
return true;
}
}
}
return false;
} /* end of Soo::findFish() */
///
/// <summary>
/// Finds all NAKED SINGLE squares
/// </summary>
/// <returns>TRUE if one or more found, FALSE otherwise</returns>
/// <remarks>
/// NAKED SINGLE is when a square has only one possible candidate.
/// </remarks>
///
private bool
findNakedSingles()
{ Square sq;
int iValue;
bool bFound = false;
for (int index = 0; index < Grid.Squares; ++index)
{ sq = _grid[ index ];
if (sq.CandidateCount == 1)
{ iValue = sq.Candidates.FirstBit;
Debug.Assert( Grid.IsValidValue( iValue ) );
_strDetails = "NAKED SINGLE";
SetSquare( index, iValue );
bFound = true;
//
// Reset the counter to the lowest peer of this square
//
if (_grid.EmptyCount > 0)
index = Math.Min(index, Grid.NthPeer(index, 0) - 1);
else
break;
}
}
return bFound;
} /* end of Soo::findNakedSingles() */
///
/// <summary>
/// Finds the first UNIQUE RECTANGLE
/// </summary>
/// <returns>TRUE if one or more found, FALSE otherwise</returns>
/// <remarks>
/// </remarks>
///
private bool
findRectangles()
{ int iBase,
iCorner1,
iCorner2,
iTarget,
iValue;
uint uDeadlyBits;
bool bFound = false;
BitSet setBoxes = new BitSet();
for (iBase = 0; iBase < Grid.Squares; ++iBase)
{ if (_grid[ iBase ].CandidateCount != 2)
continue;
uDeadlyBits = _grid[ iBase ].Candidates.Bits;
//
// iBase is now the "base corner" that we'll work off of: try to
// find a square in the same row with the same pair, and then a
// second square in the same column with the same pair.
//
iCorner1 = iBase;
while ((iCorner1 = Grid.NextSq(iCorner1, Grid.House.Column)) != iBase)
if (_grid[iCorner1].Candidates.Bits == uDeadlyBits)
break;
if (iCorner1 == iBase)
continue; // didn't find a first candidate
iCorner2 = iBase;
while ((iCorner2 = Grid.NextSq(iCorner2, Grid.House.Row)) != iBase)
if (_grid[iCorner2].Candidates.Bits == uDeadlyBits)
break;
if (iCorner2 == iBase)
continue; // didn't find a second candidate
iTarget = (Grid.GetRow(iCorner1) * Grid.Size) + Grid.GetColumn(iCorner2);
Debug.Assert( Grid.IsValidIndex(iTarget) );
if ((_grid[iTarget].Candidates.Bits & uDeadlyBits) != uDeadlyBits)
continue; // fourth corner doesn't contain the "deadly bits"
//
// The key to a "unique rectangle" is that it must occupy
// exactly TWO boxes, TWO columns, and TWO rows. Because we
// searched by row and column, we know that there are already
// 2 columns and rows, but we have to make sure that there are
// only two boxes.
//
setBoxes.ClearAll();
setBoxes.Set( Grid.GetBox(iBase) );
setBoxes.Set( Grid.GetBox(iCorner1) );
setBoxes.Set( Grid.GetBox(iCorner2) );
setBoxes.Set( Grid.GetBox(iTarget) );
if (setBoxes.Count == 2)
{ //
// Found a unique rectangle, so we can remove the "deadly
// bits" from the final corner.
//
_strDetails = String.Format("UNIQUE RECTANGLE: {0} - {1} - {2} - {3}", Grid.SqName(iBase), Grid.SqName(iCorner1),
Grid.SqName(iCorner2), Grid.SqName(iTarget));
for (iValue = BitSet.FindFirst(uDeadlyBits);
iValue > 0;
iValue = BitSet.FindNext(uDeadlyBits, iValue + 1))
{ if (EliminateCandidate(iTarget, iValue))
bFound = true;
}
if (bFound)
return true;
}
}
return bFound;
} /* end of Soo::findRectangles() */
///
/// <summary>
/// Eliminate candidates based on "Y-Wing" strategy
/// </summary>
/// <returns>TRUE if one or more candidates eliminated, FALSE otherwise</returns>
///
private bool
findWings()
{ int idx,
iCount,
iPeer,
iPeerHi,
iPeerLo,
iWingHi,
iWingLo;
uint uBitsHi,
uBitsLo,
uBitsPivot;
bool bFound = false;
for (int iPivotSq = 0; iPivotSq < (Grid.Squares - 2); ++iPivotSq)
{ iCount = _grid[ iPivotSq ].CandidateCount;
if (!(iCount == 2 || iCount == 3))
continue;
//
// Search for another square with only 2 candidates that intersects
// the pivot square and shares one common value. This square is the
// "Wing #1" square.
//
for (iPeerLo = 0; iPeerLo < Grid.Peers; ++iPeerLo)
{ iWingLo = Grid.NthPeer( iPivotSq, iPeerLo );
if (_grid[ iWingLo ].CandidateCount != 2)
continue;
uBitsPivot = _grid[ iPivotSq ].Candidates.Bits;
uBitsLo = _grid[ iWingLo ].Candidates.Bits;
if (BitSet.CountBits( uBitsPivot & uBitsLo ) != (iCount - 1))
continue;
if (iCount == 3)
{ //
// XYZ-WING: three cells that contain only 3 different numbers
// between them, but which fall outside the confines of one
// row/column/box, with one of the cells (the 'hinge') being
// able to see the other two; those other two having only one
// number in common; and the hinge having all three numbers as
// candidates.
//
for (iPeerHi = 0; iPeerHi < Grid.Peers; ++iPeerHi)
{ iWingHi = Grid.NthPeer( iPivotSq, iPeerHi );
if (Grid.Intersects( iWingLo, iWingHi ) ||
_grid[ iWingHi ].CandidateCount != 2)
{ continue;
}
uBitsHi = _grid[ iWingHi ].Candidates.Bits;
if ((uBitsLo & uBitsPivot) == (uBitsHi & uBitsPivot) ||
BitSet.CountBits( uBitsPivot & uBitsHi ) != 2 ||
BitSet.CountBits( uBitsPivot | uBitsLo | uBitsHi ) != 3)
{ continue;
}
//
// Found a possible XYZ-WING
//
Debug.Assert( BitSet.CountBits( uBitsLo & uBitsHi ) == 1 );
int iValue = BitSet.FindFirst( uBitsLo & uBitsHi );
for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
{ idx = Grid.NthPeer( iWingLo, iPeer );
if (Grid.Intersects( idx, iPivotSq ) &&
Grid.Intersects( idx, iWingHi ) &&
_grid[ idx ].Candidates.Test( iValue ))
{ _strDetails = String.Format( "XYZ-WING (Hinge {0} Wings {1} - {2})", Grid.SqName( iPivotSq ),
Grid.SqName( iWingLo ),
Grid.SqName( iWingHi ) );
if (EliminateCandidate( idx, iValue ))
bFound = true;
}
}
if (bFound)
return true;
}
}
else
{ //
// Now find a third square that intersects pivot square,
// but NOT Wing #1) and shares one (and only one) candidate
// with both "Wing #1" and the pivot. This is the "Wing #2"
// square.
//
for (iPeerHi = 0; iPeerHi < Grid.Peers; ++iPeerHi)
{ iWingHi = Grid.NthPeer( iPivotSq, iPeerHi );
if (iWingHi == iWingLo ||
Grid.Intersects( iWingLo, iWingHi ) ||
_grid[ iWingHi ].CandidateCount != 2)
{ continue;
}
uBitsHi = _grid[ iWingHi ].Candidates.Bits;
if ((uBitsLo & uBitsPivot) == (uBitsHi & uBitsPivot) ||
BitSet.CountBits( uBitsPivot & uBitsHi ) != 1 ||
BitSet.CountBits( uBitsPivot | uBitsLo | uBitsHi ) != 3)
{ continue;
}
//
// At this point, the mark shared by both wings can be
// eliminated from all squares that intersect with BOTH
// wings, except for the pivot square.
//
int iValue = BitSet.FindFirst( uBitsLo & uBitsHi );
Debug.Assert( Grid.IsValidValue( iValue ),
"Soo::findYWing() => no common mark!" );
for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
{ if ((idx = Grid.NthPeer( iWingLo, iPeer )) != iPivotSq &&
Grid.Intersects( idx, iWingHi ) &&
_grid[ idx ].Candidates.Test( iValue ))
{ _strDetails = String.Format( "Y-WING (Pivot {0} Wings {1} - {2})", Grid.SqName( iPivotSq ),
Grid.SqName( iWingLo ),
Grid.SqName( iWingHi ) );
if (EliminateCandidate( idx, iValue ))
bFound = true;
}
}
if (bFound)
return true;
}
//
// XY-WING -- find a Wing #2 that intersects and shares a
// common candidate with the Pivot wing, but does NOT
// intersect Wing #1.
//
for (iPeerHi = 0; iPeerHi < Grid.Peers; ++iPeerHi)
{ iWingHi = Grid.NthPeer( iPivotSq, iPeerHi );
if (iWingHi == iWingLo ||
Grid.Intersects( iWingLo, iWingHi ) ||
_grid[ iWingHi ].CandidateCount != 2)
{ continue;
}
uBitsHi = _grid[ iWingHi ].Candidates.Bits;
if ((uBitsLo & uBitsPivot) == (uBitsHi & uBitsPivot) ||
BitSet.CountBits( uBitsPivot & uBitsHi ) != 1 ||
BitSet.CountBits( uBitsPivot | uBitsLo | uBitsHi ) != 3)
{ continue;
}
//
// At this point, the mark shared by both wings--but NOT
// in the pivot square--can be eliminated from any squares
// that intersect BOTH wings.
//
int iValue = BitSet.FindFirst( (uBitsLo | uBitsHi) & ~uBitsPivot );
Debug.Assert( Grid.IsValidValue( iValue ),
"Soo::findYWing() => no common mark!" );
for (iPeer = 0; iPeer < Grid.Peers; ++iPeer)
{ if ((idx = Grid.NthPeer( iWingLo, iPeer )) != iPivotSq &&
Grid.Intersects( idx, iWingHi ) &&
_grid[ idx ].Candidates.Test( iValue ))
{ _strDetails = String.Format( "XY-WING (Pivot {0} Wings {1} - {2})", Grid.SqName( iPivotSq ),
Grid.SqName( iWingLo ),
Grid.SqName( iWingHi ) );
if (EliminateCandidate( idx, iValue ))
bFound = true;
}
}
if (bFound)
return true;
}
}
}
}
return bFound;
} /* end of Soo::findWings() */
///
/// <summary>
/// Recursive routine to find chained values
/// </summary>
/// <returns>TRUE if chain found, FALSE otherwise</returns>
/// <param name="uLink">Value linked from previous pair</param>
/// <param name="iLength">Length of chain built so far</param>
/// <param name="iList">Array of chained squares</param>
///
private bool
goChaining( uint uLink, int iLength, int[] iList )
{ Square sq;
int idx,
iPeer,
iPrev;
uint uNextLink;
bool bFound = false;
if (iLength >= MAX_CHAIN)
return false;
Debug.Assert( iLength > 1 );
Debug.Assert( BitSet.CountBits( uLink ) == 1 );
iPrev = iList[ iLength - 1 ];
uNextLink = _grid[ iPrev ].Candidates.Bits & ~uLink;
for (iPeer = 0; iPeer < Grid.Peers; iPeer++)
{ sq = _grid[ Grid.NthPeer( iPrev, iPeer ) ];
if (sq.CandidateCount != 2 ||
(sq.Candidates.Bits & uNextLink) == 0 ||
Utility.ArrayContains( sq.Index, iList, iLength ))
{ continue;
}
iList[ iLength++ ] = sq.Index;
if (goChaining( uNextLink, iLength, iList ))
return true;
//
// Didn't find a longer chain, so test what we have to see if
// it's valid. It must be an odd length and the end-points must
// share a common value that wasn't used in the chain. If so,
// then that common value can be excluded from all squares
// visible to BOTH endpoints.
//
if (iLength > 2 && (iLength & 0x0001) == 1)
{ int iSq,
iTarget,
iValue;
uint uHeadLink,
uTarget;
uHeadLink = _grid.SharedCandidates( iList[ 0 ], iList[ 1 ] );
uTarget = _grid[ iList[ 0 ] ].Candidates.Bits & ~uHeadLink;
iValue = BitSet.FindFirst( uTarget );
if (Grid.IsValidValue( iValue ) &&
sq.Candidates.Test(iValue) &&
!_grid[ iPrev ].Candidates.Test(iValue))
{ StringBuilder sb = new StringBuilder();
for (iTarget = 0; iTarget < Grid.Peers; ++iTarget)
{ iSq = Grid.NthPeer( sq.Index, iTarget );
if (_grid[ iSq ].Candidates.Test( iValue ) &&
Grid.Intersects( iSq, iList[ 0 ] ))
{ if (sb.Length == 0)
{ sb.Append( "CHAIN: " );
for (idx = 0; idx < iLength; ++idx)
{ if (idx > 0)
sb.Append( "-" );
sb.AppendFormat( "{0}", Grid.SqName( iList[ idx ] ) ); }
}
_strDetails = sb.ToString();
/*
Console.WriteLine( "\n\n{0}\n{1}\nValue: {2}", _grid.DisplayMarks(), sb.ToString(), iValue );
&