My US$2 million quest

Monday, November 26, 2007, 01:45 PM - Technology

I'm currently writing an application to solve Eternity II puzzle. For those who dont know what Eternity II puzzle is, here is the website.
So far my application can solve the 4x4 puzzle in about 15 ms.

For a 4x4 puzzle, there are about 16! x 4^16 combinations, which according to windows calculator, it comes to 89,862,698,310,039,502,848,000 combinations. So to pick up one solution in that haystack in 15ms, I cant feel any happier :). Still, I can guarantee that my application wont even run to completion on the original puzzle (16x16).

For a 16x16 puzzle, there are 256! x 4^(256) combinations. Again, according to windows calculator, that is roughly 1.151 x 10^(661). What do you call that? 10^661(more than the number of atoms in the universe!). Lol. My application will certainly throw StackOverflowError. :P

There are a couple of strategy I have in mind - which of course I wont reveal here (yet). :)