/*****************************************************************************
**
** grid.cs
**
*****************************************************************************/
using System;
using System.Collections.Generic;
using System.Text;
class Grid : ICloneable
{ /* -----------------------------------------------------------------------
CONSTANTS
----------------------------------------------------------------------- */
/// <summary>
/// Types of a House (Box / Column / Row)
/// </summary>
public enum House
{ None = 0,
Box,
Column,
Row
};
/// <summary>
/// An index (square offset) that is guaranteed to be off the board
/// </summary>
public const int BadIndex = -1;
/// <summary>
/// The dimensions (rows / columns) of a sub-box (3 for classic Sudoku)
/// </summary>
public const int BoxSize = 3;
/// <summary>
/// The number of columns in the puzzle (9 for classic Sudoku)
/// </summary>
/// <seealso cref="Rows"/>
public const int Columns = Size;
/// <summary>
/// Number of peers, i.e., squares sharing the same box/column/row
/// </summary>
public const int Peers = (Size * 3) - (2 * BoxSize) - 1;
/// <summary>
/// The number of rows in the puzzle (9 for classic Sudoku)
/// </summary>
/// <seealso cref="Columns"/>
public const int Rows = Size;
/// <summary>
/// The size of the puzzle (9 for classic Sudoku)
/// </summary>
public const int Size = BoxSize * BoxSize;
/// <summary>
/// The total number of squares in the puzzle (81 for classic Sudoku)
/// </summary>
public const int Squares = Columns * Rows;
/// <summary>
/// The empty (blank) value
/// </summary>
public const int ValueNone = 0;
/// <summary>
/// The minimum value allowed (1 for classic Sudoku)
/// </summary>
public const int ValueMin = 1;
/// <summary>
/// The maximum value allowed (9 for classic Sudoku)
/// </summary>
public const int ValueMax = Size;
/// <summary>
/// The minimum number of preset values required to solve a puzzle.
/// </summary>
public const int StartingValues = 17;
/* -----------------------------------------------------------------------
STATIC METHODS
----------------------------------------------------------------------- */
///
/// <summary>
/// Computes the column name
/// </summary>
/// <returns>Human-readable name</returns>
/// <param name="index">Square iHouse</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the iHouse is out of range
/// </exception>
///
public static string
ColName( int index )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException();
return String.Format( "c{0}", GetColumn( index ) + 1 ); } /* end of Grid::ColName() */
///
/// <summary>
/// Returns the box number (house) for a given square
/// </summary>
/// <returns>House number</returns>
/// <param name="index">Square to find house number for</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the iHouse is out of range.
/// </exception>
///
public static int
GetBox( int index )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException();
return ((GetRow( index ) / BoxSize) * BoxSize) +
(GetColumn( index ) / BoxSize);
} /* end of Grid::GetBox() */
///
/// <summary>
/// Returns the column number (house) for a given square
/// </summary>
/// <returns>House number</returns>
/// <param name="index">Square to find house number for</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the iHouse is out of range.
/// </exception>
///
public static int
GetColumn( int index )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException();
return (index % Columns);
}
///
/// <summary>
/// Returns the row number (house) for a given square
/// </summary>
/// <returns>House number</returns>
/// <param name="index">Square to find house number for</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the iHouse is out of range.
/// </exception>
///
public static int
GetRow( int index )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException();
return (index / Rows);
} /* end of Grid::GetRow() */
///
/// <summary>
/// Determines if two squares intersect with each other
/// </summary>
/// <returns>TRUE if they intersect, FALSE otherwise</returns>
/// <param name="iLHS">First square index</param>
/// <param name="iRHS">Second square index</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if <paramref name="iLHS"/> or <paramref name="iRHS"/> are
/// not valid.
/// </exception>
/// <remarks>
/// A square does NOT intersect itself!
/// </remarks>
///
public static bool
Intersects( int iLHS, int iRHS )
{ if (!IsValidIndex( iLHS ))
throw new IndexOutOfRangeException( "iLHS" );
if (!IsValidIndex( iRHS ))
throw new IndexOutOfRangeException( "iRHS" );
return (iLHS != iRHS) &&
((iLHS / Rows) == (iRHS / Rows) ||
(iLHS % Columns) == (iRHS % Columns) ||
GetBox( iLHS ) == GetBox( iRHS ));
} /* End of Grid::Intersects() */
///
/// <summary>
/// Tests a house number for validity
/// </summary>
/// <returns>TRUE if valid house number, FALSE otherwise</returns>
/// <param name="iHouse">House number [0...Grid.Size - 1]</param>
///
public static bool
IsValidHouse( int iHouse )
{ return (iHouse >= 0 && iHouse < Grid.Size);
} /* end of Grid::IsValidHouse() */
///
/// <summary>
/// Tests a square iHouse for validity
/// </summary>
/// <returns>TRUE if a valid iHouse, FALSE otherwise</returns>
/// <param name="index">Index to test</param>
///
public static bool
IsValidIndex( int index )
{ return (index >= 0 && index < Squares);
} /* end of Grid::IsValidIndex() */
///
/// <summary>
/// Tests a value for validity
/// </summary>
/// <returns>TRUE if a valid value, FALSE otherwise</returns>
/// <param name="iValue">Value to test</param>
/// <remarks>
/// Note that the empty value (ValueNone) is NOT considered valid.
/// </remarks>
///
public static bool
IsValidValue( int iValue )
{ return (iValue >= ValueMin && iValue <= ValueMax);
} /* end of Grid::IsValidValue() */
///
/// <summary>
/// Converts a Grid.House.* constant into a human-readable string
/// </summary>
/// <returns>Human-readable name, i.e. "Box", "Column" or "Row"</returns>
/// <param name="house">Grid.House.* constant</param>
/// <exception cref="ArgumentException">
/// Raised if the house is not Box / Column / Row
/// </exception>
///
public static string
HouseName( Grid.House house )
{ string strHouse = "";
switch (house)
{ case Grid.House.Box:
strHouse = "Box";
break;
case Grid.House.Column:
strHouse = "Column";
break;
case Grid.House.Row:
strHouse = "Row";
break;
default:
throw new ArgumentException( "house" );
}
return strHouse;
} /* end of Grid::HouseName() */
///
/// <summary>Computes the row name</summary>
/// <returns>Human-readable name</returns>
/// <param name="index">Square iHouse</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the iHouse is out of range
/// </exception>
///
public static string
RowName( int index )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException();
return String.Format( "r{0}", GetRow( index ) + 1 ); } /* end of RowName() */
///
/// <summary>
/// Builds a human-readable list of squares
/// </summary>
/// <param name="iSq">Array of 0..Grid.Size squares</param>
/// <param name="iCount">Count of squares in <paramref name="iSq"/> parameter</param>
/// <returns>Human-readable string</returns>
///
public static string
SqList( int[] iSq, int iCount )
{ StringBuilder sb;
if (iSq == null)
throw new ArgumentNullException( "iSq" );
if (iCount < 0)
throw new ArgumentException( "iCount" );
sb = new StringBuilder( iCount * 5 );
for (int idx = 0; idx < iCount; ++idx)
{ if (sb.Length > 0)
sb.Append( " " );
sb.Append( SqName( iSq[ idx ] ) );
}
return sb.ToString();
} /* end of Grid::SqList() */
///
/// <summary>Computes the square name</summary>
/// <returns>Human-readable name</returns>
/// <param name="index">Square iHouse</param>
///
public static string
SqName( int index )
{ return RowName( index ) + ColName( index );
}
///
/// <summary>
/// Returns the next square in a given box, column, or row
/// </summary>
/// <returns>Square iHouse</returns>
/// <param name="index">Square iHouse</param>
/// <param name="idx">Peer</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if <paramref name="iHouse"/> is out of range.
/// </exception>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if the paramref name="idx"/> parameter is outside the range 0..Peers - 1
/// </exception>
///
public static int
NthPeer( int index, int idx )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException( "index" );
return (idx >= 0 && idx < Peers) ? _iPeers[ index, idx ] : -1;
} /* end of Grid::NthPeer() */
///
/// <summary>
/// Returns the next square in a given box, column, or row
/// </summary>
/// <returns>Square iHouse</returns>
/// <param name="index">Square iHouse</param>
/// <param name="house">Grid.House.*</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if <paramref name="iHouse"/> is out of range.
/// </exception>
/// <exception cref="ArgumentException">
/// Raised if the paramref name="house"/> parameter is not one of
/// Grid.House.Box, Grid.House.Column, or Grid.House.Row
/// </exception>
///
public static int
NextSq( int index, Grid.House house )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException( "index" );
switch (house)
{ case Grid.House.Box:
index++;
if ((index % BoxSize) == 0)
{ index += Columns - BoxSize;
if (((index / Size) % BoxSize) == 0)
index -= Rows * BoxSize;
}
break;
case Grid.House.Column:
index += Columns;
if (index >= Squares)
index -= Squares;
break;
case Grid.House.Row:
index++;
if ((index % Columns) == 0)
index -= Columns;
break;
default:
throw new ArgumentException( "house" );
}
return index;
} /* end of Grid::NextSq() */
///
/// <summary>
/// Returns the Nth square in a given box, column, or row
/// </summary>
/// <returns>Square iHouse</returns>
/// <param name="iHouse">House number (0..Size - 1)</param>
/// <param name="house">House.*</param>
/// <param name="idx">Offset within type (0..Size - 1)</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if <paramref name="iHouse"/> or <paramref name="idx"/> are out
/// of the range [0..Size - 1] inclusive.
/// </exception>
///
public static int
NthSq( int iHouse, Grid.House house, int idx )
{ int index = -1;
if (!IsValidHouse( iHouse ))
throw new ArgumentOutOfRangeException( "iHouse" );
if (idx < 0 || idx >= Size)
throw new ArgumentOutOfRangeException( "idx" );
switch (house)
{ case Grid.House.Box:
index = ((iHouse / BoxSize) * (BoxSize * Rows)) +
((idx / BoxSize) * Columns) +
((iHouse % BoxSize) * BoxSize) + (idx % BoxSize);
break;
case Grid.House.Column:
index = iHouse + (idx * Rows);
break;
case Grid.House.Row:
index = (iHouse * Rows) + idx;
break;
default:
throw new ArgumentException( "house" );
}
return index;
} /* end of Grid::NthSq() */
/* -----------------------------------------------------------------------
VARIABLES
----------------------------------------------------------------------- */
protected static readonly int[ , ] _iPeers = null;
protected int[] _iCounts = new int[ Size + 1 ];
protected Square[] _sq = new Square[ Squares ];
/* -----------------------------------------------------------------------
CONSTRUCTOR
----------------------------------------------------------------------- */
static
Grid()
{ int idx,
index;
List<int> peers = new List<int>();
_iPeers = new int[ Grid.Squares, Peers ];
for (index = 0; index < Grid.Squares; ++index)
for (idx = 0; idx < Peers; ++idx)
_iPeers[ index, idx ] = Grid.BadIndex;
for (index = 0; index < Grid.Squares; ++index)
{ peers.Clear();
for (idx = 0; idx < Grid.Squares; ++idx)
if (index != idx &&
(GetRow( index ) == GetRow( idx ) ||
GetColumn( index ) == GetColumn( idx ) ||
GetBox( index ) == GetBox( idx )))
{ if (!peers.Contains(idx))
peers.Add(idx);
}
idx = 0;
peers.Sort();
foreach (int iPeer in peers)
_iPeers[ index, idx++ ] = iPeer;
}
}
public
Grid()
{ for (int index = 0; index < Squares; ++index)
_sq[ index ] = new Square( index );
Reset();
}
/* -----------------------------------------------------------------------
METHODS
----------------------------------------------------------------------- */
/// <summary>
/// Implements the Clone() method so that this object can be copied
/// </summary>
/// <returns>Copy (clone) of this instance of the grid</returns>
public object
Clone()
{ Grid clone = new Grid();
for (int index = 0; index < Squares; ++index)
if (!_sq[index].IsEmpty)
clone.Set(index, _sq[index].Value);
return clone;
} /* end of Grid::Clone() */
/// <summary>
/// Evaluates how many times a given value has been played on the grid
/// </summary>
/// <returns>Count of times the value has been placed</returns>
/// <param name="iValue">Value to check</param>
///
public int
CountValues( int iValue )
{ if (!(iValue == 0 || IsValidValue( iValue )))
throw new ValueOutOfRangeException();
return _iCounts[ iValue ];
} /* end of Grid.CountValues() */
///
/// <summary>Displays the current board state</summary>
/// <seealso cref="DisplayMarks"/>
///
public string
Display()
{ int index,
iCol,
iRow;
StringBuilder sb = new StringBuilder();
for (index = iRow = 0; iRow < Rows; ++iRow)
{ for (iCol = 0; iCol < Columns; ++iCol, ++index)
{ if (_sq[index].IsEmpty)
sb.Append(". "); else
{ sb.AppendFormat( "{0} ", _sq[ index ].Value ); }
if (iCol < (Columns - 1) && ((iCol + 1) % BoxSize) == 0)
sb.Append( "| " );
}
sb.Append( "\n" );
if (iRow < (Rows - 1) && ((iRow + 1) % BoxSize) == 0)
sb.Append( "------+-------+------\n" );
}
return sb.ToString();
} /* end of Grid::Display() */
///
/// <summary>
/// Displays the current board, showing pencil marks
/// </summary>
/// <seealso cref="Display"/>
///
public string
DisplayMarks()
{ int index,
iCol,
iRow,
iMark;
StringBuilder sb = new StringBuilder();
sb.Length = 0;
for (iRow = 0; iRow < (BoxSize * Rows); ++iRow)
{ if ((iRow % Rows) == 0)
sb.Append( " +-----------------+-----------------+-----------------+\n" );
else if ((iRow % BoxSize) == 0)
sb.Append( " | . . . . . . . . | . . . . . . . . | . . . . . . . . |\n" );
for (iCol = 0; iCol < (BoxSize * Columns); ++iCol)
{ if ((iCol % Columns) == 0)
sb.Append( " | " );
else if ((iCol % BoxSize) == 0)
sb.Append( " : " );
index = ((iRow / BoxSize) * Rows) + (iCol / BoxSize);
iMark = (((iRow % BoxSize) * BoxSize) + (iCol % BoxSize)) + 1;
if (_sq[ index ].IsEmpty)
{ if (_sq[ index ].Candidates.Test( iMark ))
sb.Append( iMark );
else
sb.Append( " " );
}
else if (iMark == 4)
sb.AppendFormat( "[{0}]", _sq[ index ].Value ); else if (iMark < 4 || iMark > 6)
sb.Append( " " );
}
sb.Append( " |\n" );
}
sb.Append( " +-----------------+-----------------+-----------------+\n" );
return sb.ToString();
} /* end of Grid::DisplayMarks() */
///
/// <summary>
/// Displays the current board in a one line "short form"
/// </summary>
/// <returns>String containing current board in abbreviated format</returns>
/// <param name="cEmpty">Character to use for empty squares</param>
/// <seealso cref="Display"/>
///
public string
DisplayShortForm( char cEmpty )
{ StringBuilder sb = new StringBuilder( Squares + 1 );
sb.Length = 0;
for (int index = 0; index < Squares; ++index)
if (_sq[ index ].IsEmpty)
sb.Append( cEmpty );
else
sb.Append( _sq[ index ].Value );
return sb.ToString();
} /* end of Grid::DisplayShortForm() */
///
/// <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>
/// <param name="strDetails">Output string that describes why the parse may have failed</param>
///
public bool
Parse(string strRaw, out string strDetails)
{ int index,
iValue;
try
{ Reset();
if (String.IsNullOrEmpty( strRaw ) || strRaw.Length < Squares)
{ strDetails = "Insufficient input.";
return false;
}
index = 0;
foreach (char ch in strRaw)
{ if (ch == '-' || ch == '+' || ch == '|')
continue;
if (ch == '#' || ch == ';')
break;
if (ch > ' ')
{ if (Int32.TryParse( ch.ToString(), out iValue ) &&
IsValidValue( iValue ))
{ Set( index, iValue );
}
index++;
}
}
}
catch (IllegalValueException ex)
{ strDetails = String.Format( "The value '{0}' at square {1} is illegal.", ex.iValue, SqName( ex.index ) );
return false;
}
catch (UnsolvableSquareException ex)
{ strDetails = String.Format( "Square {0} has no legal value.", SqName( ex.index ) );
return false;
}
strDetails = "";
return true;
} /* end of Grid::Parse() */
///
/// <summary>
/// Resets the grid to it's initial (blank) state
/// </summary>
///
public void
Reset()
{ _iCounts[ ValueNone ] = Squares;
for (int idx = ValueMin; idx <= ValueMax; ++idx)
_iCounts[ idx ] = 0;
for (int index = 0; index < Squares; ++index)
_sq[ index ].Reset();
} /* end of Grid::Reset() */
///
/// <summary>
/// Assigns a value to a square
/// </summary>
/// <returns>TRUE if set, FALSE otherwise</returns>
/// <param name="index">Index of square</param>
/// <param name="iValue">Value to be assigned</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the <paramref name="index"/> parameter is out of range.
/// </exception>
/// <exception cref="ArgumentOutOfRangeException">
/// Raised if the <paramref name="iValue"/> parameter is out of range.
/// </exception>
///
public bool
Set( int index, int iValue )
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException( "index" );
if (!IsValidValue( iValue ))
throw new ArgumentOutOfRangeException( "iValue" );
if (_sq[ index ].Value == iValue)
return false;
_iCounts[ ValueNone ]--;
_sq[ index ].Value = iValue;
_iCounts[ iValue ]++;
//
// Clear this value from linked squares
//
if (_iCounts[ iValue ] < Grid.Size)
{ for (int idx = 0; idx < Peers; ++idx)
_sq[ _iPeers[ index, idx ] ].ClearCandidate( iValue );
}
return true;
} /* end of Grid::Set() */
///
/// <summary>
/// Sets a square to an empty (blank) value
/// </summary>
/// <returns>TRUE if set, FALSE otherwise</returns>
/// <param name="index">Index of square</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the <paramref name="index"/> parameter is out of range.
/// </exception>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the <paramref name="index"/> parameter is out of range.
/// </exception>
///
public bool
SetEmpty( int index )
{ int iValue,
iValBefore;
if (!IsValidIndex( index ))
throw new IndexOutOfRangeException( "index" );
if ((iValBefore = _sq[ index ].Value) == ValueNone)
return false;
_iCounts[ iValBefore ]--;
_iCounts[ ValueNone ]++;
_sq[ index ].Reset();
for (int iPeer = 0; iPeer < Peers; ++iPeer)
{ if ((iValue = _sq[ _iPeers[ index, iPeer ] ].Value) != ValueNone)
_sq[ index ].ClearCandidate( iValue );
else
refreshCandidates( _iPeers[ index, iPeer ], iValBefore );
}
return true;
} /* end of Grid::SetEmpty() */
///
/// <summary>
/// Returns a bit map of candidates shared by two squares
/// </summary>
/// <returns>Bit set of candidates found in both squares</returns>
/// <param name="iLHS">Left hand square</param>
/// <param name="iRHS">Right hand square</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if either parameter are outside the range 0...Grid.Squares
/// </exception>
///
public uint
SharedCandidates( int iLHS, int iRHS )
{ if (!IsValidIndex( iLHS ))
throw new IndexOutOfRangeException( "iLHS" );
if (!IsValidIndex( iRHS ))
throw new IndexOutOfRangeException( "iRHS" );
return (_sq[ iLHS ].Candidates.Bits & _sq[ iRHS ].Candidates.Bits);
} /* end of Grid::SharedCandidates() */
///
/// <summary>Rebuilds a given candidate for a square</summary>
/// <param name="index">Square to rebuild the candidates for</param>
/// <param name="iValue">Value to update candidate for</param>
///
private void
refreshCandidates( int index, int iValue)
{ if ( _sq[index].IsEmpty )
{ if (_iCounts[ iValue ] > 0)
{ for (int iPeer = 0; iPeer < Peers; ++iPeer)
if (_sq[ _iPeers[ index, iPeer ] ].Value == iValue)
{ _sq[ index ].ClearCandidate( iValue );
return;
}
}
_sq[ index ].SetCandidate( iValue );
}
else
_sq[index].ClearAllCandidates();
} /* end of Grid::refreshCandidates() */
/* -----------------------------------------------------------------------
PROPERTIES
----------------------------------------------------------------------- */
///
/// <summary>
/// Retrieves a square on the puzzle.
/// </summary>
/// <returns>Square</returns>
/// <param name="index">Index of desired square</param>
/// <exception cref="IndexOutOfRangeException">
/// Raised if the index is out of range.
/// </exception>
///
public Square
this[ int index ]
{ get
{ if (!IsValidIndex( index ))
throw new IndexOutOfRangeException();
return _sq[ index ];
}
}
///
/// <summary>
/// Count of empty (blank) squares
/// </summary>
/// <returns>Count of empty squares [0..Squares]</returns>
///
public int
EmptyCount
{ get
{ return _iCounts[ 0 ];
}
} /* end of Grid::EmptyCount */
///
/// <summary>
/// Count of non-empty (filled) squares
/// </summary>
/// <returns>Count of non-empty squares [0..Squares]</returns>
///
public int
FilledCount
{ get
{ return (Squares - _iCounts[ 0 ]);
}
} /* end of Grid::FilledCount() */
} /* end of class Grid */
/*****************************************************************************
**
** End of grid.cs
**
*****************************************************************************/