3

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?

Raphael
  • 72,336
  • 29
  • 179
  • 389
Craig Feinstein
  • 301
  • 1
  • 11

4 Answers4

3

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

Vor
  • 12,513
  • 1
  • 30
  • 60
  • It is probably hard to beat the first approach :-) – Juho Mar 03 '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 04 '13 at 16:10
  • 2
    @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 04 '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 04 '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 05 '13 at 10:27
  • Yes, I just checked that the dot configurations are correct. – Craig Feinstein Mar 05 '13 at 13:16
  • They are from the top clockwise as you said. – Craig Feinstein Mar 05 '13 at 13:17
  • @CraigFeinstein: ok, I entered the faces in the reverse order. It takes ~200msec to solve an instance on my PC ... now I'm going to check if it's all ok (I'll verify a couple of solutions by hand), and I'll keep you informed. – Vor Mar 05 '13 at 15:23
  • Excellent. I'd like to see the code of your program. – Craig Feinstein Mar 05 '13 at 19:58
  • @CraigFeinstein: Here it is. As you can see the approach is totally different :-). If you want to compile it, remove the "package test;" line and download the Choco library which must be included in the classpath. – Vor Mar 05 '13 at 20:32
  • 1
    @CraigFeinstein: I also wrote a standard solver in javascript and published it on my blog (the code is on the page source) – Vor Mar 07 '13 at 01:12
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.

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

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.

vonbrand
  • 14,004
  • 3
  • 40
  • 50
0

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

jdelavilla
  • 1
  • 1