Let's start with a recent post by Brendan Owen to the egroups Eternity mailing list.

Brendan wrote:

> I think so, the basic idea behind the solution process was outlined here.

>

> - Finding out what endgame shapes tend to be easier.

> - Dividing the board into two regions.

> - Estimating the needed size of the end game.

> - Finding the easy and hard pieces by randomly tiling the endgame or another

> related shape.

> - Using a limited BFS to tile the start game keeping easy pieces.

> - Speed increases ie CCells, void checks, etc.

> - Avoiding ATG searches.

> - Showing parity is practically useless for this puzzle.

> - Estimating the number of solutions.

> - etc.

This pretty much describes our method at the top level, except that we do not divide the board into two regions.

Here is one way to think of tiling. For an algorithm which keeps trying to place pieces we can pretend there is a typical branching factor (i.e., typical number of ways of adding a piece to the current position) which depends only on the number of placed pieces, and so you get a graph like the above one. `A' is meant to be the area above the x-axis and below the curve, and `B' is the area below the x-axis and above the curve. So the expected number of solutions is exp(A-B), which is independent of the algorithm used, although A and B can individually depend on the algorithm. In general the better the algorithm, the closer the curve is to the x-axis and the smaller A and B are.

If A<B then the problem is overconstrained and we would expect
no solutions unless someone planted one, in which case there would be
one solution and we would be aiming at finding *the* solution.
In this case I guess the only method would be some kind of an
exhaustive search. The running time would be about exp(A) because
after `p' pieces are placed the search will quickly reach a point
where it can't branch any further. Making the algorithm branch on the
most constrained sites first will reduce A and so make it quicker.

If A>B then the problem is underconstrained and you have extra freedom before you reach the point p. Clearly we want to use this freedom to arrive at the best possible situation when we hit the point p. This is done by getting rid of the least tilable pieces first and leaving as good a board shape as possible. We will have to arrive at the point p about exp(B) times before we expect a solution. As before, after arriving at p the search will quickly terminate. We should spend some effort in getting to p in a good state, but presumably this effort will be comparable with the time taken to exhaust from p, so in all the algorithm will take about exp(B) time to find a solution.

For the full Eternity board we are in the second case with
A>>B. We have estimated there are about 10^{95}
solutions to eternity, though this is very rough. Others have put the
figure at 10^{120} and they may well be right. There is some
critical boardsize, c, for which we would expect 1 (unplanted)
solution. We did estimate this c some time ago but I can't remember
our conclusion. Maybe it was about 70 for a typical set of
pieces. Whatever it is, it probably represents the most difficult size
to solve. So the more pieces you add after c, the easier the puzzle
gets which may seem a bit surprising. Given a larger boardsize c+r,
one has freedom to place the first r pieces in many different
ways. Presumably it is easy to find a way of placing them (choosing
bad pieces) such that the resulting size c problem is easier than
typical. Of course that is how you solve Eternity itself. Here is a
plausibility argument which shows why you might expect there to be a
critical size c. The number of ways of arranging the n pieces (not
worrying about small overlaps) is something like n!a^{n} for
some constant a, and the number of constraints these have to satisfy
to actually fit is proportional to the total perimeter of the shapes
which is proportional to n. So you expect something like
n!(a/b)^{n} solutions for some constants a and b
(a/b<1). For large enough n this will be greater than 1. I think
Brendan Owen has said this before in a different way.

Before we took on Eternity proper, we worked a bit on making a solver - i.e., a program that exhaustively searches smaller shapes. To make a solver, you need to make the program decide which site to tile at any stage and whether or not to terminate work on a partial when it can be proved that it is/will be stuck (I think this is called void checking here on this list). Our void checking is quite strong: after the placement of any piece, we make sure that all length 11 subpaths of the boundary are valid according to the above-mentioned lookup table. In addition to this, when we decide which site to tile, we calculate how constrained every site is according to an n-ply search (n is adjustable, but typically only 1 or 2). So if there is any site where you can't place n pieces leaving a boundary which passes the lookup table test then the partial will be rejected. We think it is generally important to tile the most constrained site, but in some cases it is clearly a waste of time and even a simple fixed order is better, so we have some idea how we might improve our method of choosing sites. For hex9 we find the 73752 solutions in about 25 seconds (with no special symmetry code), which at the time we wrote it (c. Feb 2000) was quite a bit faster than other publicised solvers. On other benchmarks like hex36 we were also quite a lot faster. But on one of the latest benchmarks - milestone 32 - our solver is 20 times slower than `Soliver'. On the other hand I think milestone 32 is particularly suited to a fixed order because it is long and thin (so there is an obvious good order) and there is no altitude-type boundary.

One way of seeing why we want to choose the most constrained site
first (assuming there is no cost in finding out what it is) is
this. Pretend that the branching factor when there are n pieces in
place is always b_{n}. Then the number of nodes searched is
N=1+b_{0}(1+b_{1}(1+b_{2}(1+...))). If
b_{n} > b_{n+1} then you reduce N by swapping
b_{n} and b_{n+1}, so you get the smallest N by
putting b_{0}, b_{1},... in increasing order.

