Eternity II puzzle backtracker.


hamster

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.

 

 

 

 

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.