# Hamiltonian paths tutorial

## Introduction

Hamiltonian paths are rarely encountered in video games compared to "shortest path" algorithms like A*. This is partly because the Hamiltonian paths problem is notoriously difficult, but mostly because there haven't been enough open source projects, libraries or tutorials on the subject. This is a real shame since many genres of games*could*be designed around the use of Hamiltonian paths.

Diagram 1: Super Chains, co-developed by your truly.

Find the longest chain of bubbles sharing the same color.

Hamiltonian paths present a search problem that is considered "NP-hard". Some really sophisticated research has gone into this problem, so please consider this humble tutorial as a brief introduction.

## Knight's tour problem

Imagine a regular 8x8 chessboard. Can you traverse every square on the board using only the knight piece? Here is the catch: you are only allowed to visit each square once! It takes exactly 63 moves to solve the puzzle and if you manage to do it, then you have found one possible "Hamiltonian path". Note that if you can finish the Knight's tour one move away from the initial square where you started then you have completed what is called a "Hamiltonian cycle".Diagram 2: Knight piece with eight possible moves highlighted in yellow.

## Building the graph

Initially, it seems like Hamiltonian paths are an easy challenge for the computer. All we have to do is track the number of visited squares, right? Before we give it a try, let's refer to the chessboard as a "graph" and its squares as "vertices" or "nodes". Any possible move of the knight will be called an "edge". Why? Because technical nomenclature make us sound smart! When we draw all possible connections on the board then the terminology makes a little more sense:Diagram 3: Graph of the legal knight moves on a chessboard:

Lines are called "edges", where each edge connects two neighboring nodes

Circles are called "nodes" and each number represents the number of edges for that node

The graph is represented in Lua as a table where:
1.each key is a node and
2.each value is a table containing the neighboring nodes.

This simple approach allows us to check if any two nodes are connected by writing:

if graph[node1][node2] then -- node1 and node2 are connectedNext, we are going to build a graph representing the chessboard. Each node or square on the board will be labeled with a number (from 1 to 64 for an 8x8 board). To connect the nodes, we need a way to find all the legal knight moves for any given square. The following example uses a method called "mailboxing". Mailboxing adds a few rows of padding and allows us to eliminate invalid moves, so that our poor knight can't jump off the board! If you have any chess knowledge at all, you could probably come up with a different approach of generating the graph.

-- mailbox local w, h = 8, 8 local squares = {} local sq = 1 for y = 3, h + 2 do local i = (y - 1)*(w + 2) for x = 2, w + 1 do squares[i + x] = sq sq = sq + 1 end end -- graph local knight = { -21, -19, -12, -8, 8, 12, 19, 21 } local graph = {} for from, sq in pairs(squares) do graph[sq] = {} for _, move in pairs(knight) do local to = from + move local sq2 = squares[to] if sq2 then graph[sq][sq2] = true end end end

## Traversing the graph

We know for a fact that the Knight's tour problem can be solved with 63 moves. If we include the starting square that's a path of 64 squares.Generally, we can figure out the longest, theoretically possible Hamiltonian path for

*any*graph using the formula:

maxdepth = numberOfNodes - max(nodesWithOnlyOneEdge - 2, 0)This value is important, because it serves as an upper bound while searching for a solution.

To estimate the

*length*of the longest Hamiltonian path, we use the following code:

-- count the number of edges for a node function count(edges) local n = 0 for neighbor in pairs(edges) do n = n + 1 end return n end -- estimate the longest Hamiltonian path function maxdepth(graph) local n = 0 local edge1 = 0 for node, edges in pairs(graph) do if count(edges) == 1 then edge1 = edge1 + 1 end n = n + 1 end return n - math.max(edge1 - 2, 0) end

### Brute force

OK, though guy... you recently upgraded your CPU and think you can plow through the Hamiltonian path problem in no time. The bad news is that that there are estimated 4x10^{51}possible move sequences and the valid solutions are quite rare. Now that you have an idea of the

*enormous*size of the search space, it should be clear that using "brute force" is clearly not an option.

### Warnsdorf's rule

While there are linear-time algorithms for solving the Knight's tour, this is not the case for more complicated types of graphs. Nevertheless, mathematicians have discovered a few clever tricks. Warnsdorf's rule suggest that when searching the graph, we should seek the nodes that have the*fewest*non-visited neighbors. Let's look at a concrete example.

Diagram 4: Graph traversal following Warnsdorf's rule

1. Graph of four nodes (A,B,C and D) and five edges, traversal begins from node A.

2. Node A: There are three possible choices (B,C and D). Two of the choices (B and C) have fewer non-visited neighbors compared to the third choice (D). According to Warnsdorf, choices B and C must be considered before D.

3. Node C: There is one possible choice (D)

4. Node D: There is one possible choice (B)

Warnsdorf's rule is good for simple graphs like our chessboard, but it may not always work. In many cases, following the rule is

*not*enough to find a solution. Therefore, our code needs to perform some backtracking.

local visited = {} -- count the number of non-visited neighbors function nonvisited(edges) local n = 0 for neighbor in pairs(edges) do if not visited[neighbor] then n = n + 1 end end return n end -- traverse the graph using Warnsdorf's rule function traverse(graph, node, depth, best, path) depth = depth or maxdepth(graph) path = path or {} best = best or {} -- track the longest path table.insert(path, node) if #path > #best then for i = 1, #path do best[i] = path[i] end end -- visit neighboring nodes if #best < depth then visited[node] = true -- consider all non-visited neighbors local choices = {} for neighbor in pairs(graph[node]) do if not visited[neighbor] then table.insert(choices, neighbor) end end -- sort choices by fewest non-visited neighbors table.sort(choices, function(a, b) return nonvisited(graph[a]) < nonvisited(graph[b]) end) -- try each available choice for i = 1, #choices do if traverse(graph, choices[i], depth, best, path) then break end end visited[node] = nil end table.remove(path) return #best == depth, best end

### Choosing a starting node

Note that with the Knight's tour problem we can start the search from any square, but for other types of graphs*some*starting nodes could be eliminated.

For the purposes of this tutorial, we want to keep it simple. Using the "traverse" algorithm is as easy as providing a graph and a starting node:

-- search for Hamiltonian paths local res, path = traverse(graph, 1) -- print the longest path found error("found path:" .. table.concat(path,','))

I would like to end this tutorial by saying that the code provided here is far from perfect. The methods we have considered are just slightly more advanced than using brute force, but the difference in speed is significant. The tutorial code could probably handle most small graphs in less than a second, but imagine what may be possible with more sophisticated techniques! More importantly, I hope to have encouraged you to learn about graph theory. Thanks for reading and have a nice day.

- Knight's Tour on Wikipedia