What is the branching factor at a particular site? You could say it is the number of legal placements that cover that site. But some of those placements may lead immediately to dead ends (e.g., 30 degree angles), so it seems reasonable to discard these and count just the placements that don't lead to immediate impossibilities. But this treats placements which have only one possible followup move the same as placements which have many followup moves. Wouldn't a more refined measure treat the former with less weight than the latter? Well maybe. If you took this to the extreme then your `measure' would end up being how many global solutions there were, so you have to take into account how long it actually takes to calculate the local information to get a meaningful balance. If you expect to do say 10^10 nodes of work underneath the current node, then it is presumably worth choosing the site to branch on with quite a lot of care, but if you only expect 10^5 nodes then you can't afford to waste too much time choosing the site.

The above waffle was leading to the idea of a 2-ply version of the local branching factor (which is not just the sum over local placements of followup placements). Our solver decides on an appropriate n, works out an n-ply version of the local branching factor at each site, and then branches on the site with the smallest one. However it seems that for the kind of length exhaust we typically did (of the order of minutes), it is rarely worth using more than the ordinary n=1, so this method does not gain all that much in the cases in which we used it. But because I like the n-ply local branching factor, I'm include a description of it here. Perhaps it might even be useful for other search problems.

We chose to extrapolate by using extra pieces, i.e., exhausting
regions using more pieces than fit in the region. This method, and the
modeling process that followed, underwent many changes, but we'll
describe our first version of it here. To begin with we worked with
regions of size 24 (obtained in some fairly ad hoc way) and then
replaced the 24 pieces in remaining hand with 90 random pieces. The
advantage of using extra pieces is that we expect to get solutions,
but not to take too long to exhaust. With these numbers we are sort of
getting (90 choose 24)/4=about 10^{21} times more solutions
(fake) at the cost of a much smaller increase in running time. (The
1/4 comes in because there is a 1/4 chance that a random set of the 90
pieces will have the right parity.) Unfortunately these random pieces
are not really comparable to the 24 pieces that were there
naturally. For example, at any site on the boundary there will be a
piece from the original 24 which fits there (this follows from our
most constrained site choice), but there may or may not be a piece
from the 90 random pieces which fits there, so for this and other
reasons the random pieces don't have the same distribution as the
original pieces. This illustrates how the extrapolation process may
lead to wrong results. We did have some refinements in our later
versions to reduce this problem, and some others to monitor it.

HTML version

(If this comes out as gibberish then try one of the lower two.)

PDF version

(This is likely to work if you use Windows, and may work anyway.)

Postscript version

(This is likely to work if you're using a version of Unix.
You may need to use ghostview to read it.)

These are the parameters (l

probs2

These are the parameters resulting from a modeling process which
should be more accurate when you use it on a good (tilable) set of pieces (which
is what happens in practice).

Here is how to use the parameters in probs1 or probs2. Given a region of size 24 with one simple boundary, work out

c_{0}=the number of corners (changes in direction) in the boundary,

c_{1}=the number of altitudes in the boundary, and

c_{2}=the number of half-equilateral triangle edges in the boundary.

(For example, piece 1 has c_{0}=6, c_{1}=2, c_{2}=12)

Then for each of the 24 available pieces, add the number in the row of
the file corresponding to that piece. Add this to
m_{0}c_{0}+m_{1}c_{1}+m_{2}c_{2}
and call the result x. The probability estimate is then 8exp(x).

When you've decided on the model parameters for all sizes greater than 24, you have a score for a node. (A `node' is just a situation - a region together with the remaining unused pieces.) The breadth-first-search (BFS) method we used then works like this. You start off with an empty board and all 209 pieces unused. This is the top node (level 0). You then decide on the most constrained site and generate all the piece placements which tile that site. You then take the top 10 scoring nodes of these, and throw away the others and also throw away the top node (though you have to remember your family history if you want to be able to resconstruct a solution). This gives you 10 level 1 nodes. At the next stage you generate all of the children of all of the level 1 nodes, take the 10 most highly scoring according to the level 2 score and throw away the rest, and so on. You can improve the performance by doing extra lookahead and increasing 10 (the `width'). We were using lookahead about 2 (but with quite strong `void checking') and width about 10000 on the run that found the solution, although we have since tried widths up to 1000000 and these are better. This method was described by Patrick Hamlyn on the mailing list a long time ago and is a very nice method. I wonder if we are using it slightly differently from him, since he said he had difficulty persuading his program not to squander the good pieces, which shouldn't be a problem using absolute scores.

At some point (e.g., level 178) one should switch from a BFS to just
doing an exhaustive search on all of the existing nodes. Actually, as
you might expect, there are slightly better methods that make a
smoother transition doing pruned searches, but I think just switching
to an exhaustive search at the best point is not all that bad.