hamster

Eternity II puzzle backtracker.

Recommended Posts

Just dropping by to say I've finished an FPGA-based solver for Eternity II style tile matching puzzles. (see http://en.wikipedia.org/wiki/Eternity_II_puzzle).

 

eternity-ii_main.jpeg

 

It runs on the Spartan 6 LX9 @ 200 MHz with a four-stage pipeline, allowing four 'threads' to share the logic resources and work on the same puzzle at any time.

 

Even better than that, I can fit four of these four stage pipelines in the LX9, giving 16 threads that each can place up to 50 M tiles per second. If I use distribututed RAM for some of the smaller RAM instances I can fit 12 threads @ but at a slower clock of 160MHz. Each thread is about 10% the speed of a highly optimised software solver running on a 3.5GHz i7 core, making the total LX9 about as fast as a single i7 core.

 

However, it is very, very unlikely that it will ever find a solution to the puzzle - even at > 100 million search nodes per second it takes a very long time to brute-force the the estimated 10^52 search nodes.

 

 

 

 

 

 

Share this post


Link to post
Share on other sites

TIme has expired. Working on Eternity 2 was what got me started looking at FPGAs, I always thought that it would be a dead end, but I now aim aiming 48 threads running at 200MHz on a LX9 - If it works it it will do as much work per second as an eigth i7 cores.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now