How can I use TDD to solve a puzzle with an unknown answer?

Recently I wrote a Ruby program to determine solutions to a "Scramble Squares" tile puzzle:

I used TDD to implement most of it, leading to tests that looked like this:

it "has top, bottom, left, right" do
  c =
  card =[0] == :CT
  card.bottom.should == :WB
  card.left.should == :MT
  card.right.should == :BT

This worked well for the lower-level "helper" methods: identifying the "sides" of a tile, determining if a tile can be validly placed in the grid, etc.

But I ran into a problem when coding the actual algorithm to solve the puzzle. Since I didn't know valid possible solutions to the problem, I didn't know how to write a test first.

I ended up writing a pretty ugly, untested, algorithm to solve it:

  def play_game
    working_states = []
    after_1 = step_1
    i = 0
    after_1.each do |state_1|
      step_2(state_1).each do |state_2|
        step_3(state_2).each do |state_3|
          step_4(state_3).each do |state_4|
            step_5(state_4).each do |state_5|
              step_6(state_5).each do |state_6|
                step_7(state_6).each do |state_7|
                  step_8(state_7).each do |state_8|
                    step_9(state_8).each do |state_9|
                      working_states << state_9[0]

So my question is: how do you use TDD to write a method when you don't already know the valid outputs?

If you're interested, the code's on GitHub:


  • This isn't a direct answer, but this reminds me of the comparison between the Sudoku solvers written by Peter Norvig and Ron Jeffries. Ron Jeffries' approach used classic TDD, but he never really got a good solution. Norvig, on the other hand, was able to solve it very elegantly without TDD.

    The fundamental question is: can an algorithm emerge using TDD?