/*****************************************************************************
**
** 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 );
throw new ApplicationException();
*/
if (EliminateCandidate( iSq, iValue ))
bFound = true;
}
}
if (bFound)
return true;
}
}
iLength--; // discard this link
}
return false;
}
///
/// <summary>
/// Recursive search for 'colored' squares
/// </summary>
/// <param name="iValue">Value to search for</param>
/// <param name="iDepth">Current length of the colored chain</param>
/// <param name="iHere">Last colored squares</param>
/// <param name="iColors">Array of current square colors</param>
/// <returns>"FALSE" color</returns>
///
private bool
goColoring( int iValue, int iDepth, int iHere, int[] iColors )
{ int iCount,
iPair,
iPeer;
bool bColored = false;
for (Grid.House house = Grid.House.Box; house <= Grid.House.Row; ++house)
{ iCount = 1;
iPair = -1;
iPeer = iHere;
while ((iPeer = Grid.NextSq(iPeer, house )) != iHere)
{ if (_grid[ iPeer ].Candidates.Test( iValue ))
{ iPair = iPeer;
if (++iCount > 2)
break;
}
}
if (iCount == 2 &&
iColors[ iPair ] == 0)
{/*
Console.WriteLine("{0}: colored {1} as {2}", iDepth, Grid.SqName(iPair), iColor);
*/
bColored = true;
iColors[ iPair ] = (iDepth % 2) + 1;
goColoring( iValue, iDepth + 1, iPair, iColors );
}
}
return bColored;
}
///
/// <summary>
/// Recursive routine to find fish (SWORDFISH, JELLYFISH, etc.)
/// </summary>
/// <param name="iValue">Value to fish for</param>
/// <param name="iDepth">Current depth</param>
/// <param name="iMaxDepth">Maximum depth</param>
/// <param name="iLines">Array of offsets where previous candidates found</param>
/// <param name="uSetAll">Mask of squares where candidates found</param>
/// <param name="uSquares">Array of square masks</param>
/// <param name="houses">Array of houses to search</param>
/// <returns>TRUE if candidate elminiated, FALSE otherwise</returns>
///
private bool
goFishing( int iValue, int iDepth, int iMaxDepth, int[] iLines,
uint uSetAll, uint[] uSquares, ref House[] houses )
{ int iLine;
bool bFound = false;
if (iDepth < iMaxDepth)
{ int iCount,
iLastLine;
uint uSquare;
Debug.Assert( iDepth > 0 );
iLastLine = Grid.Size - (iMaxDepth - (iDepth + 1));
for (iLine = iLines[ iDepth - 1 ] + 1; iLine < iLastLine; ++iLine)
{ iCount = houses[ iLine ].GetCandidateSquares( iValue, out uSquare );
if ((iCount >= 2 && iCount <= iMaxDepth) &&
(uSetAll & uSquare) != 0 &&
BitSet.CountBits( uSetAll | uSquare ) <= iMaxDepth)
{ uSetAll |= uSquare;
iLines[ iDepth ] = iLine;
uSquares[ iDepth ] = uSquare;
if (goFishing( iValue, iDepth + 1, iMaxDepth, iLines, uSetAll, uSquares, ref houses ))
bFound = true;
}
}
}
else
{ int idx, iLineStop;
StringBuilder sb = new StringBuilder();
switch (iDepth)
{ case 2:
sb.Append( "X-WING" );
break;
case 3:
sb.Append( "SWORDFISH" );
break;
case 4:
sb.Append( "JELLYFISH" );
break;
case 5:
sb.Append( "SQUIRMBAG" );
break;
default:
sb.AppendFormat( "GRONK-{0}", iDepth ); break;
}
sb.Append( (houses == _housesColumn) ? " BY COLUMN: " : " BY ROW: " );
for (idx = 0; idx < iDepth; ++idx)
{ if (idx > 0)
sb.Append( " - " );
sb.Append( houses[ iLines[ idx ] ].SqList( uSquares[ idx ] ) );
}
_strDetails = sb.ToString();
//
// At this point, iLines[] has rows/columns to be skipped,
// so start at the top and advance to the next skip line.
//
for (idx = iLine = 0; idx <= iDepth; ++idx, ++iLine)
{ iLineStop = (idx < iDepth) ? iLines[ idx ] : Grid.Size;
for (; iLine < iLineStop; ++iLine)
if (houses[ iLine ].EliminateCandidateSquares( iValue, uSetAll ))
bFound = true;
}
}
return bFound;
} /* end of Soo::goFishing() */
///
///
/// <summary>
/// Verifies that the current grid can be solved.
/// </summary>
/// <returns>TRUE if solvable, FALSE otherwise</returns>
///
private bool
isSolvable()
{ if (_possible.HasValue)
return (bool)(_possible);
_possible = false;
_strDetails = "";
//
// Check to make sure we have enough starting positions
//
if (_grid.FilledCount < Grid.StartingValues)
{ _difficulty = Difficulty.IMPOSSIBLE;
_strDetails = "Not enough starting values.";
return false;
}
//
// Now check each house to ensure that it is solvable.
//
for (int iHouse = 0; iHouse < Grid.Size; ++iHouse)
{ if (!_housesBox[ iHouse ].IsSolvable( _strDetails ) ||
!_housesColumn[ iHouse ].IsSolvable( _strDetails ) ||
!_housesRow[ iHouse ].IsSolvable( _strDetails ))
{ _difficulty = Difficulty.IMPOSSIBLE;
return false;
}
}
_possible = true;
return true;
} /* end of Soo::isSolvable() */
///
/// <summary>
/// Determines if a puzzle has been solved
/// </summary>
/// <returns>TRUE if solved, FALSE otherwise</returns>
///
private bool
isSolved()
{ if (!_solved.HasValue)
{ _solved = false;
if (_grid.EmptyCount == 0)
{ //
// Now check each house to ensure that it has been solved.
//
for (int iHouse = 0; iHouse < Grid.Size; ++iHouse)
{ if (!_housesBox[ iHouse ].IsSolved() ||
!_housesColumn[ iHouse ].IsSolved() ||
!_housesRow[ iHouse ].IsSolved())
{ return false;
}
}
_solved = true;
}
}
return (bool)(_solved);
} /* end of Soo::isSolved() */
#endregion
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
///
/// <summary>
/// Retrieves a square on the puzzle.
/// </summary>
/// <returns>Square</returns>
/// <param name="index">Index of desired square</param>
///
public Square
this[ int index ]
{ get
{ return _grid[ index ];
}
}
///
/// <summary>
/// Returns more information about the previous action
/// </summary>
/// <returns>Text in human-readable form.</returns>
///
public string
Details
{ get
{ return _strDetails;
}
set
{ _strDetails = value;
}
} /* end of Soo::Details() */
///
/// <summary>
/// Returns the relative difficulty of the current puzzle
/// </summary>
/// <returns>Difficulty level</returns>
///
public Difficulty
Level
{ get
{ return _difficulty; }
} /* end of Soo::Level */
///
/// <summary>Property that exposes the Grid variable</summary>
///
public Grid
Grid
{ get
{ return _grid;
}
set { _grid = value;
_hints.Clear();
_difficulty = Difficulty.UNKNOWN;
_possible = null;
_solved = null;
}
} /* end of Soo::Grid() */
///
/// <summary>
/// Returns a list of hints
/// </summary>
/// <returns>Hint list</returns>
///
public List<Hint>
Hints
{ get
{ return _hints;
}
} /* end of Soo::Details() */
///
/// <summary>
/// Tests to see if the puzzle has been solved
/// </summary>
/// <returns>TRUE if solved, FALSE otherwise</returns>
///
public bool
Solvable
{ get
{ return isSolvable();
}
} /* end of Soo::IsSolvable() */
///
/// <summary>
/// Tests to see if the puzzle has been solved
/// </summary>
/// <returns>TRUE if solved, FALSE otherwise</returns>
///
public bool
Solved
{ get
{ return isSolved();
}
} /* end of Soo::IsSolved() */
///
/// <summary>
/// Returns the version
/// </summary>
/// <returns>Version</returns>
///
public string
Version
{ get
{ return "v0.00.0017";
}
}
};
/*****************************************************************************
**
** End of Soo.cs
**
*****************************************************************************/