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

Question

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:

• Tests: https://github.com/mattdsteele/scramblesquares-solver/blob/master/golf-creator-spec.rb
• Production code: https://github.com/mattdsteele/scramblesquares-solver/blob/master/game.rb