I am looking for advice/guidance/solutions which can help me with the following problem:

  • Imagine a spatial graph in the x,y-plane arranged in an m x n grid

    • e.g. a 4x4 grid
  • Each vertex in the graph may have an arbitrary number of intrinsic characteristics or properties

    • e.g. each vertex has an associated numerical value, a color, and/or shape.
  • There is an arbitrary set of global rules placing restrictions on graph traversal. The global rule essentially generates the edges of the graph.

    • e.g. from any vertex, you may only travel to an adjacent vertex of a different color.
  • The global rules are constant, simple, and few

  • Each vertex specifies exactly one local rule, which may augment or supersede/break the global rules for traversal only for the next move.

    • e.g. for the next move, the destination vertex must have a numerical value lower than the current vertex.
  • The rules are such that they allow for exactly one traversal of the entire graph (visiting each vertex) without backtracking for every permutation of the graph, but the starting vertex may vary across permutations

  • Each traversal of a distinct permutation of the graph (excluding rotations/reflections) is distinct.

    • e.g. imagine that each vertex had a value 0-n, and each vertex n allowed a jump to the vertex with value n-1. Then each permutation of the graph is solvable by simply starting at the highest valued vertex and descending, but the traversal sequence is not distinct, it is the same for every permutation.
  • Additionally, I am also trying to avoid the opposite situation where the local rule on each vertex is just a string of conditionals mapping each distinct layout or local neighborhood to a unique traversal rule.

    • e.g. a vertex's local rule should not be something like: "If the neighboring vertices have values 1,3,4,6, then jump to the vertex with value 11; and if the vertices have values 4,5,8,9, then jump to the vertex with value 1; and if ..." Ideally it is instead something simple, e.g. "while still adhering to the global rules, the next move must also be to a vertex with a lower value."

What approach could I take to begin trying to solve this? I am thinking of building a program to enumerate each permutation of a 4x4 graph, a genetic algorithm to develop rules for traversal and characteristics, and to evaluate fitness by the ability to traverse each with exactly one solution that is distinct across permutations that aren't reflections/rotations, but I would greatly appreciate any insights/guidance.

  • $\begingroup$ I am trying to create a simple puzzle with high variability. $\endgroup$ Commented Jun 27 at 5:03
  • 1
    $\begingroup$ I believe this question needs to be much more specific (e.g. as to what constitutes a "rule") to allow for a sensible answer. As of now, the notion of global rules can be subsumed into just the collection of local rules. Tuning these can then allow to build any (directed) subgraph of the original grid, which surely (?) is not what you intended. $\endgroup$ Commented Jun 27 at 12:40
  • $\begingroup$ The global rule generates the edges of the graph, e.g. if the global rule is that you must move to an adjacent vertex (von Neumann neighborhood), then it's clear where to draw the edges. After generating the initial set of edges, you'd need to iterate through each vertex's local rule to prune and redraw edges. $\endgroup$ Commented Jun 27 at 16:32
  • $\begingroup$ The global rule is optional, you could rely on each local rule alone for the edges if that's simpler. The local rules are permanent/intrinsic to the vertex, so they would need to generate exactly one solution regardless of permutation. $\endgroup$ Commented Jun 27 at 16:49