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 = Cards.new
  card = c.cards[0]
  card.top.should == :CT
  card.bottom.should == :WB
  card.left.should == :MT
  card.right.should == :BT
end

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]
                    end
                  end
                end
              end
            end
          end
        end
      end
    end

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:

Solution

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?