Joe’s Pyramid

Yesterday, while reading the last issue of the NewScientist, I came across the following very cute riddle:

Lazy, I asked myself if it were possible to write {10} lines long Python code to solve this innocent looking enigma. The whole pyramid is entirely determined by the {6} numbers lying at the bottom, and each one of them is an integer between {1} and {99}: these numbers must be different so that there are at most {\binom{99}{6} \approx 1.1 \times 10^9} possibilities to test! Brute force won’t work my friend!

When stupid brute force does not work, one can still try annealing/probabilist methods: this works pretty well for Sudoku (which is NP-hard) as this is brilliantly described here and there. The principle is simple: if one can find a good energy function {E:\{1, \ldots, 99\}^6 \rightarrow \mathbb{R}} such that a solution to the problem corresponds to a low energy configuration, one can do MCMC-simulating annealing-etc on the target distribution

\displaystyle \pi(\text{configuration}) \propto e^{-\beta \cdot E(\text{configuration})}.

The issue is that it might be very difficult to choose a sensible energy function {E(\cdot)}. Foolishly, I first tried the following energy function, and then ran a random walk Metropolis algorithm with {\pi} as target probability:

\displaystyle  \pi(\text{configuration}) \propto e^{\beta \cdot {\text{Height}}(\text{configuration})}

where {\text{Height}(\text{configuration})} is the numbers of levels that one can fill, starting from the bottom, without encountering any problem {i.e} no repetition and no number greater than {100}. With different values of {\beta} and letting run the algorithm for a few millions iterations ({5} min on my crappy laptop), one can easily produce configurations that are {5}-levels high: but the algorithm never found any real solution {i.e} a configuration with height equal to {6}.

Now I am curious wether this is possible to produce a non-stupid energy function {E(\cdot)} so that this riddle is solvable in a reasonable amount of time by standard MCMC – annealing methods.

As a conclusion, I should mention that with a pen and a cup of coffee, one can easily find a solution: I will not spoil the fun, but just say that the configuration space is not that big if one think more carefully about it…

Challenge – Announcement

Have you already heard about the 17×17 Challenge ? It all started 7 months ago, and still no solution has been found. I have the feeling though that no really serious attempt at solving the problem has been done, even if very encouraging results have been found. It could be very interesting to keep track of the progress made so that results will be published here. Send what you have reached so far!

In the next few weeks, I will try to write about the Monte Carlo approaches described in the excellent book “Monte Carlo Strategies in Scientific Computing” by Jun Liu: I do not think that one can easily solve the problem with a direct implementation of these methods, but I want to know more about it. These are all more or less Markov Chain Monte Carlo Methods: I have tried the “parallel tempering” method, which gives results that are not that bad, and was planning to check the “flat histogram” method. “Simulated annealing” methods have succesfully been used to solve the Sudoku problem though: see Christian Robert blog for example. I am also planning to continue my reading of the fascinating book “Information, Physics, and Computation” by Marc Mezard: methods described in this book (belief propagation, k-SAT problem, etc…) are more adapted to the 17×17 challenge I think, and I am quite optimistic about it.

 

17x17_4_anonymous

Best Solution so far, by Rohan Puttagunta: only 4 monochromatic rectangles!

Read also here,here,here,here and there – and have a try with this on-line simulator !