Sudoku Part 1: Defining The Solver Behavior

• 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 introduction I talked briefly about my goals for this series. I wanted to create both a Sudoku generator which could generate puzzles for both myself and a theoretical automatic solver. There are many places to find such tools on the internet, but my goal was to use this as an exercise to show how someone could use various techniques and tools such as Behavior-Driven Development and the Castle Windsor Project. Today, we'll start with Behavior-Driven Development.

Needed Behavior

What are we trying to accomplish Here? Let's start with the Sudoku Solver first. Let's pretend that I am having a conversation with a customer who is asking me to write this Sudoku solver for them. Let's also say that I am not familiar with sudoku puzzles. First the customer explains to me that a Sudoku puzzle is a 9x9 grid with 9 3x3 sub-regions within the grid where each cell can hold a value from 1-9. He also explains that the puzzle begins with some of the cells (or pieces) already filled in for us, and the rest is for the solver to fill in.

So we have the following dialog:

• What happens when the puzzle is solved?

• All cells should be assigned a value.
• No column should have duplicate values.
• No row should have duplicate values.
• No region should have duplicate values.

The customer explains to me that if the solution meets the provided criteria we are guaranteed of a valid solution for the given puzzle. But then I start thinking. Is it possible to be given a Sudoku puzzle which has many possible solutions? I think that if I don't place any pieces, clearly there would be many possible solutions. So this leads to the following:

• What happens when a puzzle has multiple solutions?
• The puzzle should be reported as invalid.

Ok, so now I know what happens if a puzzle has many solutions, but what if the puzzle has no solution.

• What happens when a puzzle has no solution?
• There is no solution for the puzzle.

Ok, so my customer gave me a pretty weird look on that one, but there is nothing wrong with asking right?

Note that my customer has not told me any specifics about how he or she would like the puzzle to be solved, only that the puzzle should be solved and what the result of a valid solved puzzle would be.

Letting The Behavior Drive Our Development

Ok, so now I'm back in the office, ready to begin work on the Sudoku solver for my customer. Where do I begin? This is where the Behavior-Driven Development (BDD) comes in to play. Behavior-Driven Development is basically a Test-Driven Development (TDD) technique where your tests are designed around the needed behaviors of your software. This should result in tests which are far easier to refactor, since most changes results in complete removal or replacement of tests instead of removing pieces of a method based test.

Additionally by wording your tests in such a way that it portrays the resulting behavior of the software, the results of the tests become easy for our customers to read to understand how the software is working.

Let's look at the resulting unit tests to show what I'm talking about. First lets look at solving a valid puzzle. (*Warning* These tests are currently written in MSTest, I will most likely change to NUnit or mbUnit before releasing the entire source code.)

[TestClass]
public abstract class When_A_Puzzle_Is_Solved
{
  private Sudoku.Solver.ISolver solver;
  private Puzzle puzzle;
  private Solution solution;

  public When_A_Puzzle_Is_Solved(Sudoku.Solver.ISolver solver)
  {
    this.solver = solver;
  }

  [TestInitialize]
  public void Initialize()
  {
    CreateSolvablePuzzle();
    solution = solver.Solve(puzzle);
  }

  private void CreateSolvablePuzzle()
  {
    puzzle = new Puzzle();

    puzzle.Rows[0][1].AssignedValue = Value.Five;
    puzzle.Rows[0][2].AssignedValue = Value.Four;
    puzzle.Rows[0][7].AssignedValue = Value.Two;
    puzzle.Rows[1][0].AssignedValue = Value.Three;
    puzzle.Rows[1][3].AssignedValue = Value.Four;
    puzzle.Rows[2][0].AssignedValue = Value.Seven;
    puzzle.Rows[2][3].AssignedValue = Value.Eight;
    puzzle.Rows[2][6].AssignedValue = Value.Three;
    puzzle.Rows[2][7].AssignedValue = Value.Five;
    puzzle.Rows[3][1].AssignedValue = Value.Seven;
    puzzle.Rows[3][2].AssignedValue = Value.One;
    puzzle.Rows[3][5].AssignedValue = Value.Five;
    puzzle.Rows[3][8].AssignedValue = Value.Three;
    puzzle.Rows[4][0].AssignedValue = Value.Six;
    puzzle.Rows[4][3].AssignedValue = Value.Three;
    puzzle.Rows[4][5].AssignedValue = Value.Eight;
    puzzle.Rows[4][8].AssignedValue = Value.Nine;
    puzzle.Rows[5][0].AssignedValue = Value.Five;
    puzzle.Rows[5][3].AssignedValue = Value.Nine;
    puzzle.Rows[5][6].AssignedValue = Value.Four;
    puzzle.Rows[5][7].AssignedValue = Value.Seven;
    puzzle.Rows[6][1].AssignedValue = Value.Eight;
    puzzle.Rows[6][2].AssignedValue = Value.Five;
    puzzle.Rows[6][5].AssignedValue = Value.Four;
    puzzle.Rows[6][8].AssignedValue = Value.One;
    puzzle.Rows[7][5].AssignedValue = Value.Three;
    puzzle.Rows[7][8].AssignedValue = Value.Six;
    puzzle.Rows[8][1].AssignedValue = Value.Six;
    puzzle.Rows[8][6].AssignedValue = Value.Eight;
    puzzle.Rows[8][7].AssignedValue = Value.Nine;
  }

