Canonical algorithm for "visit every door once"

Question

There are many puzzles, which are a variant of the classic puzzle "7 Koenigsberg bridges", where you have to find a route through a set of rooms, without even using the door twice.

Here is an example of one without a solution.

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

I am interested in a programmatic approach to solving such problems, and although there are several ways to determine that a particular room and door configuration does not have a solution, I am interested in calculating door lists to visit to solve the puzzle. One way to look at a problem is to convert its configuration to a graph and solve for the Hamiltonian. However, such a problem requires binding to inelegant logic due to restrictions that are prohibited by U-Turns.

I cracked the solution in a few minutes to show the problem. This is a brute force solution that puts “rooms” in groups, with an added invariant that you cannot move from one “door” to another “door” in one room (since this would entail a U-turn).

I feel that there should be a better abstraction to represent this problem, which does not resort to the following "tricks":

• The presence of additional logic for removing doors in the same room as the actual options when the path has just left this room.

• Creating a graph that is not isomorphic to the input room configuration.

• Filtration of all configurations that do not satisfy the spread limit. (Option No. 1)

Is there an existing body of literature that solves these problems, and if so, what are their findings? Are the problems in the room fundamentally different from the methods used by the most well-known graph algorithms, which require this special logic? If there is a better solution that is not a conversion to a schedule, I would also like to hear about it.

Here the existing code that works, groups represent the first problem, groups that are commented out represent the last 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)) } } } 

Doors are marked as follows:

Answer 1

As you said, a door can only be used once.

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

• Each room represents a peak.
• Outside is the pinnacle
• Each door is a bi-directional edge.
• In any room there can be several doors going to any other room or outside.

Then you will follow each edge only once.

To convert your data structure to an adjacency list, I would do the following:

• Collect all the shortcuts for each door into an array
• Find two adjacent rooms for each door label.
• Add two rooms as an entry in the adjacency list

Something like this will build an adjacency list from an existing data structure:

 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 move between rooms. Each door will have one edge connecting the two rooms. If you cross an edge (go through the door), you must remove it (or mark it) so that you do not go through it (go through the door) again.