- Sudoku Part 0: Introduction
- Sudoku Part 1: Defining The Solver Behavior
- Sudoku Part 2: Implementing A Solver
- Sudoku Part 3: Defining The Generator Behavior
- Sudoku Part 4: Implementing A Generator
In the previous posting (Defining The Solver Behavior) we discussed the needed behavior in order to build a working Sudoku solver. Today we're going to build our first implementation of a solver which exhibits the previously described behaviors.
Algorithm
For the first solver I took a relatively simple approach. It's not quite a brute-force solver, but it is close. I call the first implementation the RecursiveSolver, since it solves the puzzle using a recursive algorithm.
In order to solve the puzzle we'll first analyze the board position to determine the number of candidate values for each puzzle piece. The set of candiate values will be the full list of values minus the set of values in the piece's row, minus the set of values in the piece's column and then minus the set of values in the piece's region.
Once we have computed the candidate values for each piece, we'll record the piece with the fewest candidate values. We'll then loop over the candidate values in a random order calculating the piece with the minimum candidates given that move and continuing the process.
If we find a board position where there are no longer any pieces without an assigned value we know we have found a solution. If we have already recorded a value solution and we find a second board position we know we have found an invalid position.
If we found a board position where there is a piece with 0 potential values, we know we have traversed a path which will not lead to a solution.
If we traverse all possible paths of the puzzle and can not find a solution, then we know we have an unsolvable puzzle as our algorithm would have examined every possible choice a solver could make.
Broken into steps our algorithm looks like the following:
- Find The Piece With The Minimum Number Of Candidate Values
- If A Piece Is Found With No Candidate Values, Return Without Solution
- If No Pieces exist with Candidate Values Return the Solution We Are Done
- Loop Over Each Candidate Value
- Assign the Value to the Solution
- Return To Step 1 Given The New State
- If We Found A Solution, Verify That We Have Not Previously Found A Solution
- Loop To Step 4 Until No Other Candidates Are Available
- Return The Solution If It Was Found
In the last installment we created abstract behavior tests since we did not have a specific implementation of a solver. We had a set of behaviors we wanted all potential solver implementations to exhibit. So first we need to create concrete test classes which inherit from our abstract ones.
First, let's look at what we need to do for the case when a puzzle is solved:
[TestClass]
public class When_RecursiveSolver_Solves_A_Puzzle : When_A_Puzzle_Is_Solved
{
public When_RecursiveSolver_Solves_A_Puzzle()
: base(new RecursiveSolver())
{
}
}
That's pretty simple isn't it? Now, this works fine with the MSTest tool, I have not actually verified that this technique works in other .NET unit testing frameworks, but I believe it does. We rely on inheritance to pull all of our expectations from our base test class.
We can continue this pattern for all other behavior cases as well. Take special note to the fact that we are constructing the instance of the solver we want to test in the constructor of the test class. This is needed since our base class takes an ISolver to use for its test cases.
Solver Source
Now let's look at the good stuff. What does the solver code look like?
public class RecursiveSolver : ISolver
{
private Random rand;
public RecursiveSolver()
{
this.rand = new Random();
}
#region ISolver Members
public Solution Solve(Puzzle puzzle)
{
Solution solution = new Solution(puzzle);
solution = SolvePiece(FindMinimumCandidatePiece(solution), solution);
return solution;
}
#endregion
private Solution SolvePiece(Piece piece, Solution solution)
{
//when the provided piece is null we know there are no remaining
//pieces to be filled in indicating that the puzzle is solved.
if (piece == null)
{
return solution;
}
//we clone the current solution to ensure that we always provide
//later steps with the same configuration. Otherwise once the item
//recursed the values within the soultion reference would have changed.
solution = (Solution)solution.Clone();
Solution returnSolution = null;
Solution foundSolution = null;
HashSet<Value&*gt; candidates = CalculateCandidates(piece, solution);
//loop over all possible choices for this piece. If we finish
//looping and no slution was found the earlier steps will have
//a null solution indicating the path was incorrect.
while (candidates.Count > 0)
{
solution.Values[piece] = candidates.PopRandomItem();
returnSolution = SolvePiece(FindMinimumCandidatePiece(solution), solution);
if (returnSolution != null)
{
if (foundSolution != null)
{
throw new DuplicateSolutionFoundException("Provided puzzle is invalid.");
}
foundSolution = returnSolution;
}
}
return foundSolution;
}
private Piece FindMinimumCandidatePiece(Solution solution)
{
Piece foundPiece = null;
int minimumCandidates = 10;
foreach (Piece piece in solution.Puzzle.Pieces)
{
if (!solution.Values.ContainsKey(piece))
{
HashSet<Value> candidates = CalculateCandidates(piece, solution);
if (candidates.Count < minimumcandidates)
{
minimumCandidates = candidates.Count;
foundpiece = piece;
//If we found a piece with only 1 candidate we can stop looking
//since 1 is the minimum possible candidates for a valid piece.
if (minimumCandidates == 1)
{
break;
}
}
}
}
return foundPiece;
}
private HashSet<Value> CalculateCandidates(Piece piece, Solution solution)
{
HashSet<Value> candidates = new HashSet<Value>((Value[])Enum.GetValues(typeof(Value)));
candidates.ExceptWith(GetAssignedValues(piece.Column, solution));
candidates.ExceptWith(GetAssignedValues(piece.Row, solution));
candidates.ExceptWith(GetAssignedValues(piece.Region, solution));
return candidates;
}
private HashSet<Value> GetAssignedValues(IEnumerable<Piece> pieces, Solution solution)
{
HashSet<Value> values = new HashSet<Value>();
foreach (Piece piece in pieces)
{
if (solution.Values.ContainsKey(piece))
{
values.Add(solution.Values[piece]);
}
}
return values;
}
}
Notice that there is actually a lot of logic within this solver. While it could be argued that some of this logic deserves its own behavior class, at this time I'm going to consider it premature optimization, and leave it for future refactoring.
For example the ability to calculate potential values isn't something which is specific to a solver, or at least this solver. This could be usable elsewhere. If/When it becomes valuable to break it out we'll do it.
Also of note is the PopRandomValue method on the HashSet<>. PopRandomValue is obviously an extension method here, just don't tell anyone! This method randomly selects an item from the Set and then removes it from the set so it won't be selected next time. The implementation is as follows:
public static class HashSetExtension
{
private static Random rand;
static HashSetExtension()
{
rand = new Random();
}
public static T PopRandomItem(this HashSet<T> set)
{
List<T> list = new List<T>(set);
T item = list[rand.Next(0, list.Count - 1)];
set.Remove(item);
return item;
}
}
What do we have to show for all of our effort? Well a pretty screen with lots of green of course!
Notes
Note that we could have included additional behavior tests regarding how this particular solver should behave. At this time I don't deem it necessary since our only real requirements is that the solver gives valid solutions when one is available, and reports when no solution is available.
As previously mentioned we could break apart some items of this solver into multiple solvers. We'll investigate those possibilities at a later point.
Look for the next section where we'll discuss our Sudoku puzzle generator!
-- John Chapman
1 comment:
Thanks for this great one.
Post a Comment