GPU algorithm might help Eternity II puzzle solvers

Eternity II is a puzzle with 256 pieces which need to be placed correctly on a 16x16 board. There is a price of 2 million dollars, for the submitter of the correct solution. To get an idea, you can try a much simpler online demo here. Watch also the presentation with Lucy Pinder as youtube video.

GPU delivers a cost-free plugin which might help puzzle solvers. If a puzzle solver manages to find a solution with the help of GPU, the price will be entirely for the solver, the GPU Team will not claim any money. To get the software, one should download a GPU (at least version 0.948).

After getting the software, one needs to buy the puzzle and to create a particular e2pieces.txt file, as done with the BOINC Eternity II project, which was shutdown at the end of 2007. Instructions to create the file e2pieces.txt are here. Beginning from version 0.9494 (Tools -> Autoupdate to latest version will get it), GPU also supports the e2hints.txt file, containing hints, and which should be placed in the same directory as e2pieces.txt. To get the hints, you should buy and solve the complementary 6x6 and 6x12 puzzles, and then submit the solution to the official Eternity webpage. The hints are not required, but might help in finding a solution. Please note that for legal reasons the GPU Team cannot distribute any piece definition file, nor give information about the hints.

The file e2pieces.txt (and e2hints.txt if you have one) should now be placed somewhere on your computer, e.g. at the root of the drive C:\. Now from a running GPU choose Tools->Console frontend and type the following command in the edit box at the top:

Check the 'local' checkbox and press the 'Send to GPU' button. Check the 'Resend job each 2 minutes' as well. GPU will now show under Tabs -> GPU Engine -> Jobs that it is crunching the puzzle beginning from a random position. After half an hour on a Core Duo, or one hour on an older AMD Athlon, the plugin will report the maximum number of placed pieces on the board (typically from 80 to 217 pieces)

The output can be seen on the screensaver (for entertainment purposes only) and into four separate files: Go to the GPU\plugins\output directory. The file eternity_log.txt shows the current computation going on, the file eternity_current_best.txt shows the current best board in the ongoing computation. The file eternity_best_depth.txt shows the best seen board with the maximum number of placed pieces. If a solution is found, the file eternity_solution.txt will be created. Instead of 256, the GPU plugin will report a 99999, to signal that it found the solution.

The algorithm has 5 different fill strategies: left to right, spyral inward, spyral outward and mixed spyral. A divide and conquer strategy is enabled if you have hints, the board is then splitted in four rectangles. The rectangles which contain the hints are then splitted in four additional subrectangles. Well, please keep in mind that it is not a true divide and conquer, as the partitions still depend from the other's borders.

Beginning from version 0.9504 (downloadable with Tools->Autoupdate to latest version), the plugin also supports milestones as follows. When the plugin computes, it stores each 2-3 minutes a milestone under plugins/output/eternity_milestone.txt. The milestone is stored in a human readable format and can be easily modified manually. In the milestone file, the pieces, their rotation and the path to the solution are stored. Once the eternity_milestone.txt file exists, it is possible to restart the computation by calling the eternity plugin without parameters: just send:

eternity_solver

to the GPU as you did before with the Console Frontend. The computation will restart from the milestone point then.

Source code for the brute force backtracker algorithm is in Delphi and can be seen here.

The algorithm is able to solve the 4x4 puzzle which is online on the eternity page, the 6x6 hint in one second, and the 6x12 hint in about one minute on a 1GHz processor. Assuming you created a hint1.txt and hint2.txt file, the GPU command will then be:

6, 6, 'C:\hint1.txt', eternity_solver
12, 6, 'C:\hint2.txt', eternity_solver

Even if the GPU plugin might never report a 99999, the above mentioned text files might help solvers in finding a solution, if they use the proposed partial solutions as start points.

For people interested in Theoretical Informatics, an interesting paper is the following:

In it, the authors talk about the various degrees of complexity of jigsaw puzzles, polyomino packing puzzles (Eternity), and edge matching puzzles (Eternity II) (link taken from this blog). The paper shows that there are polynomial reductions between these types of problems. As the first is NP complete, the other two are as well, because a reduction exists.

The GPU team is also searching for a solution and therefore we are interested in feedback. Please report your wishes, problems and support requests to the GPU mailing list.