Sudoku Part 4: Implementing A Generator

• 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 our last segment (Defining The Generator Behavior) we looked at the specifications required to generate new Sudoku puzzles. It turned out that from a specification standpoint, there were not many expectations that we placed on the generator. We basically just want a solvable sudoku puzzle. We didn't much care how it worked, or what the puzzle looked like, so long as the result was uniquely solvable.

Algorithm

Today, we're going to create our very first sudoku solver using a similar technique as the one we used to actually solve the puzzle. We're going to develop what I call the RecursiveGenerator.

In order to generate our puzzle, we'll first fill all board pieces with a valid sudoku value. While we're filling in each piece we'll ensure that we never create an invalid board. Meaning that at no time will we have a board with duplicate row values, column values or region values. We'll utilize a recursive algorithm very similar to the RecurisveSolver we developed previously.

Now that we have a fully populated sudoku board with no duplicate row, column or region values, we'll start removing values from random pieces. In order to do this we'll create a list of all pieces on the board and then assign a random double value to them and sort the list. We'll iterate over the list removing that piece's value from our board until our ISolver implementation reports that our board is an invalid puzzle. At this time we'll put back the last piece we removed and consider the puzzle generated.

Test Class Implementation

Our test class to test our generator implementation is only minimally more complex than the solver implementation we used in an earlier section. Because this generator we built has a dependency on an ISolver we need to provide an implementation which we have already tested so that our generator can operate successfully. For this we're obviously going to use our already tested RecursiveSolver implementation. Note that while it would be possible to use a different type of solver (or notably a mock solver), doing this would most likely require significant changes to the tests which we are running, and this is not an exercise we're yet willing to go through.

[TestClass]
public class When_RecursiveGenerator_Generates_A_Puzzle : When_A_New_Puzzle_Is_Generated
{
  public When_RecursiveGenerator_Generates_A_Puzzle()
    : base(new RecusiveGenerator(new RecursiveSolver()))
  {

  }
}

Notice that the only new twist to this code is that our constructor for RecursiveGenerator must now takes an implementation of ISolver.

RecursiveGenerator Source

public class RecusiveGenerator : IGenerator
{
  private Random rand;
  private ISolver solver;

  public RecusiveGenerator(ISolver solver)
  {
    rand = new Random();
    this.solver = solver;
  }

  public Puzzle Generate()
  {
    Puzzle puzzle = new Puzzle();
    
    //fully fill a puzzle with valid pieces
    GeneratePiece(GetMinimumPosibilityPiece(puzzle), puzzle);

    //now remove random values until the puzzle is no longer
    //uniquely solvable.

    SortedList<double, Piece> sortedPieces = new SortedList<double, Piece>();
    foreach (Piece piece in puzzle.Pieces)
    {
      sortedPieces.Add(rand.NextDouble(), piece);
    }

    Piece lastPiece = null;
    Value? lastValue = null;

    try
    {
      foreach (double key in sortedPieces.Keys)
      {
        lastPiece = sortedPieces[key];
        lastValue = lastPiece.AssignedValue;
        lastPiece.AssignedValue = null;
        solver.Solve(puzzle);
      }
    }
    catch (DuplicateSolutionFoundException)
    {
      //when we reach the point of a duplicate solution
      //we need to put the last value we stripped off back.
      lastPiece.AssignedValue = lastValue;
    }
    
    return puzzle;
  }

  private bool GeneratePiece(Piece piece, Puzzle puzzle)
  {
    if (piece == null)
    {
      return true;
    }

    HashSet<Value> potentials = CalculatePotentials(piece);

    do
    {
      piece.AssignedValue = null;

      // if there are no potential values for this piece then
      // we have reached the end of the line.
      if (potentials.Count == 0)
      {
        return false;
      }

      piece.AssignedValue = potentials.PopRandomItem();
    } while (!GeneratePiece(GetMinimumPosibilityPiece(puzzle), puzzle));

    return true;
  }

  private Piece GetMinimumPosibilityPiece(Puzzle puzzle)
  {
    Piece minimumPiece = null;
    int minimumPossiblities = Enum.GetValues(typeof(Value)).Length + 1;

    foreach (Piece piece in puzzle.Pieces)
    {
      int possibilities = CalculatePotentials(piece).Count;
      if (!piece.AssignedValue.HasValue && possibilities < minimumPossiblities)
      {
        minimumPossiblities = possibilities;
        minimumPiece = piece;
      }
    }

    return minimumPiece;
  }
  
  private HashSet<Value> CalculatePotentials(Piece piece)
  {
    HashSet<Value> potentials = GetPossibleValues();

    potentials.IntersectWith(GetSolutionValues(piece.Column));
    potentials.IntersectWith(GetSolutionValues(piece.Row));
    potentials.IntersectWith(GetSolutionValues(piece.Region));

    return potentials;
  }

  private HashSet<Value> GetSolutionValues(IEnumerable<Piece> pieces)
  {
    HashSet<Value> values = GetPossibleValues();
    foreach (Piece piece in pieces)
    {
      if (piece.AssignedValue != null)
      {
        values.Remove(piece.AssignedValue.Value);
      }
    }

    return values;
  }

  private HashSet<Value> GetPossibleValues()
  {
    HashSet<Value> values = new HashSet<Value>();
    foreach (Value val in Enum.GetValues(typeof(Value)))
    {
      values.Add(val);
    }
    return values;
  }
}

Notice that a lot of this code is very similar to that of the solver. This could probably be refactored, but for now we'll leave as is.

Again, what do we have to show for our hard word? Our green lights of course!

Notes

For those readers with a keen eye, something may seem less than optimal regarding the approaches we took here in this section. We'll get in to what those may be and what we can do about them in future segments after we have built a UI to be able to show these generated Sudoku puzzles.