www.pudn.com > sudoku.rar > Solver.cs
//--------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// File: Solver.cs
//
// Description: Sudoku puzzle solver.
//
//--------------------------------------------------------------------------
using System;
using System.Drawing;
using System.Collections;
using Microsoft.Sudoku.Techniques;
using Microsoft.Sudoku.Collections;
using Microsoft.Sudoku.Utilities;
namespace Microsoft.Sudoku
{
/// Analyzes and solves Sudoku puzzles.
public sealed class Solver
{
/// Prevent external instantiation.
private Solver(){}
/// Evaluates the difficulty level of a particular puzzle.
/// The puzzle to evaluate.
/// The perceived difficulty level of the puzzle.
public static PuzzleDifficulty EvaluateDifficulty(PuzzleState state)
{
if (state == null) throw new ArgumentNullException("state");
SolverOptions options = new SolverOptions();
foreach(PuzzleDifficulty diff in new PuzzleDifficulty[]{PuzzleDifficulty.Easy, PuzzleDifficulty.Medium, PuzzleDifficulty.Hard})
{
GeneratorOptions go = GeneratorOptions.Create(diff);
if (state.NumberOfFilledCells < go.MinimumFilledCells) continue;
options.AllowBruteForce = !go.MaximumNumberOfDecisionPoints.HasValue;
options.EliminationTechniques = go.Techniques;
options.MaximumSolutionsToFind = options.AllowBruteForce ? 2u : 1u;
SolverResults results = Solver.Solve(state, options);
if (results.Status == PuzzleStatus.Solved &&
results.Puzzles.Count == 1) return diff;
}
return PuzzleDifficulty.Invalid;
}
/// Attempts to solve a Sudoku puzzle.
/// The state of the puzzle to be solved.
/// Options to use for solving.
/// The result of the solve attempt.
/// No changes are made to the parameter state.
public static SolverResults Solve(PuzzleState state, SolverOptions options)
{
// Validate parameters
if (state == null) throw new ArgumentNullException("state");
if (options == null) throw new ArgumentNullException("options");
bool addedTechnique = false;
if (options.EliminationTechniques.Count == 0)
{
options.EliminationTechniques.Add(new NakedSingleTechnique());
addedTechnique = true;
}
// Turn off the raising of changed events while solving,
// though it probably doesn't matter as the first thing
// SolveInternal does is make a clone, and RaiseStateChangedEvent
// is not cloned (on purpose).
bool raiseChangedEvent = state.RaiseStateChangedEvent;
state.RaiseStateChangedEvent = false;
// Attempt to solve the puzzle
SolverResults results = SolveInternal(state, options);
// Reset whether changed events should be raised
state.RaiseStateChangedEvent = raiseChangedEvent;
if (addedTechnique) options.EliminationTechniques = new TechniqueCollection();
// Return the solver results
return results;
}
/// Attempts to solve a Sudoku puzzle.
/// The state of the puzzle to be solved.
/// Options to use for solving.
/// The result of the solve attempt.
/// No changes are made to the parameter state.
private static SolverResults SolveInternal(PuzzleState state, SolverOptions options)
{
// First, make a copy of the state and work on that copy. That way, the original
// instance passed to us by the client remains unmodified.
state = state.Clone();
// Fill cells using logic and analysis techniques until no more
// can be filled.
Hashtable totalUseOfTechniques = new Hashtable();
FastBitArray [][] possibleNumbers = FillCellsWithSolePossibleNumber(state, options.EliminationTechniques, ref totalUseOfTechniques);
// Analyze the current state of the board
switch (state.Status)
{
// If the puzzle is now solved, return it. If the puzzle is in an inconsistent state (such as
// two of the same number in the same row), return that also, as there's nothing more to be done.
case PuzzleStatus.Solved:
case PuzzleStatus.CannotBeSolved:
return new SolverResults(state.Status, state, 0, totalUseOfTechniques);
// If the puzzle is still in progress, it means no more cells
// can be filled by elimination alone, so do a brute-force step.
// BruteForceSolve recursively calls back to this method.
default:
if (options.AllowBruteForce)
{
SolverResults results = BruteForceSolve(state, options, possibleNumbers);
if (results.Status == PuzzleStatus.Solved)
{
AddTechniqueUsageTables(results.UseOfTechniques, totalUseOfTechniques);
}
return results;
}
else return new SolverResults(PuzzleStatus.CannotBeSolved, state, 0, null);
}
}
/// Uses brute-force search techniques to solve the puzzle.
/// The state to be solved.
/// The options to use in solving.
/// The possible numbers off of which to base the search.
/// The result of the solve attempt.
/// Changes may be made to the parameter state.
private static SolverResults BruteForceSolve(PuzzleState state, SolverOptions options, FastBitArray [][] possibleNumbers)
{
// A standard brute-force search would take much too long to solve a Sudoku puzzle.
// Fortunately, there are ways to significantly trim the search tree to a point where
// brute-force is not only possible, but also more efficient. The idea is that not every number
// can be put into every cell. In fact, using elimination techniques, you can narrow down the list
// of numbers for each cell, such that only those need be are tried. Moreover, every time a new number
// is entered into a cell, other cell's possible numbers decrease. It's in your best interest
// to start the search with a cell that has the least possible number of options, thereby increasing
// your chances of "guessing" the right number sooner. To this end, you find the cell in the grid
// that is empty and that has the least number of possible numbers that can go in it. If there is more
// than one cell with the same number of possibilities, you choose randomly among them. This random
// choice allows the solver to be used for puzzle generation.
ArrayList bestGuessCells = new ArrayList();
int bestNumberOfPossibilities = state.GridSize + 1;
for (int i = 0; i < state.GridSize; i++)
{
for (int j = 0; j < state.GridSize; j++)
{
int count = possibleNumbers[i][j].CountSet;
if (!state[i, j].HasValue)
{
if (count < bestNumberOfPossibilities)
{
bestNumberOfPossibilities = count;
bestGuessCells.Clear();
bestGuessCells.Add(new Point(i, j));
}
else if (count == bestNumberOfPossibilities)
{
bestGuessCells.Add(new Point(i, j));
}
}
}
}
// If there are no cells available to fill, there is nothing you can do
// to make forward progress. If there are cells available, which should
// always be the case when this method is called, go through each of the possible
// numbers in the cell and try to solve the puzzle with that number in it.
SolverResults results = null;
if (bestGuessCells.Count > 0)
{
// Choose a random cell from amongst the possibilities found above
Point bestGuessCell = (Point)bestGuessCells[RandomHelper.GetRandomNumber(bestGuessCells.Count)];
// Get the possible numbers for that cell. For each possible number,
// fill that number into the cell and recursively call to Solve.
FastBitArray possibleNumbersForBestCell = possibleNumbers[bestGuessCell.X][bestGuessCell.Y];
for(byte p=0; p 0)
{
results.Puzzles.AddRange(tempResults.Puzzles);
}
else
{
results = tempResults;
results.NumberOfDecisionPoints++;
}
if (options.MaximumSolutionsToFind.HasValue &&
results.Puzzles.Count >= options.MaximumSolutionsToFind.Value) return results;
}
// If you are not cloning, you need to cancel out the change
newState[bestGuessCell] = null;
}
}
}
// You will get here if the requested number of solutions could not be found, or if no
// solutions at all could be found. Either return a solution if you did get at least one,
// or return that none could be found.
return results != null ? results : new SolverResults(PuzzleStatus.CannotBeSolved, state, 0, null);
}
/// Combines an incremental usage table into the total usage table.
/// The total table.
/// The incremental table.
private static void AddTechniqueUsageTables(Hashtable totalTable, Hashtable incrementalTable)
{
if (totalTable != null && incrementalTable != null)
{
foreach(DictionaryEntry entry in incrementalTable)
{
object value = totalTable[entry.Key];
totalTable[entry.Key] = value != null ?
(int)entry.Value + (int)value : (int)entry.Value;
}
}
}
/// Attempts to fill one square in the Sudoku puzzle, based purely on logic and elimination techniques.
/// The state to be augmented.
/// The techniques to use for number elimination.
/// The total usage of each technique.
/// The current set of possible numbers for each cell.
/// Changes may be made to the parameter state.
private static FastBitArray [][] FillCellsWithSolePossibleNumber(
PuzzleState state, TechniqueCollection techniques, ref Hashtable totalUseOfTechniques)
{
FastBitArray [][] possibleNumbers = PuzzleState.InstantiatePossibleNumbersArray(state);
bool moreToDo;
do
{
moreToDo = false;
byte gridSize = state.GridSize;
state.ComputePossibleNumbers(techniques, ref totalUseOfTechniques, false, false, possibleNumbers);
for(byte i=0; i