Systematic solution search for "Das Haus vom Nikolaus"

haus-vom-nikolaus.md

This code systematically explores the solution space for the puzzle "Das Haus vom Nikolaus". It finds various things:

• Solutions: Paths that use each (undirected) connection exactly once.
• Failures: Paths ending in a vertex where you cannot continue (because all connections of the vertex have been used already), but there are still unused connections elsewhere.
• "Early Failures": Paths where the last step was a mistake. That is, the path cannot be completed to a solution but without the last step it could have been (by continuing another way).

Usually one is only allowed to cross the middle of the house (the X in the sketch near the beginning of the code) in a straight line from b to e or from c to d or in the opposite direction. But some people consider the crossing as an actual vertex where you may start or end the path or change the direction. The program handles both variants.

Here are the numbers of paths of each kind found by the program for each variant of the puzzle:

	solutions	failures	early failures
without vertex X	88	266	23
with vertex X	240	1008	78

Notes on the code:

• Yes, my string-based data structures are quite simplistic. They work in this simple application but not for larger graphs. But I think the idea of the algorithm becomes clearer without elaborate graph data structures.
• Of course the algorithm could be optimized if we did not care about failures. Solutions are only possible if there are at most two vertices with an odd number of connections. And if there are two such vertices, solutions must begin at one of them and end with the other.

Running the code:

• Invoke the code using one of the following command lines, depending on which JS/TS runner you have available:

  node --watch haus-vom-nikolaus.ts
  deno run --watch haus-vom-nikolaus.ts
  bun --watch haus-vom-nikolaus.ts
  

• If you're not playing with the code and only want to run it once, omit the option --watch.
• Direct execution of (some subset of) TypeScript in node works for v23.7.0. Older versions (probably before v23) require the command-line option --experimental-strip-types, which was introduced in nodejs V22.6.0. With an even older version of nodejs you have to convert the TypeScript code to JavaScript, using the TypeScript compiler or babel or esbuild or... (or just remove the type annotations manually).

haus-vom-nikolaus.ts

/*
Das Haus vom Nikolaus
---------------------

  a
 / \
b---c
|\ /|
| X |
|/ \|
d---e

*/

console.log("Only straight crossings of X (be and cd):");
solve("abcde".split(""), "ab ac bc bd be cd ce de".split(" "));
 
console.log("\nStart, end, and direction changes allowed at X:");
solve("abcxde".split(""), "ab ac bc bd bx cx ce xd xe de".split(" "));


function solve(vertices: string[], connections: string[]) {
  const connected: Record<string, string[]> = {};
  for (const [p, q] of connections) {
    (connected[p] ??= []).push(q);
    (connected[q] ??= []).push(p);
  }

  /** Complete paths */
  const solutions: string[] = [];

  /** Paths that cannot be extended at all */
  const failures: string[] = [];

  /** Shortest paths that cannot be extended to a solution: */
  const early_failures: string[] = [];

  function search(prefix: string, choices: string[], depth: number): boolean {
    if (choices.length === 0) {
      failures.push(prefix);
      return false;
    }

    /** Can `prefix` be extended to a full path with one of the `choices`? */
    let solvable = false;

    /** Which extended prefixes cannot be extended to a full path? */
    const failingExtensions: string[] = [];

    for (const p of choices) {
      const prefix_p = prefix + p;
      if (depth === 0) {
        solutions.push(prefix_p);
        solvable = true;
      } else {
        const next_choices =
          connected[p]
          .filter(q => !prefix_p.includes(p + q) && !prefix_p.includes(q + p));
        if (search(prefix_p, next_choices, depth - 1)) {
          solvable = true;
        } else {
          failingExtensions.push(prefix_p);
        }
      }
    }
    if (solvable) {
      early_failures.push(...failingExtensions);
    }
    return solvable;
  }

  search("", vertices, connections.length);

  for (const [name, list] of Object.entries({solutions, failures, early_failures})) {
    console.log(list.length, name + ":", list.join(", "));
  }
}