www.pudn.com > sudoku.rar > PuzzleState.cs
//--------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// File: PuzzleState.cs
//
// Description: Stores the current configuration of a puzzle.
//
//--------------------------------------------------------------------------
using System;
using System.Text;
using System.Drawing;
using System.Collections;
using System.Collections.Specialized;
using System.Runtime.CompilerServices;
using Microsoft.Sudoku.Collections;
using Microsoft.Sudoku.Nullables;
using Microsoft.Sudoku.Techniques;
namespace Microsoft.Sudoku
{
/// Maintains the state for a particular instance of a Sudoku puzzle.
[Serializable]
public sealed class PuzzleState : ICloneable, IEnumerable
{
/// Maximum size of a puzzle state box.
private const byte _defaultBoxSize = 3;
/// Maximum size of a puzzle state box.
internal const byte MaxBoxSize = 3;
/// Maximum size of a puzzle state box.
internal const byte MinBoxSize = 3;
/// The size of each box in the puzzle.
private readonly byte _boxSize;
/// The size of the entire puzzle.
private readonly byte _gridSize;
/// The state of each cell in the puzzle.
private NullableByte[,] _grid;
/// Known difficulty level of the puzzle.
private PuzzleDifficulty _difficulty;
/// Additional data to store with the state.
private object _tag;
/// The number of cells currently filled in the puzzle.
[NonSerialized]
private NullableInt _filledCells;
/// The puzzle's current status. Invalidated every time the puzzle is changed.
[NonSerialized]
private PuzzleStatus _status;
/// Event raised when a cell in the grid changes its contained value.
[NonSerialized]
private EventHandler _stateChanged;
/// Whether to raise state changed events.
[NonSerialized]
private bool _raiseStateChangedEvent;
/// Initializes the PuzzleState.
public PuzzleState() : this(_defaultBoxSize) { }
/// Initializes the PuzzleState.
/// The size of each square in the puzzle.
internal PuzzleState(byte boxSize)
{
if (boxSize > MaxBoxSize || boxSize < MinBoxSize) throw new ArgumentOutOfRangeException("boxSize");
_boxSize = boxSize;
_gridSize = (byte)(boxSize * boxSize);
_grid = new NullableByte[_gridSize, _gridSize];
}
/// Initializes the PuzzleState.
/// The state to be cloned into this new instance.
private PuzzleState(PuzzleState state)
{
// You do not use MemberwiseClone here as the new state should not share references
_boxSize = state._boxSize; // immutable once created
_gridSize = state._gridSize; // immutable once created
_grid = (NullableByte[,])state._grid.Clone();
_status = state._status; // immutable once created
_filledCells = state._filledCells; // immutable once created
_difficulty = state._difficulty; // immutable once created
}
/// Gets the size of a box in the puzzle (the sqrt of the grid size).
public byte BoxSize { get { return _boxSize; } }
/// Gets the size of the puzzle grid.
public byte GridSize { get { return _gridSize; } }
/// Gets or sets the perceived difficulty level of this puzzle.
public PuzzleDifficulty Difficulty { get { return _difficulty; } set { _difficulty = value; } }
/// Gets or sets object data to be stored with this state. Must be serializable.
public object Tag { get { return _tag; } set { _tag = value; } }
/// Gets or sets the cell value.
/// The coordinates of the cell whose value is to be set or retrieved.
/// The value of the specified cell, or null if it has no value.
public NullableByte this[Point cell]
{
get { return _grid[cell.X, cell.Y]; }
set
{
NullableByte oldValue = _grid[cell.X, cell.Y];
if (oldValue != value)
{
_status = PuzzleStatus.Unknown;
_filledCells = null;
_grid[cell.X, cell.Y] = value;
OnStateChanged(); //cell, oldValue, value);
}
}
}
/// Gets or sets the cell value.
/// The x-coordinate of the cell whose value is to be set or retrieved.
/// The y-coordinate of the cell whose value is to be set or retrieved.
/// The value of the specified cell, or null if it has no value.
public NullableByte this[int cellX, int cellY]
{
get { return _grid[cellX, cellY]; }
set { this[new Point(cellX, cellY)] = value; }
}
/// Event raised when a cell in the grid changes its contained value.
public event EventHandler StateChanged
{
[MethodImpl(MethodImplOptions.Synchronized)]
add { _stateChanged = (EventHandler)Delegate.Combine(_stateChanged, value); }
[MethodImpl(MethodImplOptions.Synchronized)]
remove { _stateChanged = (EventHandler)Delegate.Remove(_stateChanged, value); }
}
/// Gets or sets whether to raise state changed events.
internal bool RaiseStateChangedEvent { get { return _raiseStateChangedEvent; } set { _raiseStateChangedEvent = value; } }
/// Raises the state changed event if RaiseStateChangedEvent is true.
private void OnStateChanged()
{
if (_raiseStateChangedEvent)
{
EventHandler handler = _stateChanged;
if (handler != null) handler(this, EventArgs.Empty);
}
}
/// Gets the puzzle's current status.
public PuzzleStatus Status
{
get
{
if (_status == PuzzleStatus.Unknown) _status = AnalyzeSolutionStatus();
return _status;
}
}
/// Gets the number of filled cells in the grid.
public int NumberOfFilledCells
{
get
{
if (!_filledCells.HasValue)
{
int count = 0;
foreach (NullableByte cell in _grid) if (cell.HasValue) count++;
_filledCells = count;
}
return _filledCells.Value;
}
}
/// Gets an enumerator for all of the cells in the grid.
/// An enumerator for all of the cells in the grid.
IEnumerator IEnumerable.GetEnumerator() { return _grid.GetEnumerator(); }
/// Deep clones this PuzzleState.
/// A deep clone of this PuzzleState.
public PuzzleState Clone() { return new PuzzleState(this); }
/// Deep clones this PuzzleState.
/// A deep clone of this PuzzleState.
object ICloneable.Clone() { return Clone(); }
/// Determines whether this state and the specified state represent the same filled in cells.
/// The other state to which to compare this state.
/// true if the states are equal; otherwise, false.
public override bool Equals(object obj)
{
PuzzleState other = obj as PuzzleState;
return (other != null) ? StatesMatch(this, other) : base.Equals(obj);
}
/// Returns the hash code for this instance.
/// The hash code for this instance.
public override int GetHashCode()
{
return ToString().GetHashCode();
}
/// Creates a string representation of this puzzle state.
/// A string representation of this puzzle state.
public override string ToString()
{
StringBuilder sb = new StringBuilder(GridSize*(GridSize+2));
for(int i=0; iCompares two puzzle states to determine if they're equal.
/// The first puzzle state.
/// The second puzzle state.
/// true if the states are equal; otherwise, false.
private static bool StatesMatch(PuzzleState first, PuzzleState second)
{
if (first == null) throw new ArgumentNullException("first");
if (second == null) throw new ArgumentNullException("second");
// They're equal only if the corresponding cells both contain the
// same number or are both empty.
if (first.GridSize != second.GridSize) return false;
for(int i=0; iDetermines what numbers are possible in each of the cells in the state.
/// The puzzle state to analyze.
/// The techniques to use for this elimination process.
///
/// Whether only one pass should be made through each technique, or whether it should repeat all techniques
/// as long as any technique made any changes.
///
/// How much each of the techniques was used.
/// The possible numbers used for this computation.
/// The computed possible numbers.
internal FastBitArray[][] ComputePossibleNumbers(
TechniqueCollection techniques, ref Hashtable usesOfTechnique,
bool onlyOnePass, bool earlyExitWhenSoleFound,
FastBitArray[][] possibleNumbers)
{
// Initialize the possible numbers grid
for (int i = 0; i < GridSize; i++)
{
for (int j = 0; j < GridSize; j++)
{
possibleNumbers[i][j].SetAll(this[i, j].HasValue ? false : true);
}
}
// Perform eliminations based on the techniques available to this puzzle state.
// The techniques available depend on the difficulty level of the puzzle.
bool notDone;
do
{
notDone = false;
foreach(EliminationTechnique e in techniques)
{
int numberOfChanges = 0;
bool exitedEarly = false;
notDone |= e.Execute(this, earlyExitWhenSoleFound, possibleNumbers, out numberOfChanges, out exitedEarly);
if (usesOfTechnique != null)
{
object uses = usesOfTechnique[e];
usesOfTechnique[e] = (uses != null) ?
numberOfChanges + (int)uses : numberOfChanges;
}
if (exitedEarly)
{
notDone = false;
break;
}
}
}
while(notDone && !onlyOnePass);
return possibleNumbers;
}
/// Analyzes the state of the puzzle to determine whether it is a solution or not.
/// The status of the puzzle.
private PuzzleStatus AnalyzeSolutionStatus()
{
// Need a way of keeping track of what numbers have been used (in each row, column, box, etc.)
// A bit array is a great way to do this, where each bit corresponds to a true/false value
// as to whether a number was already used in a particular scenario.
FastBitArray numbersUsed = new FastBitArray(_gridSize);
// Make sure every column contains the right numbers. It is fine if a column has holes
// as long as those cells have possibilities, in which case it is a puzzle in progress.
// However, two numbers cannot be used in the same column, even if there are holes.
for (int i = 0; i < _gridSize; i++)
{
numbersUsed.SetAll(false);
for (int j = 0; j < _gridSize; j++)
{
if (_grid[i, j].HasValue)
{
int value = _grid[i, j].Value;
if (numbersUsed[value]) return PuzzleStatus.CannotBeSolved;
numbersUsed[value] = true;
}
}
}
// Same for rows
for (int j = 0; j < _gridSize; j++)
{
numbersUsed.SetAll(false);
for (int i = 0; i < _gridSize; i++)
{
if (_grid[i, j].HasValue)
{
int value = _grid[i, j].Value;
if (numbersUsed[value]) return PuzzleStatus.CannotBeSolved;
numbersUsed[value] = true;
}
}
}
// Same for boxes
for (int boxNumber = 0; boxNumber < _gridSize; boxNumber++)
{
numbersUsed.SetAll(false);
int boxStartX = (boxNumber / _boxSize) * _boxSize;
for (int x = boxStartX; x < boxStartX + _boxSize; x++)
{
int boxStartY = (boxNumber % _boxSize) * _boxSize;
for (int y = boxStartY; y < boxStartY + _boxSize; y++)
{
if (_grid[x, y].HasValue)
{
int value = _grid[x, y].Value;
if (numbersUsed[value]) return PuzzleStatus.CannotBeSolved;
numbersUsed[value] = true;
}
}
}
}
// Now determine whether this is a solved puzzle or a work in progress
// based on whether there are any holes
for (int i = 0; i < _gridSize; i++)
{
for (int j = 0; j < _gridSize; j++)
{
if (!_grid[i, j].HasValue) return PuzzleStatus.InProgress;
}
}
// If you made it this far, this state is a valid solution!
return PuzzleStatus.Solved;
}
}
}