> An interesting observation on the difficulty of the puzzle,
> but there is one factor in our favour, there is more than
> solution.

I'd actually be interested in starting a side betting pool
on whether more than one solution exists (not counting
reflections and rotations on the board, obviously). Assuming
there are any takers for the "unique" side (I'm not sure which
I believe at the moment).

>> Although visually very nice (I hang a printout of the 150
>> piece attempt on my monitor) I think that mathematically
>> this result is not very interesting.

I said the same thing to Ed Pegg in a private e-mail. My
experimentation leads me to believe this is pretty easy,
actually. And what you are left with, as Patrick Hamlyn
has shown, is a bunch of non-fitting pieces.

Hmm, I wonder if it would be worth using as a heuristic
the "tileability" of the remaining pieces? This might
be particularly effective with a solution that tries to
place pieces along an outside perimeter.

> > This all sounds nice, but it is only useful if the number
> > of childs per node is limited to 1. If the problem is limited
> > to say 2^200, it still takes a few big bangs to solve it.

Depressing, isn't it? I am beginning to believe that a
depth-first search (DFS) just won't work for this puzzle.
And, of course, breadth-first (BFS) is clearly impossible.
I'm planning to modify my program to do a form of beam search,
which is a hybrid of DFS and BFS. It basically keeps an
"open" list of finite size. I plan to invent some heuristics
that let me pick the nodes that I expand, at the expense of
bypassing possible solutions. If I can exhaustively search
even a small part of the tree, I can progressively relax my
heuristics. If my heuristics are good guesses, then I solve
the problem in finite time.

>> Another idea I spend many happy hours thinking about is the
>> concept of 'conversion'. With this I mean studying problems
>> that are in some way similar to this problem, then converting
>> it to that 'space', solving it, and converting it back to this
>> one. Some classic problems were cracked in this way, like
>> Fermat's Last Theorem and Ramanujan's Pi Fomula.

The computer scientist in me says that this is a nice thought,
but that it won't help. This problem is clearly NP-complete
and will be no matter how you transform it. While you can
make the representation faster to compute, you can't dodge
the fundamental complexity of the problem.

I did spend a bit of time thinking about a representation that
would be quick to compute on. I came up with something that
eliminates the parity issue (by assuming everything goes with
the grain) and is very fast for the computer to compute whether
a piece fits or not. I'm sure there are other good representations.

>> The discussion about GA (Genetic Algorithms) and SA (Simmulated
>> Annealing) I don't believe too much in myself. These methods
>> assume that solutions that are 'almost' or 99% correct are
>> acceptable. The problem is that 'almost' does not exist in this
>> problem.

The problem is less that these things tend to find "almost"
solutions and more that there are many, many "almost" solutions
that are nowhere near the 100% correct solution. If the fitness
landscape was better-behaved, the GA or SA might have a chance.

--james