A library for defining, manipulating, scrambling, and solving arbitrary twisty puzzles using graph-theoretic and group-theoretic abstractions.
Standard twisty puzzles can be modeled as groups. With this model, metrics can be represented as subsets of these groups. A Cayley graph is a colored graph which can be constructed from a group and any generating set of that group. Finding a path to the identity element on the Cayley graph generated by a twisty puzzle and a metric corresponds to solving that puzzle, with the color of the edges in the path corresponding to the solution.
Data.Graph provides an interface representing a colored graph as a function from a node to its
neighbors along with the color of the edge traversed. It also provides generic algorithms for
searching graphs. Depth-first search (DFS) and
iterative deepening depth-first search
(IDS) both take an optional
argument to prune the search tree by providing a lower bounding function. When provided a lower
bound, IDS becomes Iterative deepening A*
(IDA*).
Data.Graph.Cayley provides a generic implementation of the Cayley graph for a group and a
generating set.
Data.Group provides a group interface and an interface for representing generating sets, along
with many generic or trivial implementations of both.
Data.Group.Permutation provides an interface for permutation groups, along with two concrete
representations: a list of cycles, and a permutation vector.
Data.Group.Cyclic provides an implementation of cyclic groups.
TODO