/*****************************************************************************
**
** House.cs
**
*****************************************************************************/
using System;
using System.Diagnostics;
using System.Text;
class House
{
/* -----------------------------------------------------------------------
VARIABLES
----------------------------------------------------------------------- */
private readonly Soo _soo;
private Grid.House _house;
private int _iHouse;
private int[] _iSq = new int[ Grid.Size ];
/* -----------------------------------------------------------------------
STATIC METHODS
----------------------------------------------------------------------- */
/* -----------------------------------------------------------------------
CONSTRUCTOR
----------------------------------------------------------------------- */
/// <summary>
/// CTOR for the House utility class
/// </summary>
/// <param name="soo">Soo object that this house belongs to</param>
public
House( Soo soo )
{
if (soo == null)
throw new ArgumentNullException( "soo" );
_soo = soo;
_house = Grid.House.None;
_iHouse = -1;
} /* end of House::House() */
///
/// <summary>
/// Alternate CTOR for the House utility class
/// </summary>
/// <param name="soo">Soo object that this house belongs to</param>
/// <param name="iHouse">House number [1..Grid.Size]</param>
/// <param name="house">Grid.House.*</param>
///
public
House( Soo soo, int iHouse, Grid.House house )
{
if (soo == null)
throw new ArgumentNullException( "soo" );
_soo = soo;
Set( iHouse, house );
} /* end of House::House() */
/* -----------------------------------------------------------------------
PUBLIC METHODS
----------------------------------------------------------------------- */
///
/// <summary>
/// Finds box/line reductions ("Locked Candidates" / "Pointing Pairs")
/// </summary>
/// <returns>TRUE if one or more found, FALSE otherwise</returns>
///
public bool
FindBoxLineReductions()
{
int iCount;
bool bFound = false;
for (int iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
if ((iCount = buildCandidateList( iValue, Grid.Size )) > 1)
{
bFound = (_house == Grid.House.Box) ?
findPointingPairs( iValue, iCount ) :
findLockedCandidates( iValue, iCount );
if (bFound)
return true;
}
return false;
} /* end of House::FindBoxLineReductions() */
///
/// <summary>
/// Finds the first HIDDEN SINGLE
/// </summary>
/// <returns>TRUE if one or more found, FALSE otherwise</returns>
/// <remarks>
/// HIDDEN SINGLE is when a house has only one possible square for a
/// candidate.
/// </remarks>
///
public bool
FindHiddenSingles()
{
bool bFound = false;
for (int iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
{
if (buildCandidateList( iValue, 2 ) == 1)
{
Debug.Assert( Grid.IsValidIndex( Utility.iScratch[ 0 ] ) );
_soo.Details = String.Format( "HIDDEN SINGLE IN {0}", this.Name );
_soo.SetSquare( Utility.iScratch[ 0 ], iValue );
bFound = true;
}
}
return bFound;
} /* end of House::FindHiddenSingles() */
///
/// <summary>Finds hidden and naked subsets</summary>
/// <returns>TRUE if found, FALSE otherwise</returns>
/// <param name="iMaxLen">Maximum length of subset to find</param>
/// <remarks>
/// </remarks>
///
public bool
FindSubsets( int iMaxLen )
{
Square sq;
int idx,
iValue;
uint uInSet;
bool bFound = false;
Subset subset = new Subset();
uint[] uBitset = new uint[ Grid.Size ];
for (idx = 0; idx < Grid.Size; ++idx)
uBitset[ idx ] = _soo[ _iSq[ idx ] ].Candidates.Bits;
while (subset.Find( uBitset, iMaxLen ))
{
/*
Console.WriteLine("{0} => found subset {1} in squares {2}",
this.Name, subset.ValueList, subsetSquares(subset.Squares));
*/
for (idx = 0; idx < Grid.Size; ++idx)
{
sq = _soo[ _iSq[ idx ] ];
if (!sq.IsEmpty)
continue; // skip set squares
uInSet = sq.Candidates.Bits & subset.Values;
//
// If square is IN the subset and has extra candidates, then
// get rid of the extras
//
if (uInSet != sq.Candidates.Bits && subset.ContainsSquare( idx ))
{
for (iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
if (sq.Candidates.Test( iValue ) &&
!subset.ContainsValue( iValue ))
{
bFound = true;
_soo.Details = subsetDescription( subset );
_soo.EliminateCandidate( sq.Index, iValue );
}
}
//
// If the square is OUTSIDE the subset, but has any of the
// candidates, then get rid of them.
//
else if (uInSet != 0 && !subset.ContainsSquare( idx ))
{
for (iValue = Grid.ValueMin; iValue <= Grid.ValueMax; ++iValue)
if (sq.Candidates.Test( iValue ) &&
subset.ContainsValue( iValue ))
{
bFound = true;
_soo.Details = subsetDescription( subset );
_soo.EliminateCandidate( sq.Index, iValue );
}
}
}
if (bFound)
return true;
}
return false;
} /* end of House::FindSubsets() */
///
/// <summary>
/// Eliminate candidates based on a square list
/// </summary>
/// <param name="iValue">Value to eliminate</param>
/// <param name="uSquares">Bit mask of squares indices</param>
/// <returns>TRUE if one or more candidates eliminated</returns>
///
public bool
EliminateCandidateSquares( int iValue, uint uSquares )
{
Square sq;
int idx = 0;
bool bFound = false;
Debug.Assert( uSquares != 0 );
for (uint uMask = 1; uMask <= uSquares; uMask <<= 1, ++idx)
{
if ((uSquares & uMask) != 0)
{
sq = _soo[ _iSq[ idx ] ];
if (sq.IsEmpty &&
_soo.EliminateCandidate( sq.Index, iValue ))
{
bFound = true;
}
}
}
return bFound;
} /* end of House::EliminateCandidateSquares() */
///
/// <summary>
/// Gets a bitset that reflects which squares allow a given candidate
/// </summary>
/// <returns>Count of candidates found, or zero if value is already set in the house</returns>
/// <param name="iValue">Value to build bitset for</param>
/// <param name="uSquares">BitSet of squares that include the candidate</param>
///
public int
GetCandidateSquares( int iValue, out uint uSquares )
{
Square sq;
int iCount = 0;
if (!Grid.IsValidValue( iValue ))
throw new ValueOutOfRangeException();
uSquares = 0;
for (int idx = 0; idx < Grid.Size; ++idx)
{
sq = _soo[ _iSq[ idx ] ];
if (sq.Value == iValue)
return 0;
if (sq.Candidates.Test( iValue ))
{
iCount++;
uSquares |= (1U << idx);
}
}
return iCount;
} /* end of House::GetCandidateSquares() */
///
/// <summary>
/// Determines if a house is solvable
/// </summary>
/// <returns>TRUE if solvable, FALSE if not</returns>
/// <param name="strWhyNot">String to receive explanation</param>
///
public bool
IsSolvable( string strWhyNot )
{
Square sq;
int iValue;
BitSet candidates;
if (IsSolved())
return true;
candidates = new BitSet();
candidates.SetRange( Grid.ValueMin, Grid.ValueMax );
for (int idx = 0; idx < Grid.Size; ++idx)
{
sq = _soo[ _iSq[ idx ] ];
if (sq.IsEmpty)
{
if (sq.Candidates.Any)
candidates.Remove( sq.Candidates.Bits );
else
{
strWhyNot = String.Format( "Square {0} has no candidates.",
Grid.SqName( sq.Index ) );
return false;
}
}
else
candidates.Clear( sq.Value );
if (candidates.Empty)
return true;
}
iValue = candidates.FirstBit;
Debug.Assert( Grid.IsValidValue( iValue ) );
strWhyNot = String.Format( "There is no place for a '{0}' in {1}.",
iValue, this.Name );
return false;
} /* end of House::IsSolvable() */
///
/// <summary>
/// Determines if a house has been solved
/// </summary>
/// <returns>TRUE if solved, FALSE otherwise</returns>
///
public bool
IsSolved()
{
for (int idx = 0; idx < Grid.Size; ++idx)
if (_soo[ _iSq[ idx ] ].IsEmpty)
return false;
return true;
} /* end of House::IsSolved() */
/// <summary>
/// Sets the house to the appropriate number / house
/// </summary>
/// <param name="iHouse">House number [1..Grid.Size]</param>
/// <param name="house">Grid.House.*</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if <paramref name="iHouse"/> or <paramref name="idx"/> are out
/// of the range [0..Grid.Size - 1] inclusive.
/// </exception>
///
public void
Set( int iHouse, Grid.House house )
{
if (!Grid.IsValidHouse( iHouse ))
throw new ArgumentOutOfRangeException( "iHouse" );
if (!(house == Grid.House.Box || house == Grid.House.Column || house == Grid.House.Row))
throw new ArgumentOutOfRangeException( "house" );
_house = house;
_iHouse = iHouse;
for (int idx = 0; idx < Grid.Size; ++idx)
_iSq[ idx ] = Grid.NthSq( iHouse, house, idx );
} /* end of House::Set() */
public string
SqList( uint uSquares )
{
int idx = 0;
StringBuilder sbResult = new StringBuilder( Grid.Size * 5 );
for (uint uMask = 1; uMask <= uSquares; uMask <<= 1, ++idx)
if ((uSquares & uMask) != 0)
{
if (sbResult.Length > 0)
sbResult.Append( " " );
sbResult.Append( Grid.SqName( _iSq[ idx ] ) );
}
return sbResult.ToString();
} /* end of House::SqList() */
/* -----------------------------------------------------------------------
PRIVATE METHODS
----------------------------------------------------------------------- */
#region "PRIVATE METHODS"
///
/// <summary>
/// Builds a list of squares that contain the given candidate
/// </summary>
/// <returns>Count of squares, or zero if value already set</returns>
/// <param name="iValue">Value to find candidate squares for</param>
/// <param name="iMaxCount">Maximum count of squares to find</param>
///
private int
buildCandidateList( int iValue, int iMaxCount )
{
Square sq;
int idx,
iCount = 0;
Debug.Assert( Grid.IsValidValue( iValue ) );
Debug.Assert( iMaxCount > 0 && iMaxCount <= Grid.Size );
for (idx = 0; idx < Grid.Size; ++idx)
{
sq = _soo[ _iSq[ idx ] ];
if (sq.Value == iValue)
return 0;
if (sq.IsEmpty &&
sq.Candidates.Test( iValue ))
{
Utility.iScratch[ iCount ] = sq.Index;
if (++iCount >= iMaxCount)
return iCount;
}
}
return iCount;
} /* end of House::buildCandidateList() */
///
/// <summary>Finds "locked candidates"</summary>
/// <returns>True if one or more found, FALSE otherwise</returns>
/// <remarks>
/// A "Locked Candidate" is when all of the candidates for a given row or
/// column lie in the same box, and can be eliminated from other rows/columns
/// inside that box.
/// </remarks>
///
private bool
findLockedCandidates( int iValue, int iCount )
{
int idx,
index,
iBox;
bool bFound = false;
Debug.Assert( _house == Grid.House.Column || _house == Grid.House.Row );
iBox = Grid.GetBox( Utility.iScratch[ 0 ] );
for (idx = 1; idx < iCount; ++idx)
if (Grid.GetBox( Utility.iScratch[ idx ] ) != iBox)
return false;
index = Utility.iScratch[ 0 ];
if (_house == Grid.House.Row)
{
while ((index = Grid.NextSq( index, Grid.House.Box )) != Utility.iScratch[ 0 ])
if (Grid.GetRow( index ) != _iHouse &&
_soo[ index ].Candidates.Test( iValue ))
{
bFound = true;
_soo.Details = String.Format( "LOCKED CANDIDATES IN {0}",
Grid.SqList( Utility.iScratch, iCount ) );
_soo.EliminateCandidate( index, iValue );
}
}
else // house == Grid.House.Column
{
while ((index = Grid.NextSq( index, Grid.House.Box )) != Utility.iScratch[ 0 ])
if (Grid.GetColumn( index ) != _iHouse &&
_soo[ index ].Candidates.Test( iValue ))
{
bFound = true;
_soo.Details = String.Format( "LOCKED CANDIDATES IN {0}",
Grid.SqList( Utility.iScratch, iCount ) );
_soo.EliminateCandidate( index, iValue );
}
}
return bFound;
} /* end of House::findLockedCandidates() */
///
/// <summary>Find all pointing pairs</summary>
/// <returns>TRUE if a pointing pair detected</returns>
/// <param name="iValue">Value to check for</param>
/// <param name="iCount">Count of squares in Utility.iScratch</param>
/// <remarks>
/// If all of candidates for a given value are in the same row or column
/// within a box, then they can be eliminated from that row or column outside
/// of the box.
/// </remarks>
///
private bool
findPointingPairs( int iValue, int iCount )
{
int idx,
index;
Grid.House house;
bool bFound = false,
bSameCol = true,
bSameRow = true;
Debug.Assert( _house == Grid.House.Box );
Debug.Assert( Grid.IsValidIndex( Utility.iScratch[ 0 ] ) );
//
// Look for pairs/triples in the same row or column
//
index = Utility.iScratch[ 0 ];
for (idx = 1; idx < iCount; ++idx)
{
if (Grid.GetColumn( Utility.iScratch[ idx ] ) != Grid.GetColumn( index ))
bSameCol = false;
if (Grid.GetRow( Utility.iScratch[ idx ] ) != Grid.GetRow( index ))
bSameRow = false;
if (!(bSameCol || bSameRow))
return false;
}
Debug.Assert( bSameCol || bSameRow ); // at least one is true...
Debug.Assert( !(bSameCol && bSameRow) ); // ...but not both
house = bSameCol ? Grid.House.Column : Grid.House.Row;
while ((index = Grid.NextSq( index, house )) != Utility.iScratch[ 0 ])
if (Grid.GetBox( index ) != _iHouse &&
_soo[ index ].Candidates.Test( iValue ))
{
bFound = true;
_soo.Details = String.Format( "POINTING PAIR IN {0}",
Grid.SqList( Utility.iScratch, iCount ) );
_soo.EliminateCandidate( index, iValue );
}
return bFound;
} /* end of findPointingPairs() */
///
/// <summary>
/// Converts a subset into readable form
/// </summary>
/// <returns>Human-readable string</returns>
/// <param name="set">Subset to build name for</param>
/// <exception cref="ArgumentNullException">
/// Raised if the <paramref name="set"/> parameter is null.
/// </exception>
///
private string
subsetDescription( Subset set )
{
string strType;
StringBuilder sbResult = new StringBuilder( Grid.Size * 5 );
if (set == null)
throw new ArgumentNullException( "set" );
switch (set.Length)
{
case 1:
strType = "SINGLE";
break;
case 2:
strType = "PAIR";
break;
case 3:
strType = "TRIPLET";
break;
default:
strType = "SUBSET";
break;
}
return String.Format( "{0} {1} IN {2}",
strType, set.ValueList, SqList( set.Squares ) );
} /* end of subsetDescription() */
#endregion
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
///
/// <summary>
/// Returns the name of the house in human-readable form
/// </summary>
/// <returns>Name, i.e., "b1" or "c4"</returns>
/// <exception cref="InvalidOperationException()">
/// Raised if the house type (_house) is not valid.
/// </exception>
///
public string
Name
{
get
{
string strHouse = "XbcrX";
return String.Format( "{0}{1}",
strHouse.Substring( (int)(_house), 1 ), (_iHouse + 1) );
}
} /* end of House::Name() */
};
/*****************************************************************************
**
** End of House.cs
**
*****************************************************************************/