> 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 1095 solutions to eternity, though this is very rough. Others have put the figure at 10120 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!an 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 bn. Then the number of nodes searched is N=1+b0(1+b1(1+b2(1+...))). If bn > bn+1 then you reduce N by swapping bn and bn+1, so you get the smallest N by putting b0, b1,... 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 1021 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.
(If this comes out as gibberish then try one of the lower two.)
(This is likely to work if you use Windows, and may work anyway.)
(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 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
c0=the number of corners (changes in direction) in the boundary,
c1=the number of altitudes in the boundary, and
c2=the number of half-equilateral triangle edges in the boundary.
(For example, piece 1 has c0=6, c1=2, c2=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 m0c0+m1c1+m2c2 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.