  [TestMethod]
  public void All_Pieces_Should_Have_A_Value()
  {
    foreach (Piece piece in puzzle.Pieces)
    {
      Assert.IsTrue(solution.Values.ContainsKey(piece));
    }
  }

  [TestMethod]
  public void No_Column_Should_Have_Duplicate_Values()
  {
    foreach (Column col in puzzle.Columns)
    {
      List<Value> foundValues = new List<Value>();
      foreach (Piece piece in col)
      {
        Assert.IsFalse(foundValues.Contains(solution.Values[piece]));
        foundValues.Add(solution.Values[piece]);
      }
    }
  }

  [TestMethod]
  public void No_Row_Should_Have_Duplicate_Values()
  {
    foreach (Row row in puzzle.Rows)
    {
      List<Value> foundValues = new List<Value>();
      foreach (Piece piece in row)
      {
        Assert.IsFalse(foundValues.Contains(solution.Values[piece]));
        foundValues.Add(solution.Values[piece]);
      }
    }
  }

  [TestMethod]
  public void No_Region_Should_Have_Duplicate_Values()
  {
    foreach (Region region in puzzle.Regions)
    {
      List<Value> foundValues = new List<Value>();
      foreach (Piece piece in region)
      {
        Assert.IsFalse(foundValues.Contains(solution.Values[piece]));
        foundValues.Add(solution.Values[piece]);
      }
    }
  }
}

Notice how closely these tests match the above dialog I had with the fictional customer. Anyone, including the customer should be able to read that test fixture (especially how it formatted in a proper runner) and verify that the behavior is correct. Plus, the test methods themselves are very short, easy to read and verify.

Behavior-Driven Development works by you first defining the scenario. The scenario becomes the test class itself with the test initialization being the place where we place our objects in to the appropriate state for our scenario. Each method then becomes a validation of what happens in a given scenario. The methods and class names are then written out as words so it easy to tell what behaviors are being tested.

Note that the initialization logic of this test builds a valid Sudoku puzzle and then asks the solver to solve it. As proof of a valid solution I have provided the puzzle and the associated solution in red below.


There are a few things which need to be explained in this code.

