[qkzckglp] spaghetti maze

unicursal labyrinth: 2 endpoints and a path between them.  lots of twists and turns but no branches.  perhaps a meditation exercise, perhaps a linear adventure with unavoidable challenges and enemies along the path.

multi unicursal labyrinth: 2*N endpoints and N paths between pairs of endpoints.  no path has branches.  task is to determine which endpoints connect to which (a matching).  also perhaps a meditation exercise.

the number of ways to pair 2*N endpoints is the product of odd numbers up to 2*N-1 (double factorial) (OEIS A001147).  N = 29 (58 endpoints) exceeds 2^128.  N = 50 (100 endpoints) exceeds 2^256.

a quick and dirty way to convert a matching to an integer or a key is to write the matching in a canonical way then hash it.  for example, ascending numeric order with separators:

SHA256("0-47 1-37 2-10 3-22 4-57 5-18 6-36 7-52 8-55 9-50 11-12 13-40 14-27 15-56 16-35 17-51 19-32 20-54 21-39 23-38 24-28 25-31 26-44 29-34 30-41 33-46 42-45 43-49 48-53") = 4fd0acf830bd822f25dec87686132cf55b11ded84ddb1bdace89a726aaf7582e

the key can then unlock the prize for solving the multi unicursal labyrinth, perhaps the next puzzle.

unsolved: algorithm for one-to-one bijection between matchings and consecutive integers.

next we consider generating a multi unicursal labyrinth.

we generate on a square grid.  place all the endpoints as nodes on the boundary of a rectangle, each node coinciding with a vertex on the square grid.  in total, the endpoints must completely surround the rectangle; this is only possible if the number of endpoints is an even composite number, and if the rectangle has the proper dimensions.

consider a square region around each internal vertex: call it a "tile".  each tile has 4 outgoing edges, one in each of the cardinal directions.  two possible tiles, the two Truchet tiles:

1. North connects to West, and South connects to East.
2. North connects to East, and South connects to West.

optionally add a third possible tile "North connects to South, and East connects to West".  although the paths visually cross, the tile represents an overpass, one path flying over the other.  permitting this tile allows more complicated multi unicursal labyrinths.

randomly assign one of the possible tile types to each internal vertex.  this creates paths between endpoint nodes on the boundary.

there will probably be internal loops (cycles).  do simulated annealing or some other optimization to penalize internal loops, altering the random tile choice at each vertex.  for example, let the objective function being maximized be (sum i (From 1) (To num_paths) ((pathlength (path[i]))^exponent)).  choosing exponent between 0 and 1 both rewards all paths being somewhat long, and penalizes internal loops, because internal loops contribute nothing to the sum.

exponent = 1/2
sqrt(100) + sqrt(100) = 20
sqrt(99) + sqrt(101) = 19.999749992

after optimization, optionally erase any internal loops that remain.  or keep them for visual noise.

page sized, mural sized, or field sized.

when solving the labyrinth (finding a matching), if a path is so long that you need to take a break while tracing it, record where you are and which way you are going.  the labeled endpoints along the edges can serve as coordinate labels.