Speeding up a program solving Icosoku

Question

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?

Answer 1

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) :-)

Answer 2

Another technique that may be suitable for your problem is backtracking. It is often used for solving puzzles such as 8 queens problem, sudoku, etc.

Answer 3

The Rubik cube is a different beast, but the techniques to study it might come handy. A look at the mathematics (group theory) behind its solution is Joyner's "Mathematics of the Rubik's Cube", the site http://permutationpuzzles.org with its links might also be of help.

Answer 4

Heuristics may help. Probably you can arrange the nodes in groups of three for example one node may be conformed by the numbers 12,10,5 which sums 27, sort all of them like this (example) 12,10,5=27 12,7,5=24 10,9,4=23... and so on.

In the other hand arrange the sum of the dots from the triangles... 3,3,3=9 first in list 3,3,2=8 (i don't know if this configuration of dots exists (doesn't matter) ... 0,0,0 at the and

1.- then you go recursive putting first, the higher triangle in the higher node. 2.- if doesn't help rotate in the same node 3.- if doesn't help, permute triangle with the next higher node, (which may have the next higher triangle).