The game

The house of santa claus is a popular game for children. The graph with 5 nodes and 8 edges is to be drawn without lifting the pen.

    5
    .
   / \
4 /---\ 3
  |\ /|
  | X |
  |/ \|
  |---|
  1   2

The program finds all 44 solutions starting at node 1. For reasons of symmetry there are corresponding solutions starting at node 2. There are no solutions starting at the nodes 3, 4 or 5.

Recursive algorithm (imperative vs. functional)

The implementations in imperative languages change the adjacency matrix of the graph or start with a zero matrix and build it up successively until it equals the adjacency matrix. Changes are made, the way through the decision tree is tracked, then the changes to the matrix get reverted.

Functional programming shows its elegance: Alternative versions of the matrix are generated for each recursion step and get discarded when they are no longer needed.

How to run

GHCI (interpreted)

start GHCI in the directory, then: :l nikolaus.hs

Get prettily formatted solutions:

putStrLn $ format $ solve 1

List of solutions

solve 1 (read the lists from right to left)

Count the solutions

length $ solve 1