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

Answer 1

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?

Answer 2

From the puzzle website:

The object of the Scramble Squares® puzzle game is to arrange the nine colorfully illustrated square pieces into a 12" x 12" square so that the realistic graphics on the pieces' edges match perfectly to form a completed design in every direction.

So one of the first things I would look for is a test of whether two tiles, in a particular arrangement, match one another. This is with regard to your question of validity. Without that method working correctly, you can't evaluate whether the puzzle has been solved. That seems like a nice starting point, a nice bite-sized piece toward the full solution. It's not an algorithm yet, of course.

Once match() is working, where do we go from here? Well, an obvious solution is brute force: from the set of all possible arrangements of the tiles within the grid, reject those where any two adjacent tiles don't match. That's an algorithm, of sorts, and it's pretty certain to work (although in many puzzles the heat death of the universe occurs before a solution).

How about collecting the set of all pairs of tiles that match along a given edge (LTRB)? Could you get from there to a solution, quicker? Certainly you can test it (and test-drive it) easily enough.

The tests are unlikely to give you an algorithm, but they can help you to think about algorithms, and of course they can make validating your approach easier.

Answer 3

dunno if this "answers" the question either

analysis of the "puzzle"

9 tiles
each has 4 sides
each tile has half a pattern / picture

BRUTE FORCE APPROACH

to solve this problem you need to generate 9! combinations ( 9 tiles X 8 tiles X 7 tiles... )

limited by the number of matching sides to the current tile(s) already in place

CONSIDERED APPROACH

Q How many sides are different? IE how many matches are there?

therefore 9 X 4 = 36 sides / 2 ( since each side "must" match at least 1 other side )
otherwise its an uncompleteable puzzle
NOTE: at least 12 must match "correctly" for a 3 X 3 puzzle

label each matching side of a tile using a unique letter

then build a table holding each tile
you will need 4 entries into the table for each tile
4 sides ( corners ) hence 4 combinations
if you sort the table by side and INDEX into the table

side,tile_number
ABcd tile_1
BCda tile_1
CDab tile_1
DAbc tile_1

using the table should speed things up
since you should only need to match 1 or 2 sides at most
this limits the amount of NON PRODUCTIVE tile placing it has to do

depending on the design of the pattern / picture
there are 3 combinations ( orientations ) since each tile can be placed using 3 orientations
- the same ( multiple copies of the same tile )
- reflection
- rotation

God help us if they decide to make life very difficult
by putting similar patterns / pictures on the other side that also need to match
OR even making the tiles into cubes and matching 6 sides!!!

Using TDD,
you would write tests and then code to solve each small part of the problem,
as outlined above and write more tests and code to solve the whole problem

NO its not easy, you need to sit and write tests and code to practice

NOTE: this is a variation of the map colouring problem
http://en.wikipedia.org/wiki/Four_color_theorem