javascript graph-theory hamiltonian-cycle

Canonical algorithm for "visit each door once" problems

There are a number of puzzles that are variant of the classic "7 Bridges of Konigsberg" puzzle where you must find a route through a set of rooms without ever using a door twice.

Here is an example of one without a solution.

... and is a slightly modified puzzle that does have a solution, as you can see here.

I'm interested in a programmatic approach to solving these sort of problems and while there are a number of ways to determine that a particular configuration of rooms and doors has no solution, I am interested in computing the lists of doors to visit to solve the puzzle. One way to view the problem is to transform it's configuration into a graph and solve for the Hamiltonian. This sort of problem however requires tacking on inelegant logic because of the constraint that "U-Turns" are prohibited.

I hacked up a solution in a few minutes to show the problem. It is a brute-force solution that puts the "rooms" into groups, with the added invariant that you cannot move from one "door" to another "door" in the same room (as that would entail doing a U-Turn).

I feel that there must be a better abstraction for representing this problem that does not resort to the following "tricks":

Having additional logic for removing doors in the same room as valid choices when the path has just come from that room.
Producing a graph that isn't isomorphic to the input room configuration.
Filtering all configurations that don't satisfy the U-turn constraint. (Variant of #1)

Is there an existing body of literature tackling these sort of problems, and if so, what are their conclusions? Are room problems fundamentally at odds with the methods employed by the most well-known graph algorithms such that it requires this special logic? If there is a better solution that isn't a transformation to a graph, I'd love to hear about that as well.

Here's the existing code that does work, the groups represent the first problem, the groups that are commented out represent the latter problem.:

// I renamed "groups" to rooms to make the code more clear.
var rooms = {
    1: ['A','B','C','D'],
    //1: ['A','B','C','D','P'],
    2: ['E', 'D', 'F', 'G'],
    3: ['F','I','J','H'],
    //3: ['F','I','P','J', 'H'],
    4: ['I', 'M', 'N', 'O'],
    5: ['C','J','M','L','K'],
    OUTER: ['A', 'B', 'E', 'G', 'H', 'O', 'N', 'L', 'K']
}

class Graph {
    constructor(rooms) {
        // This is a map of a door letter to the rooms (rooms) that it belongs to.
        this.roomKey = {};
        // The total number of doors
        this.totalNodes = 0;
        this.rooms = rooms;
        // This is only used to produce the number of rooms, but remains in case
        // I need to adapt the algorithm for the classical approach.
        this.vertices = {};
        for (var key in rooms) {
            this.addRoom(key, rooms[key]);
        }
    }

    addRoom(roomName, elements) {
        for (var from of elements) {
            if (!this.roomKey[from]) {
                // initialize
                this.roomKey[from] = [roomName]
            } else {
                this.roomKey[from].push(roomName)
            }
            for (var to of elements) {
                // it doesn't make sense to add a vertex to yourself
                if (from === to) continue
                // otherwise add the vertex
                this.addDoor(from, to)
            }
        }
    }

    addDoor(name, edge) {
        // initialize if empty
        if (!this.vertices[name]) {
            this.vertices[name] = []
            this.totalNodes++
        }

        if (this.vertices[name].indexOf(edge) != -1) {
            console.log(`${name} already has this edge: ${edge}`)
        } else {
            this.vertices[name] = this.vertices[name].concat(edge)
        }
    }

    hamiltonian(current, prevRoom, used) {
        // Find the rooms that this connects to
        var kpossible = this.roomKey[current]

        // Find the rooms that connect to this door, but filter those that are
        // in the room we just came from, this is the hacky part.
        var possibleRoom = kpossible.find((room) => room !== prevRoom)
        // Produce all possible rooms, but if we've already been to a room, remove it.
        var possibleDoors = this.rooms[possibleRoom].filter((elt) => used.indexOf(elt) == -1)

        if (used.length == this.totalNodes) {
            console.log("success!", used)
            return;
        }

        // No more possible rooms, this path is no good.
        if (!possibleDoors || possibleDoors.length === 0)
            return;

        for(var door of possibleDoors) {
            this.hamiltonian(door, possibleRoom, used.concat(door))
        }
    }
}

The doors are labeled as follows:

Solution

As you stated a door can only be used once.

I would represent the data as an adjacency list with the following properties:

Each room is a vertex
Outside is a vertex
Each door is a bi-directional edge
Any room can have multiple doors going to any other room or to the Outside

Then you would follow each edge only once.

In order to convert your data structure into an adjacency list I would do the following:

Collect all the labels for each door into an array
For each door label, find the two connecting rooms
Add the two rooms as an entry in the adjacency list

Something like this will build the adjacency list from the data structure that you already have:

var groups = {
    1: ['A','B','C','D','P'],
    2: ['E', 'D', 'F', 'G'],
    3: ['F','I','P','J', 'H'],
    4: ['I', 'M', 'N', 'O'],
    5: ['C','J','M','L','K'],
    OUTER: ['A', 'B', 'E', 'G', 'H', 'O', 'N', 'L', 'K']
}

var edges = [];
var adjacency_list = [];

// collect all the doors
for (var room in groups) {
  doors = groups[room];
  for (var door of doors) {
    if (edges.indexOf(door) < 0) {
      edges.push(door); // mark off this door
    }
  }
}

// find the connections between the rooms (build the adjacency matrix)
for (var door of edges) {
  rooms = [];

  // find the two rooms that this door connects
  for (var room in groups) {
    doors = groups[room];
    if (doors.indexOf(door) > 0) {
      rooms.push(room);
    }
  }

  // add these as an edge in our adjacency list
  if (rooms.length == 2) {
    adjacency_list.push(rooms);
  }
  else {
    //TODO: raise an error as the rooms aren't connected properly
  }
}

Now, adjacency_list is a list of edges that you can use to traverse between rooms. There will be one edge per door connecting two rooms. If you traverse an edge (go through a door), then it must be removed (or marked) so that you do not traverse it (go through the door) again.