vàp Puzzles

Once upon a time, there was a beautiful prince... No, let's start again. Once upon a time, there was a former adviser to Margaret Thatcher who designed a puzzle so difficult that it would take anybody many years (one million billion, according to his calculations) to solve it. So he offered a prize of one million pounds for the first one to solve it. Unfortunately, his estimates were somewhat wrong (what a surprise…), and it took barely one year for some smart mathematicians to come up with a solution.

and its siblings … but in spite of all that stuff, the puzzle was (and still is, minus the prize) a lot of fun, and it had four companions, one online (now gone) and the other three for sale.

The first two, Meteor featuring 10 pieces (2098 solutions) and Delta with 14 pieces (1494 solutions), can be solved rather quickly. They both use basic grids that are made of only one shape (hexagon or triangle), so that sliding a piece can be done regardless of the position (in integer grid steps, of course). The third one, Heart (20 pieces, 50 solutions), is a bit trickier, because it uses a composite grid (two squares and two rhombi).
The Meteor and Delta programs show only the solutions. The arrows modify the time (in seconds) during which each solution is displayed. Heart shows all the moves, and it is possible to change the delay between them.

There is a working program for Eternity too, but since the number of possible combinations is thought to be somewhere between 10⁴⁰⁰ and 10⁶⁰⁰, it can take a while to reach a solution. The best I have achieved so far is 190 pieces (out of 209).
The programs have been written with Delphi, which means that they will only run under Windows. All have been compiled to run with minimum priority. I should learn Java sometime, so that they can work on other platforms too.

And now for something completely different. Gone are the shapes. 256 square pieces to fit in a 16 by 16 grid. Sounds easy. Alas, the pieces are patterned, and adjacent ones have to fit. Deadline end 2008 for a prize that has doubled : two million. But they went from GBP to USD… which must have looked like a great idea before the pound collapsed. No doubt the prize for some future scion will be in Ecuadorian sucre.

Pentominoes Of course, it started long ago with the mother of them all. I do not post my programs for this, as there are already good ones in Java. The applet by David Eck is my favorite one, maybe because the algorithm uses the exact same logic (add one border of outer cells permanently blocked, linear array for cell addressing) I had developed when I first solved the 6×10 board (in Basic on an Atari; it took over 11 hours to get the first solution…). Or maybe there are not that many ways to tackle he problem. Anyway, practically all online solvers use David Eck's code. There is also a nice page showing all solutions for the 6×10, 5×12, 4×15 and 3×20 boards, and the rest of the site is a treasure trove of data on similar objects. Also worth a visit, the MathWorld page.
If you prefer to solve it by yourself, there is an application for the Palm OS that allows you to do just that. By the way, it is not that difficult to solve the 3×20 once you notice that some pieces can only be placed at specific locations.

As Stuart Coffin puts it, this set of 35 pieces is already too large to be enjoyable. Moreover, they cannot make a rectangle, since 11 pieces are not balanced (see fig. 30). They will only fill a pattern with an excess of 2, 6, 10, 14, 18 or 22 squares of one parity. The simplest such figure is a right triangle whose short sides are both 20 squares long (excess 10). Still, it is no fun at all to (try to) do it by hand.
Using a program, even if the waiting time between solutions is rather short, the general progress is awfully slow: With the pieces numbered as in Sear's Multipuzzle, the 17^th piece has not changed yet after more than 22000 solutions. This means that the total number of solutions will be rather high…

The site of Aad van de Wetering offers (among others) FlatPoly, an utterly friendly application for creating and solving this kind of puzzles.