# Speeding up a program solving Icosoku

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?

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

• It is probably hard to beat the first approach :-) – Juho Mar 3 '13 at 20:27
• I would think all of these approaches would be much slower than my approach, since they are not specialized. Why do you think they would be faster? – Craig Feinstein Mar 4 '13 at 16:10
• @CraigFeinstein: because SAT solvers are specialized to solve (rather complex practical problems) VERY fast :-) ... I bet that they can solve an Icosoku puzzle in a few milliseconds. If you post the tile configurations of your Icosoku (the dot configuration of each triangle) ; I can quickly make a Java program to test the solving speed using approach 3 – Vor Mar 4 '13 at 16:32
• The dot configurations (note that there are repeats) of each triangle are as follows:(0,0,0),(0,0,1),(0,0,3),(0,0,2),(0,1,1),(0,1,2),(0,1,2),(0,1,2),(1,1,1),(0,2,1),(0,2,1),(0,2,1),(1,2,3),(1,2,3),(3,2,1),(3,2,1),(2,2,2),(0,2,2),(0,3,3),(3,3,3) – Craig Feinstein Mar 4 '13 at 20:49
• @CraigFeinstein: I wrote a small Java+Choco program, but it doesn't show any solution. Are you sure that the dot configurations are correct (from top, clockwise)? – Vor Mar 5 '13 at 10:27

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.

• My approach is sort of a backtracking approach. Anytime an exchange makes things worse, the program backtracks by not using it. – Craig Feinstein Mar 4 '13 at 16:12

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.

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