Quote:Original post by Uthman
anyhow, im also planning on building a (scalable) solver for the puzzle this comming week before school break is over.
How do you define scalable? Polynomial-time? I think that is impossible.
Quote:would any of you like to benchmark your solvers against each other to see how we all stack up? we can define a few board sizes, {1,2,4,8,16,32} along with different numbers of colors {1,2,4,8} and produce some nice charts to compare our algorithms. i guess it would be a good idea to post what language we developed it in as well as benchmarking machine stats.
I think that the asymptotic growth as a function of board size would be much more interesting. I doubt a tractable solver is possible. What will most likely solve the puzzle is a "solver" based on probability, which may have horrible worst-case performance, but a decent average-case performance.
How much micro-optimizations you can do and how much processing power you throw at it barely matters. What matters is the difference between solving this in polynomial time or solving this in double exponential time.
IIRC the previous solvers were mathematicians who used a very sophisticated back-tracking search starting with a human-generated partial solution. Yet they had to let it run for over 7 months on two computers (I believe that was the time, but I'm not completely sure). From what I have heard, this puzzle should be significantly harder to solve.
