www.pudn.com > sudoku.rar > Generator.cs
//--------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// File: Generator.cs
//
// Description: A Sudoku puzzle generator.
//
//--------------------------------------------------------------------------
using System;
using System.Drawing;
using System.Threading;
using System.Collections;
using System.Diagnostics;
using System.Security.Cryptography;
using Microsoft.Sudoku.Utilities;
using Microsoft.Sudoku.Nullables;
using Microsoft.Sudoku.Techniques;
using Microsoft.Sudoku.Collections;
namespace Microsoft.Sudoku
{
/// Generates Sudoku puzzles.
public sealed class Generator
{
/// Options for generation.
private GeneratorOptions _options;
/// Prevent external instantiation.
/// Options used to configure how the puzzle is generated.
public Generator(GeneratorOptions options)
{
if (options == null) options = GeneratorOptions.Create(PuzzleDifficulty.Easy);
if (options.NumberOfPuzzles < 1) throw new ArgumentOutOfRangeException("options");
_options = options;
}
/// Generates a random Sudoku puzzle.
/// The generated puzzle.
public PuzzleState Generate()
{
// Puzzle generation is processor intensive, but you don't want to hog
// the CPU and make other apps noticeably slow during the process. Temporarily
// lower the processor class
using(new LowerPriorityToBelowNormal())
{
return GenerateInternal();
}
}
/// Generates a random Sudoku puzzle.
/// The generated puzzle.
private PuzzleState GenerateInternal()
{
// Generate the number of puzzles specified in the options and sort them by difficulty
ArrayList puzzles = new ArrayList();
for(int i=0; i<_options.NumberOfPuzzles; i++)
{
puzzles.Add(GenerateOne());
}
// Find the hardest puzzle from those generated and return it.
// NOTE: The puzzle may be easier than the numbers in the SolverResults
// would otherwise indicate. The generator runs each technique as much as possible
// before filling in a number, but filling in a number can actually make the puzzle
// solvable with fewer techniques.
puzzles.Sort(new SolverResultsComparer(_options.Techniques));
return ((SolverResults)puzzles[puzzles.Count-1]).Puzzle;
}
/// Used to compare the difficulty of two generated puzzles.
private sealed class SolverResultsComparer : IComparer
{
/// Techniques used to generate these puzzles.
private TechniqueCollection _techniques;
/// Initializes the comparer.
/// Techniques used to generate these puzzles.
public SolverResultsComparer(TechniqueCollection techniques)
{
if (techniques == null) throw new ArgumentNullException("techniques");
_techniques = techniques;
}
/// Compares two SolverResults.
/// The first result.
/// The second result.
/// -1 if x is less than y, 0 if they're equal, and 1 if x is greater than y.
int IComparer.Compare(object x, object y)
{
SolverResults first = x as SolverResults;
SolverResults second = y as SolverResults;
if (first == second) return 0;
else if (first == null) return 1;
else if (second == null) return -1;
else
{
// First compare by number of decision points
int diff = first.NumberOfDecisionPoints - second.NumberOfDecisionPoints;
if (diff != 0) return diff;
// Then compare each by technique, starting with the most difficult.
for(int i=_techniques.Count-1; i>=0; --i)
{
object firstUse = first.UseOfTechniques[_techniques[i]];
object secondUse = second.UseOfTechniques[_techniques[i]];
if (firstUse != null && secondUse != null)
{
diff = ((int)firstUse) - ((int)secondUse);
if (diff != 0) return diff;
}
else if (firstUse != null) return 1;
else if (secondUse != null) return -1;
}
}
// SolverResults are equal if they have the exact same number of decision points
// and usage of each technique.
return 0;
}
}
/// Generates a random Sudoku puzzle.
/// The generated results.
private SolverResults GenerateOne()
{
Thread.CurrentThread.Priority = ThreadPriority.BelowNormal;
// Generate a full solution randomly, using the solver to solve a completely empty grid.
// For this, we'll use the elimination techniques that yield fast solving.
PuzzleState solvedState = new PuzzleState(_options.Size);
SolverOptions solverOptions = new SolverOptions();
solverOptions.MaximumSolutionsToFind = 1;
solverOptions.EliminationTechniques = new TechniqueCollection(new NakedSingleTechnique());
solverOptions.AllowBruteForce = true;
SolverResults newSolution = Solver.Solve(solvedState, solverOptions);
// Create options to use for removing filled cells from the complete solution.
// MaximumSolutionsToFind is set to 2 so that we look for more than 1, but there's no
// need in continuing once we know there's more than 1, so 2 is a find value to use.
solverOptions.MaximumSolutionsToFind = 2;
solverOptions.AllowBruteForce =
!_options.MaximumNumberOfDecisionPoints.HasValue || _options.MaximumNumberOfDecisionPoints > 0;
solverOptions.EliminationTechniques = solverOptions.AllowBruteForce ?
new TechniqueCollection(new NakedSingleTechnique()) : _options.Techniques; // For perf: if brute force is allowed, techniques don't matter!
// Now that we have a full solution, we want to randomly remove values from cells
// until we get to a point where there is not a unique solution for the puzzle. The
// last puzzle state that did have a unique solution can then be used.
PuzzleState newPuzzle = newSolution.Puzzle;
// Get a random ordering of the cells in which to test their removal
Point [] filledCells = GetRandomCellOrdering(newPuzzle);
// Do we want to ensure symmetry?
int filledCellCount = _options.EnsureSymmetry && (filledCells.Length % 2 != 0) ? filledCells.Length - 1 : filledCells.Length;
// If ensuring symmetry...
if (_options.EnsureSymmetry)
{
// Find the middle cell and put it at the end of the ordering
for(int i=0; i _options.MinimumFilledCells;
filledCellNum += 2)
{
// Store the old value so we can put it back if necessary,
// then wipe it out of the cell
oldValues[0] = newPuzzle[filledCells[filledCellNum]].Value;
oldValues[1] = newPuzzle[filledCells[filledCellNum+1]].Value;
newPuzzle[filledCells[filledCellNum]] = null;
newPuzzle[filledCells[filledCellNum+1]] = null;
// Check to see whether removing it left us in a good position (i.e. a
// single-solution puzzle that doesn't violate any of the generation options)
SolverResults newResults = Solver.Solve(newPuzzle, solverOptions);
if (!IsValidRemoval(newPuzzle, newResults))
{
newPuzzle[filledCells[filledCellNum]] = oldValues[0];
newPuzzle[filledCells[filledCellNum+1]] = oldValues[1];
}
}
// If there are an odd number of cells in the puzzle (which there will be
// as everything we're doing is 9x9, 81 cells), try to remove the odd
// cell that doesn't have a pairing. This will be the middle cell.
if (filledCells.Length % 2 != 0)
{
// Store the old value so we can put it back if necessary,
// then wipe it out of the cell
int filledCellNum = filledCells.Length-1;
byte oldValue = newPuzzle[filledCells[filledCellNum]].Value;
newPuzzle[filledCells[filledCellNum]] = null;
// Check to see whether removing it left us in a good position (i.e. a
// single-solution puzzle that doesn't violate any of the generation options)
SolverResults newResults = Solver.Solve(newPuzzle, solverOptions);
if (!IsValidRemoval(newPuzzle, newResults)) newPuzzle[filledCells[filledCellNum]] = oldValue;
}
}
// otherwise, it's much easier.
else
{
// Look at each cell in the random ordering. Try to remove it.
// If it works to remove it, do so greedily. Otherwise, skip it.
for(int filledCellNum=0;
filledCellNum < filledCellCount && newPuzzle.NumberOfFilledCells > _options.MinimumFilledCells;
filledCellNum++)
{
// Store the old value so we can put it back if necessary,
// then wipe it out of the cell
byte oldValue = newPuzzle[filledCells[filledCellNum]].Value;
newPuzzle[filledCells[filledCellNum]] = null;
// Check to see whether removing it left us in a good position (i.e. a
// single-solution puzzle that doesn't violate any of the generation options)
SolverResults newResults = Solver.Solve(newPuzzle, solverOptions);
if (!IsValidRemoval(newPuzzle, newResults)) newPuzzle[filledCells[filledCellNum]] = oldValue;
}
}
// Make sure to now use the techniques specified by the user to score this thing
solverOptions.EliminationTechniques = _options.Techniques;
SolverResults finalResult = Solver.Solve(newPuzzle, solverOptions);
// Return the best puzzle we could come up with
newPuzzle.Difficulty = _options.Difficulty;
return new SolverResults(PuzzleStatus.Solved, newPuzzle, finalResult.NumberOfDecisionPoints, finalResult.UseOfTechniques);
}
/// Returns all cells in a collection in random order.
/// The puzzle state.
/// The collection of cells.
private static Point [] GetRandomCellOrdering(PuzzleState state)
{
// Create the collection
Point [] points = new Point[state.GridSize*state.GridSize];
// Find all cells
int count=0;
for (int i = 0; i < state.GridSize; i++)
{
for (int j = 0; j < state.GridSize; j++)
{
points[count++] = new Point(i,j);
}
}
// Randomize their order
for(int i=0; i
/// Based on the specified GeneratorOptions, determines whether the SolverResults
/// created by solving a puzzle with a particular cell value removed represents a valid
/// new state.
///
/// The puzzle state being validated.
/// The SolverResults to be verified.
/// true if the removal that led to this call is valid; otherwise, false.
private bool IsValidRemoval(PuzzleState state, SolverResults results)
{
// Make sure we have a puzzle with one and only one solution
if (results.Status != PuzzleStatus.Solved || results.Puzzles.Count != 1) return false;
// Make sure we don't have too few cells
if (state.NumberOfFilledCells < _options.MinimumFilledCells) return false;
// Now check to see if too many decision points were involved
if (_options.MaximumNumberOfDecisionPoints.HasValue &&
results.NumberOfDecisionPoints > _options.MaximumNumberOfDecisionPoints) return false;
// Otherwise, it's a valid removal.
return true;
}
}
}