Solver for the "3D Logic" puzzle
This is solver for the '3D Logic' game available here. It uses a brute-force method to try all paths until it finds the solution, so it is not very smart. If several solutions exist, only the first one is printed. The archive includes examples up to the 12th level.
You need OCaml and make to be able to compile the program. I'm not providing precompiled binaries at the moment.
Theoretical background
The puzzle with the face size of 3 can be represented with the following planar graph:
X - X - X -+- X - X - X
| | | | | |
X - X - X -+- X - X - X
| | | | | |
X - X - X -+- X - X - X
| | | | | |
+ + + | | |
| | | | | |
X - X - X-----+ | |
| | | | |
X - X - X---------+ |
| | | |
X - X - X-------------+
The puzzle has an interesting theoretical background: finding disjoint
paths in a graph. This has been proven to be NP-complete problem,
but polynomial time algorithms exist for planar graphs and fixed
k (number of colors). However, the algorithm is incredibly
complicated; apart from group theory you also need to find the dual of
a planar graph (which is currently the biggest obstacle for me to
implement it). Even though the program implements a "stupid"
algorithm, it is pretty fast, and I don't see the need to implement
a more advanced algorithm.
Two papers discuss the problem of disjoint paths in directed graphs at length, and they also give references to the undirected version of the algorithm:
Alexander Schrijver: "Finding k disjoint paths in a directed planar graph" SIAM J. Comput., Vol. 23, No. 4, pp. 780-788, August 1994
Alexander Schrijver: "A Group-Theoretical Approach to Disjoint Paths in Directed Graphs"; this document can be fetched here.
