[Solved]: Speeding up a program solving Icosoku

Problem Detail: 

I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The pins are printed with the numbers from 1 to 12, and the triangular tiles have up to three dots in each of their corners. The object of the game is, for any arrangement of the pins, to choose the positions and orientations of the triangles so that the total number of dots on the five joining corners of each pin equals the number of the pin."

I created a computer program which solves this puzzle by randomly choosing any two triangular tiles and then exchanging them (giving each tile a random orientation) if and only if the total discrepency (which can be measured in various ways) between each number on the pins and the total number of dots on the five joining corners of each pin decreases. But I have found that it takes hundreds or even thousands of iterations to finally get a solution for most initial configurations. I would like my program to take less time. Any suggestions?

Asked By : Craig Feinstein

Answered By : Vor

I suggest you to look at other (completely different) approaches, too:

1. write a program that given an Icosoku configuration outputs a SAT instance that can be solved using a SAT solver;
2. (re)write your program using a constraint programming language (for example STP) or write a program that given an Icosoku configuration outputs an intermediate source code for the constraint solver;
3. (re)write your solver using a SAT library (for example Choco for Java).

... perhaps you'll find them interesting (and faster) :-)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10216