Something Old, Something New...

Eternity II

I posted something about the Eternity II puzzle a while back. This puzzle still has not been solved (and I kind of doubt it will be, at least not without a lot of hints).

Over the past few weekends I have been revisiting my solver code and seeing what improvements I could make. It's been amazing! I've had new ideas and new approaches to take. All in all I've sped my solver up by 250%.

I run my solver in idle processing mode (so it doesn't interfere with my gaming). My old solver would get around 10 million placements a second. My new one gets 25 million. When I compile it for pure speed (i.e. no pretty pictures of its current state and a bump of processor priority) I'm closer to 30 million. And that number is per core!

EVE Blue

In my last post I mentioned I've been working on my own Industry program for EVE. This has been progressing rather well. I've named it simply Blue (for blueprint).

I've pulled and integrated the last EVE data dump. My character editor will download character stats with EVE API. I've also got integration to EVE Central.

After combining all this information and also information on station pricing (i.e. manufacturing, research) I can generate an array of reporting. For one of my reports I feed it a character and a fictitious ML and PL, and it gives me numbers on what blueprints may be worth buying for a particular region. Of course all this information needs to be taken with a grain of salt and researched in game before any action taken.

Here is a picture of my report here but I can't get blogger to show it full size... you will need to click it to read it proper.



I need to integrate sales volume from the market window into this program somehow too. This would give me more accurate data.

How to Win $2 Million Dollars

Its simple, just be the first to complete this 256 piece puzzle before the end of next year. Easy, right? Looks can be deceiving!

I have been interested in this line of puzzles ever since I received Eternity I for Christmas way back in 1999. It presented a fun programming problem to me, and I enjoyed tackling the various methods of programmatically solving it. When the puzzle was solved (by two mathematicians) I kept an eye out for news of a second puzzle.

And then I found that news, at the beginning of this year. There were some details on the format of the puzzle (i.e. square pieces, 8x8 board) out there... enough to get me a head start on a solver for this puzzle. I found my old eternity newsgroup, now resurrected as a place to discuss the new puzzle. Discussions were already taking place, a lot of which were based on expected number of solutions, piece tileablity, things that were very important to the previous puzzle. I completed my solver and anxiously awaited the release.

I had my puzzle and the two hint puzzles shipped to me from England. My wife started solving the two hint puzzles by hand while I encoded the 256 pieces of the main puzzle into a file. How deceivingly simple the two clue puzzles were... she had them both solved in less than an hour. And this was about how long it took me to finish encoding. I let loose my solver (an instance on each of my computers) and watched it. It really was fascinating to watch... it would place a bunch of pieces... remove some... place some again... really neat stuff. As a programmer, I really enjoy seeing things I have spent long hours on work the way they should. I had really high hopes.

But alas, this puzzle is a lot more difficult... the search space is simply to vast. My best "partial" solution to date was discovered last weekend. A 216 piece partial, the silhouette of which can be seen here. I cannot show the actual picture due to copyright issues. Unfortunately my first generation of solver did not save off partial solutions... I'll never know if I had had something better in the past.

My first generation solver placed tiles one at a time. Last month I finalized my second generation solver (running now) that places tiles via a 2x2 "super" tile. I pre-create all the 2x2 tile combinations when the solver starts up, so my puzzle is effectively an 8x8 board but with millions of pieces. My third generation solver will handle 2x4 tiles... sort of. I did some math and if I wanted to pre-create all the 2x4 "super" tiles ahead of time I would need something like 20 terra bytes of storage to save them all!

So I decided to do something a bit different here and only generate the top and bottom edge "super" tiles for only around 25 gigs of storage. Since the storage requirements are large, I will need to save them to disk instead of to memory. This will reduce the speed of my solver somewhat but it may be worth it since I will be placing 8 pieces at a time. I have yet to complete this solver so it should be interesting.