/*****************************************************************************
**
** Utility.cs
**
*****************************************************************************/
using System;
using System.Diagnostics;
using System.Text;
struct Hint
{ public enum HintType
{ SET_VALUE = 0,
ELIMINATE_CANDIDATE
};
public HintType type;
public int index;
public int iValue;
public string strWhy;
};
///
/// <summary>
/// Exception used to indicate that an Index is out of range
/// </summary>
///
public class IllegalValueException : ApplicationException
{ /// <summary>
/// Stores the square iHouse where the exception was raised.
/// </summary>
public int index;
/// <summary>
/// Stores the value that cause the exception to be raised.
/// </summary>
public int iValue;
///
/// <summary>
/// Constructor (CTOR)
/// </summary>
/// <param name="iSq">Square where illegal value was played</param>
/// <param name="iVal">Illegal value played at the square</param>
///
public IllegalValueException( int iSq, int iVal )
: base( String.Format( "Value '{0}' is illegal in square {1}.", iVal, Grid.SqName( iSq ) ) )
{ index = iSq;
iValue = iVal;
}
};
///
/// <summary>
/// Exception used to indicate that a square cannot be solved
/// </summary>
///
public class UnsolvableSquareException : ApplicationException
{ /// <summary>
/// Stores the square iHouse where the exception was raised.
/// </summary>
public int index;
///
/// <summary>
/// Constructor (CTOR)
/// </summary>
/// <param name="iSq">Square that cannot be solved</param>
///
public UnsolvableSquareException( int iSq )
: base( String.Format( "Square {0} is unsolvable.", Grid.SqName( iSq ) ) ) { index = iSq;
}
}
///
/// <summary>
/// Exception used to indicate that a Value is out of range
/// </summary>
///
public class ValueOutOfRangeException : ApplicationException
{ ///
/// <summary>
/// Constructor (CTOR)
/// </summary>
///
public ValueOutOfRangeException( )
: base( "The supplied value is out of range." )
{ /* EMPTY CTOR */ }
}
///
///
///
static class Utility
{ public static int[ ] iScratch = new int[ Grid.Size ];
public static bool
ArrayContains( int iTarget, int[ ] array, int iArrayLen )
{ Debug.Assert( array != null );
Debug.Assert( iArrayLen >= 0 );
for (int idx = 0; idx < iArrayLen; ++idx)
if (array[ idx ] == iTarget)
return true;
return false;
} /* end of ArrayContains() */
} /* end of class Utility */
///
/// <summary>
/// Alternative to BitArray designed for a smaller number of bits
/// </summary>
///
class BitSet
{ ///
/// <summary>
/// The maximum number of bits that can be stored in this BitSet
/// </summary>
///
protected const int MAX_BITS = (8 * sizeof( uint )) - 1;
/// <summary>
/// Order of kTableBits[] array (2^kTableSize)
/// </summary>
protected const int kTableSize = 4;
/// <summary>
/// Lookup table of bit counts
/// </summary>
protected static readonly int[ ] kTableBits;
/// <summary>
/// Current bits
/// </summary>
protected uint _bits = 0;
/// <summary>
/// Cached bit count
/// </summary>
protected int _count = 0;
/* -----------------------------------------------------------------------
STATIC METHODS
----------------------------------------------------------------------- */
static
BitSet( )
{ uint uCount,
uSize = 1U << kTableSize;
kTableBits = new int[ uSize ];
for (uint udx = 0; udx < uSize; ++udx)
{ uCount = udx - ((udx >> 1) & 0xDB6DB6DB) - ((udx >> 2) & 0x49249249);
kTableBits[ udx ] = (int) (((uCount + (uCount >> 3)) & 0xC71C71C7) % 63);
}
}
///
/// <summary>
/// Counts the number of non-zero bits in an unsigned integer
/// </summary>
/// <returns>Count of non-zero bits</returns>
/// <param name="uBits">Unsigned integer to count bits in</param>
///
public static int
CountBits( uint uBits )
{ int iCount = 0;
/*
if (uBits != 0)
{ uint uCount = uBits - ((uBits >> 1) & 0xDB6DB6DB) - ((uBits >> 2) & 0x49249249);
iCount = (int)(((uCount + (uCount >> 3)) & 0xC71C71C7) % 63);
}
*/
/*
* if (uBits != 0)
{ uBits -= ((uBits >> 1) & 0x55555555);
uBits = (((uBits >> 2) & 0x33333333) + (uBits & 0x33333333));
uBits = (((uBits >> 4) + uBits) & 0x0f0f0f0f);
iCount = (int)((uBits * 0x01010101) >> 24);
}
*/
while (uBits > 0)
{ iCount += kTableBits[ uBits & ((1U << kTableSize) - 1U) ];
uBits >>= kTableSize;
}
return iCount;
} /* end of BitSet::CountBits() */
///
/// <summary>
/// Returns the iHouse of the first non-zero bit
/// </summary>
/// <returns>Index of first non-zero bit, or -1 if not found</returns>
/// <param name="uBits">Rack of bits to find first non-zero bit in</param>
///
public static int
FindFirst( uint uBits )
{ return FindNext( uBits, 0 );
} /* end of BitSet::FindFirst() */
///
/// <summary>
/// Returns the iHouse of the next non-zero bit
/// </summary>
/// <returns>Index of first non-zero bit, or -1 if not found</returns>
/// <param name="uBits">Rack of bits to find first non-zero bit in</param>
/// <param name="iStart">Starting bit for search</param>
///
public static int
FindNext( uint uBits, int iStart )
{ int iBit = iStart;
if (iStart < 0 || iStart >= MAX_BITS)
throw new ArgumentOutOfRangeException( );
for (uint uMask = (1U << iStart); uMask <= uBits; uMask <<= 1, ++iBit)
if ((uBits & uMask) != 0)
return iBit;
return -1;
} /* end of BitSet::FindNext() */
/* -----------------------------------------------------------------------
METHODS
----------------------------------------------------------------------- */
///
/// <summary>
/// Default CTOR for the BitSet class
/// </summary>
///
public
BitSet( )
{ ClearAll( );
} /* end of BitSet() */
///
/// <summary>
/// Alternate CTOR for the BitSet class
/// </summary>
/// <param name="uBits">Starting bit flags</param>
///
public
BitSet( uint uBits )
{ _bits = uBits;
_count = -1;
} /* end of BitSet() */
///
/// <summary>
/// Clears a specific bit
/// </summary>
/// <returns>TRUE if bit cleared, FALSE if no change</returns>
/// <param name="iBit">Zero-based index of bit to test</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if the <paramref name="iBit"/> is out of range.
/// </exception>
///
public bool
Clear( int iBit )
{ if (iBit < 0 || iBit >= MAX_BITS)
throw new ArgumentOutOfRangeException( );
uint uMask = 1U << iBit;
if ((_bits & uMask) == 0)
return false;
_bits &= ~uMask;
_count--;
return true;
} /* end of BitSet::Clear() */
///
/// <summary>
/// Sets all the bits to zero
/// </summary>
///
public void
ClearAll( )
{ _bits = 0;
_count = 0;
} /* end of BitSet::ClearAll() */
///
/// <summary>
/// Includes (ORs) bits from another BitSet
/// </summary>
/// <returns>TRUE if bits set, FALSE if no change</returns>
/// <param name="uBits">Bits to include</param>
///
public bool
Include( uint uBits )
{ if ((_bits | uBits) == _bits)
return false;
_bits |= uBits;
_count = -1;
return true;
} /* end of BitSet::Include() */
///
/// <summary>
/// Removes (AND NOTs) bits from another BitSet
/// </summary>
/// <returns>TRUE if bits removed, FALSE if no change</returns>
/// <param name="uBits">Bits to remove</param>
///
public bool
Remove( uint uBits )
{ if ((_bits & uBits) == 0)
return false;
_bits &= ~uBits;
_count = -1;
return true;
} /* end of BitSet::Remove() */
///
/// <summary>
/// Sets a specific bit
/// </summary>
/// <returns>TRUE if bit set, FALSE if already set</returns>
/// <param name="iBit">Zero-based index of bit to test</param>
/// <exception cref="System.ArgumentOutOfRangeException">
/// Raised if the bit index is out of range.
/// </exception>
///
public bool
Set( int iBit )
{ if (iBit < 0 || iBit >= MAX_BITS)
throw new ArgumentOutOfRangeException( );
uint uMask = 1U << iBit;
if ((_bits & uMask) != 0)
return false;
_bits |= uMask;
_count++;
return true;
} /* end of BitSet::Set() */
///
/// <summary>
/// Sets a range of bits in the set
/// </summary>
/// <returns>TRUE if one or more bits set, FALSE if no change</returns>
/// <param name="iFrom">Starting zero-based bit index</param>
/// <param name="iTo">Ending zero-based bit index</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if the <paramref name="iFrom"/> or <paramref name="iTo"/>
/// parameter is outide the range [0..Bitset::Capacity].
/// </exception>
///
public bool
SetRange( int iFrom, int iTo )
{ uint uNewBits;
if (iFrom < 0 || iFrom >= MAX_BITS)
throw new ArgumentOutOfRangeException( "iFrom" );
if (iTo < iFrom || iTo >= MAX_BITS)
throw new ArgumentOutOfRangeException( "iTo" );
_count = (iTo - iFrom) + 1;
uNewBits = ((1U << _count) - 1) << iFrom;
if (_bits == uNewBits)
return false;
_bits = uNewBits;
return true;
} /* end of BitSet::SetRange() */
///
/// <summary>
/// Determines how many bits are shared
/// </summary>
/// <returns>Count of bits in common, or zero if none</returns>
/// <param name="uRHS">Right-hand side bits</param>
///
public int
Shared( uint uRHS )
{ return CountBits( _bits & uRHS );
} /* end of BitSet::Shared() */
///
/// <summary>
/// Tests a specific bit
/// </summary>
/// <returns>TRUE if bit is 1, FALSE otherwise</returns>
/// <param name="iBit">Zero-based index of bit to test</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if the bit iHouse is out of range.
/// </exception>
///
public bool
Test( int iBit )
{ if (iBit < 0 || iBit >= MAX_BITS)
throw new ArgumentOutOfRangeException( );
return ((_bits & (1U << iBit)) != 0);
} /* end of BitSet::Test() */
///
/// <summary>
/// Converts a bitset into readable form
/// </summary>
/// <returns>String of values, separated by spaces</returns>
///
public override string
ToString( )
{ int idx = 0;
StringBuilder sbResult = new StringBuilder( Grid.Size * 2 );
for (uint uMask = 1; uMask <= _bits; uMask <<= 1, ++idx)
if ((_bits & uMask) != 0)
{ if (sbResult.Length > 0)
sbResult.Append( " " );
sbResult.Append( idx );
}
return sbResult.ToString( );
} /* end of ToString() */
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
///
/// <summary>
/// Evaluates whether ANY of the bits are set
/// </summary>
/// <returns>TRUE if one or more bits set, FALSE otherwise</returns>
///
public bool
Any
{ get
{ return (_bits != 0);
}
} /* end of BitSet::Any() */
///
/// <summary>
/// Raw bits
/// </summary>
/// <returns>Bits</returns>
///
public uint
Bits
{ get
{ return _bits;
}
set
{ _bits = value;
_count = -1;
}
} /* end of BitSet::Bits() */
///
/// <summary>
/// Maximum number of bits that can be stored
/// </summary>
/// <returns>Maximum bit number</returns>
///
public int
Capacity
{ get
{ return MAX_BITS - 1;
}
} /* end of BitSet::Capacity() */
///
/// <summary>
/// Count of non-zero bits currently in the set
/// </summary>
/// <returns>Count of non-zero bits</returns>
///
public int
Count
{ get
{ if (_count < 0)
_count = CountBits( _bits );
return _count;
}
} /* end of BitSet::Count() */
///
/// <summary>
/// Evaluates whether ANY of the bits are set
/// </summary>
/// <returns>TRUE if no bits set, FALSE otherwise</returns>
///
public bool
Empty
{ get
{ return (_bits == 0);
}
} /* end of BitSet::Empty() */
///
/// <summary>
/// Returns the first non-zero bit in the set
/// </summary>
/// <returns>Zero-base bit offset, or -1 if all zeroes</returns>
/// <seealso cref="FindFirst"/>
///
public int
FirstBit
{ get
{ return FindFirst( _bits );
}
}
} /* end of class BitSet */
class Subset
{ private uint _uSubset;
private BitSet _squares;
private BitSet _values;
/* -----------------------------------------------------------------------
METHODS
----------------------------------------------------------------------- */
public
Subset( )
{ _uSubset = 1;
_squares = new BitSet( );
_values = new BitSet( );
}
public bool
ContainsSquare( int iSq )
{ return _squares.Test( iSq );
}
public bool
ContainsValue( int iValue )
{ return _values.Test( iValue );
}
///
/// <summary>looks for sets of bits</summary>
/// <returns>Subset if found, zero otherwise</returns>
/// <param name="uBitset">Array of candidates</param>
/// <param name="iMaxLen">Maximum subset size to find</param>
///
public bool
Find( uint[ ] uBitset, int iMaxLen )
{ int idx,
iBits;
uint uAllBits = 0;
for (idx = 0; idx < Grid.Size; ++idx)
uAllBits |= uBitset[ idx ];
for (; _uSubset <= uAllBits; _uSubset++)
{ if ((_uSubset & uAllBits) != _uSubset)
continue;
iBits = BitSet.CountBits( _uSubset );
if (iBits < 2 || iBits > iMaxLen)
continue;
_squares.ClearAll( );
_values.ClearAll( );
for (idx = 0; idx < Grid.Size; ++idx)
if ((uBitset[ idx ] & _uSubset) != 0)
{ _squares.Set( idx );
_values.Include( uBitset[ idx ] & _uSubset );
}
if (_squares.Count == _values.Count)
{ _uSubset++;
return true;
}
}
return false;
} /* end of Subset::Find() */
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
public int
Length
{ get
{ return _values.Count;
}
}
public bool
Naked
{ get
{ return (_squares.Count == _values.Count);
}
}
public uint
Squares
{ get
{ return _squares.Bits;
}
}
public uint
Values
{ get
{ return _values.Bits;
}
}
public string
ValueList
{ get
{ return _values.ToString( );
}
}
} /* end of class Subset */
/*****************************************************************************
**
** End of Utility.cs
**
*****************************************************************************/