Solving Impossible Problems
I’ve always been interested in enormous, impossible progamming problems.
That’s probably why I’ve steered my career in the direction of machine learning algorithms and statistical AI.
And, for those of you who followed my 30-days-30-ideas thread last summer, that’s why I was so interested in the AI-Coder business idea.
But anyhow, about those impossible problems…
Waaay back in June 1999, an eccentric British aristocrat published the Eternity Puzzle, consisting of a dodecagon broken into 209 individual pieces, each of them a unique irregular polygon. The goal of the puzzle was to arrange those pieces back into the original polygon, and the game’s creator offered a £1 million bounty for the first person to submit a valid solution.
A couple of Cambridge mathematicians developed a heuristic pruning algorithm to drastically reduce the size of the decision tree, and eighteen months after the contest was announced, they cashed their million-pound check.
I didn’t read about the puzzle until long after it had been solved, but I read several articles describing the winning algorithm, and then I hunted around the internet for a similar contest I could tackle.
No such luck.
In the middle of 2002, a colleague of mine told me about the First Annual Google Programming Contest, which had just completed. Google was providing 900,000 scraped pages from their monthly crawl, and were asking contestants to “do something cool” with the data. They offered a $10,000 prize and a trip to the Googleplex for the winner. It sounded like a fun project, and I was sorry that I missed out on it.
Likewise, in late 2003, I read an article about the Second Annual Learning Machine Challenge, which had just completed. In that competition, contestants would write programs to compete in some turn-based game (like checkers or connect-four). The tricky part was that the actual objectives and rules of the game would be kept a secret from the authors of the code. So, rather than writing an AI application capable of playing some pre-defined game, the contestants had to write an AI engine capable of learning how to win, without actually knowing how to play.
Fascinating.
The sponsoring company, Ai Research offered a $2,000 prize, as well as a trip to their research headquarters in Israel.
Unfortunately, neither Google nor Ai Research ever repeated their “annual” contests once I was aware of them, so I never got a chance to compete.
In October 2005, though, Netflix announced a new programming contest. They’ve published a hundred million records from their rating database (let’s say Joe Username gave Little Miss Sunshine five stars, but he only gave Miss Congeniality one star).
From those hundred million ratings, a machine learning algorithm can make predictions about how each user would rate any given movie not yet rated by that user. They’ve provided a benchmark (the results of their current production algorithm) and announced that the first contestant who can improve upon the predictive accuracy of that algorithm by at least 10% will win a million dollars.
Fun fun fun!!
In my actual nine-to-five job, I work on statistical machine learning algorithms to perform classifications and predictions over large data-sets using Bayesian algorithms, set-theory reduction principles, and vector space models. So the Netflix contest is exactly the kind of thing I love to tinker with.
Since the contest was announced, I’ve spent a few hours of my spare time here and there tinkering with algorithms. My implementation isn’t finished yet, but I’ve produced some very compelling intermediate results.
For example, I developed a technique for generating a similarity metric between any two movies in the database. Given the movie title Reservoir Dogs, I can tell you that the ten most similar films (in order) are:
2. Fight Club
3. The Usual Suspects
4. American Beauty
5. GoodFellas: Special Edition
6. Seven
7. Memento
8. The Silence of the Lambs
9. The Big Lebowski
10. Kill Bill: Vol. 1
For the movie Sweet Home Alabama, the ten most similar titles are:
2. Pretty Woman
3. Maid in Manhattan
4. Two Weeks Notice
5. Miss Congeniality
6. The Wedding Planner
7. Dirty Dancing
8. What Women Want
9. Runaway Bride
10. My Big Fat Greek Wedding
Using my super-secret similarity algorithm, I built a vector space model with hundreds of thousands of correlated dimensions, into which I project each of the 481,000 Netflix users. Then based on their relative proximities in vector space (calculated using vector cosines), I make predictions about how much each person will enjoy each movie.
It’s pretty cool, though it’s not quite finished yet.
As I solidify my implementation, you can expect me to write some more lengthy articles about my results. Kinda like the analysis of the question Why is Miss Congeniality so popular? that I posted to the Netflix Prize forums. Check back here for more details in the very near future.
(FYI: The Netflix project is the hobby project that I alluded to back in this post. And, yeah, I’m still also working on the VaporTrade project, as I mentioned here.
Anyhow, this morning, I read a press release announcing the publication of the Eternity II puzzle this summer.
This tricky bastard requires the puzzle-solver to arrange 256 square pieces onto a 16 by 16 grid such that their boundary colors and patterns match up with those of their neighboring pieces. This time, they’re offering a $2 million prize.
Since all of the pieces are squares, they’ll all fit next to one another in any arrangement (unlike a jigsaw puzzle, or the original Eternity puzzle, where most pieces have edges that will only interlock with certain other pieces), and each piece can be rotated into four possible positions. So, the number of unique permutations is expressed in the formula:
This can, obviously, be simplified to the more familiar formula:
Which, of course, evaluates to the number:
0016220906942793907867076793100926389379381434261416478269087586750
1694067879811828263099911002824502269863767900659808267713524471498
5216309627216978185027472968697325977719268417095542431799037585076
8358283328930609312491673026631857012057959935704204380176289796896
7913288392358349926499080367106126808955655757788055130822660925636
0610935522236371648959565075057291129730566766819588320040149109420
8054978465610034146265769803158933291635166357023361314365890301804
6594141829756341976042552093454321091341793769032610361177538560000
00000000000000000000000000000000000000000000000000000000000
…or, 1.15 x 10661, for those of you who prefer scientific notation.
I’ve got a few preliminary ideas for tackling the Eternity II, and reducing the search-tree down to a reasonable size, but I won’t be able to do much until I can get my hands on an actual copy of the puzzle in July. (But I want one NOW!!!)
Anyhow, I’m always on the lookout for new impossible problems to investigate. If any of you have found interesting programming puzzles or contests, let me know.
The bigger (and impossibler), the better!
January 27th, 2007 at 9:18 pm
Those 10 most similar lists are fantastic! That seems very valuable to me, but I would guess also very likely those online-renting companies already use or know about this algorithm, no?
January 28th, 2007 at 1:44 pm
Well, I was being a bit tongue-in-cheek when I referred to my similarity algorithm as “super-secret”. I’m sure Netflix already has its own similarity metric, but I don’t know exactly how theirs works. The technique I’m using is pretty standard, but I like to think that my algorithm has a few special non-standard tweaks that make it unique.
I’ll talk more about it in the near future, maybe even spilling the beans about my similarity algorithm, when I write more about the Netflix project in an upcoming blog post.
Glad you liked those lists :-)
February 20th, 2007 at 11:07 am
There’s also the Hutter prize.
http://prize.hutter1.net/
February 20th, 2007 at 11:36 pm
Very cool. I had never heard of the Hutter prize.
I’ll add it to my list of cool contests!!
May 11th, 2007 at 1:08 pm
Hey Benji,
Like you, I’m working on the Netflix prize, and am also at least thinking about this Eternity II one. I think the problem is not nearly so hard as your formula above suggests. According to the rules of Eternity II, the “edge” pieces all have a solid gray pattern. So there are exactly four pieces out of the 256 that can be corners and nothing else (those have two adjacent edges that are gray), and 56 pieces that will go on the edges (those all have one gray side). The remaining pieces have no gray sides and go in the middle. So those constraints dramatically reduce the number of possible valid configurations. According to some quick math it’s only:
874404596001840344334115334339810428100226026630908072783783357759260665487743920982648223387010474567330281002065941593654159181121812531818012587910788489\
144857712411871770206688520533951588761096786819331321207449836141023839090796895566300321689781601799312038965993833114777799581568067338482760990552471531\
030395749190997455198513401006689230611902315104203233421653294213798462208305658322762226383480460759634085067486272050724248245574609655485688038361841504\
52421457185879477942119986888704000000000000000000000000000000000000000000000000000000000000
or 8.744×10^559.
That’s a simpler problem by a factor of about 1×10^102 – over a google!
May 12th, 2007 at 7:26 pm
Good job, Bill. I admire your moxie!!
Actually, I’ve done some modeling of the problem, including writing a randomized puzzle-generator based on some a few details that I observed on the Eternity II website:
* There seem to be four different border shapes, and six different colors: pink, purple, yellow, blue, green, and orange. If each color can be either a foreground or a background color (but not both), then than makes a total of 120 different border styles.
* With 256 pieces, and each piece having four edges, the puzzle has a total of 1024 edges. But 64 of those edges are on the outer puzzle border, so they’re colored grey. That leaves 960 patterned borders.
* I therefore postulate that each border style will be used in eight different locations on the puzzle. (8 x 120 = 960)
Based on those assumptions, I wrote some code (in the D Programming Language, which is fun to tinker with) to generate random puzzles of different sizes. Then I can print those puzzles out on sheets of paper and cut them up to see how difficult they actually are, using only the computational machinery of my own grey matter.
(With almost any difficult software problem, I like to prototype it in my brain (and on paper) first, before writing code. That way, I can test my assumptions about the problem and see whether my solution makes pragmatic sense before taking the time to devise a clever algorithm. Often, the process of paper-prototyping suggests a reasonable algorithm.)
Anyhow, I haven’t attempted a 16×16 puzzle yet. But I’ve solved a 12×12 puzzle on my own–with no help from a computerized solver implementation–in about an hour and a half.
If my assumptions about the puzzle structure are correct, and if I can translate my grey-matter algorithm into a software implementation (and I’m sure I could), then a computerized solver would zip right through a 16×16 puzzle (which is only 77% larger than the 12×12 puzzle) in probably only a minute or two.
The reason a puzzle like this is so easy is that you can lay down the first few pieces in such a way as to constrain which pieces could *possibly* be placed next. In essence, you can paint yourself into a corner very quickly. After only a handful of pieces are on the table, you can identify the current partial solution as completely invalid and then start from scratch. And the more pieces on the table, the more constrained the remainder of the puzzle becomes.
So I think my assumptions must be flawed.
I’m now guessing that the pieces are probably printed with different border patterns on the front and back. If that’s true, then the puzzle will effectively contain 512 different pieces, but a winning solution can only contain half of those pieces (since the other half of the pieces will be invisible, facing down on your living-room table).
I haven’t done any of the math yet to figure out the relative difference in difficulty if the pieces have different border patterns on the front and back, but I think it’ll make the game very tricky.
Of course, maybe the pieces are actually just single-sided. If that’s the case, I’ll be sure to tell all of my loyal blog readers what I’ve decided to do with my $2 million.
May 14th, 2007 at 8:24 am
Hey Benji,
I hadn’t seen anything to suggest those constraints on the color and shapes for the edges (where did you see that?). If you’re right, and there are 120 edge styles, that would be helpful information in preparing a solution framework before the game is actually released. I was approaching the problem the same way as you, on paper and then in code. I just left the number of unique edge styles, size of grid, etc. as parameters for now.
There is one other piece of information in the Eternity rules that I noticed: there is one piece (piece 139), which has a specified starting position on the board, so that reduces the possibilities a little.
I’m not sure I’d agree that if there are 120 edge styles then each will be used exactly eight times. Although that’d be elegant from a symmetry perspective, I would think that establishing that requirement up front would basically mean that the inventor of the puzzle would have had to solve it just like anyone else. When the first Eternity Puzzle was created, the inventor had a zillion pieces available to him and he just picked from the pile until he filled in the dodecagon then he threw out all the other pieces. I’d suspect that the same general approach would have been taken on this version. If there are 120 edge styles (ignoring the gray border style), there would be just under 200,000,000 unique pieces in the universe of possible pieces, so he could just fill in the mosaic from that set, then throw out the 99.9999% of the pieces he didn’t need. That would be a far simpler problem than one where you must use the set of 256 pieces provided. Although requiring each edge to be used exactly eight times isn’t an impossible constraint, it would make creating the puzzle in the first place far more difficult. Maybe not quite as difficult as solving the puzzle given a fixed set of 256 pieces (since there is some flexibility in how you distribute those eight instances of each edge style among the pieces), but I don’t know for sure how big an obstacle it’d be. It certainly wouldn’t seem plausible that the inventor had to first solve the same problem he was betting $2M no one else could (at least not before he sold enough puzzles for it to not really matter).
Though I haven’t yet attempted a proof, I’d bet this problem is from the class of NP-Complete. However, like you said, as the board is filled in, I suspect that there are clever ways to very quickly decide that there are no solutions given the remaining pieces. The question is whether you can eliminate large enough numbers of possible solutions quickly enough to solve the problem before the universe suffers heat death. If you are right that there are 120 edges and each is used eight times, that would change things a lot, I think.
Cheers,
Bill
June 16th, 2007 at 12:55 pm
There are some interesting monthly puzzles at IBM Research too:
http://www.research.ibm.com/ponder/
no prizes though, just your name posted. Mostly mathematics, but often related to computer science.
July 13th, 2007 at 8:26 am
In the eternity II mailing list we have been discusing details about eternity II problem and we have been sharing ideas and implementing algorithms to solve it. We have reached the conclusion that probably the eternity II game will have 16 different borders. Solving a 16×16 board with 24 border colors can be done in less than an our. A 16×16 with 16 border colors is much much more complicated and many people think that it will be impossible to solve.
Greetings
Zerjillo
July 18th, 2007 at 1:49 am
Hi Benji !
Can you send the training data (which is quite large) to my email :anurag.sahay@in.ibm.com
July 25th, 2007 at 11:21 am
google’s latest programming contest was called Code Jam
http://www.google.com/codejam/
July 30th, 2007 at 5:31 pm
Can anione tellme how much combinations of figures and colours are in eternity II? Thank in advice.
August 1st, 2007 at 10:32 pm
It would be very easy for the original creator to make. Just draw up a completed puzzle however he liked and then cut it up. Then identify the problem make sure you can’t solve it yourself (but obviously a solution exists) and make sure the dimensions are sufficiently large to prevent brute force approaches.
August 11th, 2007 at 7:10 am
In your first formula, the one just after “So, the number of unique permutations is expressed in the formula”, k must begin by 1, not by 0.
August 13th, 2007 at 9:49 am
Good catch, Jesus.
As a computer science guy (rather than a mathematics guy), I’ve gotten used to the idea that all sequences start with zero, rather than one.
Luckily, since (4k) = 0 where k is zero, the end result of the calculation is still accurate.
September 1st, 2007 at 11:20 pm
Just a quick question (It may or may not be a dumb one) if you eliminate the edge pieces from the programming all together, and only work with a 14 x 14 grid, would this elimainate a huge percentage of possibilities? You could get all the possibilities straight up, when you get all of the 100% results possible for only the 14 x 14 grid, then add the final pieces to get the final answer?
September 7th, 2007 at 1:01 pm
That’s a good question, Lyndon.
Solving a puzzle like this can be conceptualized as a search problem within a massive decision tree. When placing the first piece on the board, you have 256 different pieces (and four rotations per piece) to choose from. Chances are, the choice is incorrect, since the puzzle has so few correct solutions.
But how long does it take to realize that the choice was incorrect? Often, you won’t know you made a bad placement until you’ve already traversed deeply into the decision tree (empirically, on this puzzle, you can often get 100 or 200 nodes deep into the decision tree before discovering that you’ve hit a dead end). To reduce the amount of wasted time searching through unproductive branches of the tree, it’s essential to discover those dead-ends as soon as possible.
One of the techniques I’m using (and most of the other puzzlers on the Eternity2 Yahoo group) is to find the most constrained positions on the board, and start trying to find valid pieces for those locations first.
As it turns out, the most constrained positions are the corners. Each corner location can support only four possible pieces. On the borders, there are only 56 possible pieces for each location. In the center of the board, there are 196 different candidate pieces for each location.
Constraints are also added to the board each time a new piece is placed, since the occupied grid cells have to have matching edges with the new pieces placed adjacent to them.
Starting in the corners, progressing through the edges, and then working on the center (always placing new pieces adjacent to existing pieces), maximized the amount of constraint on the board throughout the solver.
Eliminating the corners and borders would get rid of a lot of those constraints, so it’d be harder for the solver to know whether it was searching through an unproductive branch of the search tree.
On the other hand…
Eliminating those border constraints would make it easier to tile pieces in the center region. It’d be much easier to place each piece without all those extra constraints, and you’d fill out the puzzle grid more quickly.
Of course, you’d often create false 14×14 solutions (since many of those solutions would be impossible to combine with a legal border solution).
I’ve been working on a supervised learning technique for consuming imperfect puzzle solutions (either with mismatching edges or duplicate pieces) and using their imperfections to learn about the puzzle’s larger constraint structure. It actually could be quite useful, from this perspective.
If I had a few million 14×14 inner solutions, I might be able to study the characteristics of those false solutions, leveraging their statistical properties to better trim the global search tree toward finding a ream 16×16 solution.
I like the way you think, Lyndon :-) Are you working on the puzzle?
September 8th, 2007 at 2:09 am
You are not right. Did you read the solution of the first puzzle? Big size of the puzzle is not a guarantee that it will be more difficult than the smaller ones. You are not right for the brute force too. In a distributed environment it is not so impossible: http://www.eternity2.net/ Anyway, brute force even in a distributed computing will not be efficient enough. I am sure that the winner will use some smart eristic.
The edge pieces provide you a way to split the problem it two parts and of course to simplify it, but you still have a problem to relate both solutions (1. Solution for the border and 2. Solution from the middle part). In practice you can arrange first all possible borders and after that to arrange 14×14 by all possible ways starting from the piece 139. At the end you still will need to mach solutions form the borders with the solutions of the middle part.
Is it possible to use non-deterministic algorithms (like GA) in solving such a problem? Did some of you try to solve only borders of the puzzle? The corner pieces are 4 and can be arranged in 4! ways. After that we have 4 edges by 14 edge pieces or 56 and they can be arranged in 56! ways. To find all possible borders it should be: 4!*56!
September 20th, 2007 at 2:13 am
Hi Benji,
I purchased the puzzle a week after it was released in Australia and sat down for 4-5 hours and only got about 7 lines of pieces done. That’s only about 22 pieces done per hour doing it manually. I realised that this puzzle will only ever be solved by a computer, (unless you can pick winning lotto numbers) so I joined eternity2.net and have my computer running 24/7.
Do you have a program set up to work it out on the computer yet? I am very interested in seeing a competitor to eternity2.net.
p.s. I heard that if you join up with the eternity2 yahoo group you are automatically disqualified from the comp. Is this true?
Good luck with the algorythms.
September 20th, 2007 at 7:46 pm
I have a copy of the puzzle. There are only 22 different side markings – they’re listed on the inside front cover of the instruction manual.
September 24th, 2007 at 11:55 pm
I haven’t purchased the puzzle yet, but from what little that I can find, the unique number of permutations is approximately 256! * 4^256, however this is not needed in anyway shape or form. The puzzle can be attached mathematically and not in a brute force manner to achieve a solution in the shortest time possible.
October 8th, 2007 at 12:40 am
Need RAM? I have a machine with 4 processors and 128GB RAM waiting for interesting problems to solve. Email me…
December 9th, 2007 at 9:39 pm
Distributed computing is not likely to crack it. It is more likely to crack it with a very optimized program like the one running on my machine. Hit a depth of 212 earlier :-)
March 14th, 2008 at 10:23 am
Eternity II facts:
22 unique edge colors (plus gray, making 23 in total)
Each tile has its tile number printed on the back, so is not reversible.
There are around 1.2 million unique combinations of 4 tiles arranged in a square. I call this arrangement a ‘Quad’. Of these, 1050 quads fit in the corner; and around 43000 fit along an edge. There are 460 unique edge patterns formed by all possible quads.
This problem really is effectively impossible, and I will be very surprised indeed if anyone solves it, ever — except by trying possible board layouts at random, and being very very very lucky.
November 2nd, 2011 at 7:11 pm
tipster…
[...]benjismith.net » Blog Archive » Solving Impossible Problems[...]…