First, I chose to use an enumeration for puzzle values as a way to limit the values of the puzzle. This actually looks very lame when I read it, having the names of numbers represent the numbers themselves, and it may be refactored at a later point, but for now it helped me ensure no 0s or 10s showed up (although I have learned that enumerations are pretty lame and nothing stops you from assigning an invalid integer value to the enumeration, but that's a post for another day).

Second, notice that I used an interface for my solver, not a specific solver. The reason for this is really simple. I don't know at this point how the puzzle will be solved, only what the result of a solver should be. It doesn't matter how the internal solver works at this point, provided it sticks to the interface and this root behavior.

I also made the choice to make the Puzzle class and a separate Solution class. Basically this just allows a puzzle to remain free of solution information and would theoretically allow someone to make Puzzle classes persistable and not have to worry about updating a puzzle while creating a solution for it.

Now that we have our behaviors defined for what happens with a valid puzzle, lets move on to the other cases which were discussed in the dialog with the customer.

[TestClass]
public abstract class When_A_Puzzle_Has_Multiple_Solutions
{
  private ISolver solver;
  private Puzzle puzzle;

  public When_A_Puzzle_Has_Multiple_Solutions(ISolver solver)
  {
    this.solver = solver;
  }

  [TestInitialize]
  public void Initialize()
  {
    CreateInvalidPuzzle();
  }

  private void CreateInvalidPuzzle()
  {
    puzzle = new Puzzle();

    puzzle.Rows[4][4].AssignedValue = Value.Five;
  }

  [TestMethod]
  [ExpectedException(typeof(DuplicateSolutionFoundException))]
  public void The_Solver_Should_Report_An_Invalid_Puzzle()
  {
    solver.Solve(puzzle);
  }
}

Note that in this scenario, many valid sudoku boards could be created when only one piece is filled in. As such we are saying that whenever a puzzle with many solutions is provided we expect any solver to throw an exception.

I'm not actually a big fan of this approach, but I did it anyways here. Basically checking for duplicate solutions is something which I think would actually be useful for business logic. Therefore I for see cases where I could wind up using this exception for flow control, which I am opposed to. However, since at this point I just need a failure it works fine, and I can always refactor it later.

There is still one case remaining from the solver discussion:

[TestClass]
public abstract class When_A_Puzzle_Has_No_Solution
{
  private Puzzle puzzle;
  private ISolver solver;

  public When_A_Puzzle_Has_No_Solution(ISolver solver)
  {
    this.solver = solver;
  }

  [TestInitialize]
  public void Initialize()
  {
    puzzle = new Puzzle();

    puzzle.Rows[0][0].AssignedValue = Value.Five;
    puzzle.Rows[0][1].AssignedValue = Value.One;
    puzzle.Rows[0][2].AssignedValue = Value.Three;
    puzzle.Rows[0][3].AssignedValue = Value.Two;
    puzzle.Rows[0][4].AssignedValue = Value.Nine;
    puzzle.Rows[0][5].AssignedValue = Value.Four;
    puzzle.Rows[0][6].AssignedValue = Value.Eight;
    puzzle.Rows[0][7].AssignedValue = Value.Seven;
    puzzle.Rows[0][8].AssignedValue = Value.Six;
    puzzle.Rows[1][0].AssignedValue = Value.Eight;
    puzzle.Rows[1][1].AssignedValue = Value.Two;
    puzzle.Rows[1][2].AssignedValue = Value.Seven;
    puzzle.Rows[1][3].AssignedValue = Value.Five;
    puzzle.Rows[1][4].AssignedValue = Value.Six;
    puzzle.Rows[1][5].AssignedValue = Value.One;
    puzzle.Rows[1][6].AssignedValue = Value.Three;
    puzzle.Rows[1][7].AssignedValue = Value.Four;
    puzzle.Rows[1][8].AssignedValue = Value.Nine;
    puzzle.Rows[2][0].AssignedValue = Value.Nine;
    puzzle.Rows[2][1].AssignedValue = Value.Six;
    puzzle.Rows[2][2].AssignedValue = Value.Four;
    puzzle.Rows[2][3].AssignedValue = Value.Seven;
    puzzle.Rows[2][4].AssignedValue = Value.Eight;
    puzzle.Rows[2][5].AssignedValue = Value.Three;
    puzzle.Rows[2][6].AssignedValue = Value.One;
    puzzle.Rows[2][7].AssignedValue = Value.Two;
    puzzle.Rows[2][8].AssignedValue = Value.Five;
    puzzle.Rows[3][0].AssignedValue = Value.Six;
    puzzle.Rows[3][1].AssignedValue = Value.Five;
    puzzle.Rows[3][2].AssignedValue = Value.One;
    puzzle.Rows[3][3].AssignedValue = Value.Three;
    puzzle.Rows[3][4].AssignedValue = Value.Seven;
    puzzle.Rows[3][5].AssignedValue = Value.Nine;
    puzzle.Rows[3][6].AssignedValue = Value.Two;
    puzzle.Rows[3][7].AssignedValue = Value.Eight;
    puzzle.Rows[3][8].AssignedValue = Value.Four;
    puzzle.Rows[4][0].AssignedValue = Value.Two;
    puzzle.Rows[4][1].AssignedValue = Value.Eight;
    puzzle.Rows[4][2].AssignedValue = Value.Nine;
    puzzle.Rows[4][3].AssignedValue = Value.One;
    puzzle.Rows[4][4].AssignedValue = Value.Five;
    puzzle.Rows[4][5].AssignedValue = Value.Six;
    puzzle.Rows[4][6].AssignedValue = Value.Seven;
    puzzle.Rows[4][7].AssignedValue = Value.Three;
  }

  [TestMethod]
  public void No_Solution_Should_Be_Provided()
  {
    Assert.IsNull(solver.Solve(puzzle));
  }
}

Note that for this scenario I took the puzzle from Part 0 which proved to be unsolvable and used it as my test puzzle.

Hopefully this gives you a good idea of how to define your behaviors. In the next post we'll look at creating concrete tests for an actual implementation of a solver that exhibits the behaviors we discussed here. Note that we discussed the behavior unit tests first since when developing with Behavior-Driven Development, the behavior tests come first!

--John Chapman