*Cardinal Chains* is a simple to understand, fantastically fun puzzle game (you can get it here, and on any mobile device).The premise is as follows: The player is given a grid of numbers, and a coloured start point. The objective is to fill the entire grid with colour by moving from the start to every square in the grid. You are not allowed to backtrack, and you can only move to a square with a higher or equal number than the one you’re currently on.

Being the ~~extremely cool person~~ giant nerd that I am, my first thought was “*Can I get a computer to play this?”*

In drawing out diagrams of the levels, it became apparent they could be represented as *graphs*. Rather than a graph of a function, which most people are familiar with, I’m referring to a mathematical structure made up of * nodes *connected together by

*. For example, the level above can be represented like this:*

**edges**

Graphs can be **weighted **or **unweighted**, and can be **undirected, directed **or **mixed. **Weighted vs unweighted simply refers to whether the vertices have a value associated with them. These can be used to represent the “cost” of travelling along that vertex. For example, if your nodes are cities, and your vertices roads, the weights might represent how far apart the cities are (i.e. how “long” each road between them is).

In an undirected graph, every edge can be travelled along in both directions. In a directed graph, each edge only goes one way. A mixed graph is, unsurprisingly, one that contains both directed and undirected edges. It’s worth noting that any mixed (or indeed undirected) graph can be made into a directed graph by simply converting every undirected edge to two directed ones, one in each direction.

So what we have above is an **unweighted mixed graph**.

#### Complications

Graph theory is a pretty well established subject, so all I need to do now is look up the algorithm for visiting every node on a graph exactly once, code it up, and we’re done right? **Wrong.** The problem of visiting every node on a graph exactly once has indeed been studied at length (it’s called the *Hamiltonian path problem),* but it has been shown to be *np-complete. *What this means is that it’s very easy to check whether a solution is valid, but there is no efficient way to come up with a solution in the first place. Consider soduku – if someone hands you a completed grid it’s trivial to check whether it’s correct, but actually solving it in the first place is much harder. The Hamiltonian path problem has a similar type of difficulty. Note that both with soduku and the cardinal chains levels, most everyday examples are small enough that they can simply be solved with brute force: try every possible solution until you come up with the right one. I’d quite like to avoid this if possible, though.

At this point I realised I wasn’t going to be able to solve any arbitrary, randomly generated level. However, the levels in *Cardinal Chains* have been **designed to be solvable by a human.** Hell, I did the first 75 levels or so in about half an hour. So, I decided on a new strategy: play the game, and slowly, step-by-step, figure out what logical deductions I’m using to solve the problems. If I can generalise these into rules, perhaps I can come up with a step-by-step way a machine can solve each level. After doing this for a little while (and spending lots of time drawing and staring at graph representations on my whiteboard), I came up with the following rules (I refer to directed edges leaving or arriving at a node as exits and entrances):

- “End points”, if they exist, can be located as nodes with either a single two-way edge or no exit edges.
- If a node with a two-way edge is an end point, the edge can be made into an entry edge.
- If a node has only a two-way edge and exit edges, the two-way edge can be converted to an entry edge (since all nodes must be accessible somehow).
- If a node has only a two-way edge and entry edges, the two-way edge can be converted to an exit edge (since if it’s not an end point, you need to be able to leave it).
- If a node is part of the only path to an end point, that node can’t have any other exits (as if you took them you’d never get to the end point).
- If a node has only a single exit, all other entrances to that destination can be destroyed (since you
*have*to arrive at it from that node). - If every node (apart from Start) has a single exit edge, and an end point has been found, the solution is found by backtracking from End and only moving to Start when it is the only possible option.

Following only these rules I was able to solve several levels “by hand” on my whiteboard. How exciting! Time to write some code. I chose to use Python, since it’s by far the language I’m most comfortable with, and enough my brain is already occupied with problem solving to have to also worry about unfamiliar syntax. If I want to visualise the solutions later, I’ll use Tk, or write a little snippet that throws the relevant information to p5.js.

#### Implementing the rules

The first thing we need is something to represent our graph. For an unweighted graph, we can just use a dictionary: Each node has an ID, which we use as a key, and its values are the IDs of the nodes it is connected to. This representation is implicitly **directed**:
{'A':['B', 'C']} represents a graph with 3 nodes and two **one way** vertices going from A to B and C respectively. If we want two way vertices, we have to add vertices going back the other way:

1 2 3 |
{'A': ['B', 'C'], 'B': ['A'], 'C': ['A']} |

So we need a graph class, a dictionary to store the nodes and their vertices and a method to construct a graph from a Cardinal Chains level. We also need a method to check if a vertex between two nodes is two-way, since I refer to undirected vertices a lot in my rules, while our graph representation is directed. I chose to represent the levels as matrices, with a value of -1 representing an unused grid square, 0 representing a start square and then the other squares simply represented by their numbers. As a result, we can construct the graph as follows:

- Iterate over each grid square and do the following:
- If the square contains -1, do nothing
- Otherwise, look at all the adjacent squares. If their values are greater than or equal to the current square’s value, construct vertices to them from the current square.

Dealing with all the edge cases turned this method into a bit of a monster of for loops and if/else statements, but the comments should make it clear enough.

*(mouse over or click the ⇔ icon to expand the code box so you don’t need to scroll sideways).*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Graph: def __init__(self): self.nodes = {} # Nodes are stored as a dict with their ids as keys # Check if there's a two-way edge between two nodes def twoWay(self, x, y): return ((y in self.nodes[x]) and (x in self.nodes[y])) def from_matrix(self, matrix): self.matrix = matrix for rowI, row in enumerate(matrix): for colI, val in enumerate(row): # If cell is empty, do nothing if val == -1: pass # Otherwise, check all 4 neighbours (if they exist) # and add the relevant edge to the graph else: if val == 0: self.startPoints.append((rowI, colI)) self.nodes[(rowI, colI)] = [] for (i, j) in [(0, 1), (1, 0), (0, -1), (-1, 0)]: if ( # Column out of bounds rowI + i >= 0 and rowI + i < len(matrix) and # Row out of bounds colI + j >= 0 and colI + j < len(matrix[0]) and # Comparing node with itself not (i == 0 and j == 0) ): if matrix[rowI + i][colI + j] >= val: self.nodes[(rowI, colI)].append((rowI + i, colI + j)) |

At this point I realised a visualiser of some kind would probably prove a very hand debugging tool down the road. I’m not terribly experienced using Tkinter, so the code is a little hack-y, but I’ve included it and my test script anyways just in case you’re interested. The result confirms my graph representation is working as expected.

*(again, mouse over or click the ⇔ icon to expand the code box)*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
def draw(self): # Window width and height, and matrix box side length in pixels width = 1280 height = 720 box = 100 fontSize = 36 # Set up a simple Tk canvas root = Tk() c = Canvas(root, width=width, height=height) c.pack(side="top", fill="both", expand=True) # Add headings and divider to our display c.create_text(width/4., height*.1, text="Level Matrix", font=("TkDefaultFont",fontSize)) c.create_text(3*width/4., height*.1, text="Level Graph", font=("TkDefaultFont",fontSize)) c.create_line(width/2., 0, width/2., height) # Now we're going to display the input matrix and # the generated graph, side by side # We want these to sit nicely centered in their halves, # so first we're going to calculate how much space we need # for our representation diagramWidth = box*len(self.matrix[0]) diagramHeight = box*len(self.matrix) padX = (width/2. - diagramWidth)/2. padY = (height - diagramHeight)/2. # Make the matrix representation for rowI, row in enumerate(self.matrix): for colI, val in enumerate(row): # Calculate rectangle placement and draw it rectX = padX + colI * box rectY = padY + rowI * box c.create_rectangle(rectX, rectY, rectX + box, rectY + box, outline="black") # Apply the relevant label, if any if val != -1: if val == 0: c.create_text(rectX + box/2., rectY + box/2., text='S', font=("TkDefaultFont",fontSize)) else: c.create_text(rectX + box/2., rectY + box/2., text=str(val), font=("TkDefaultFont",fontSize)) # Make the graph representation # We need to shift accross to the other section of the window r = box * .1 # Radius of the node dots rectX += width/2. + box/2. + r/2. rectY += box/2. + r/2. sep = (box - 2*r*1.4) # This is the length of the vertex arrows # Draw a dot for each node if val != -1: c.create_oval(rectX - r, rectY - r, rectX + r, rectY + r, fill='black') # For each vertex, draw the relevant arrow if (rowI, colI) in self.nodes.keys(): for vertex in self.nodes[(rowI, colI)]: direction = (vertex[0] - rowI, vertex[1] - colI) startX = rectX + direction[1]*r*1.4 startY = rectY + direction[0]*r*1.4 endX = startX + direction[1]*sep endY = startY + direction[0]*sep c.create_line(startX, startY, endX, endY, arrow="last", width=3, arrowshape=(16,20,6)) root.bind('<Escape>', sys.exit) root.mainloop() |

1 2 3 4 5 6 7 8 9 10 |
from Graph import Graph t = [ [-1, -1, 0], [ 1, 1, 1], [ 1, 1, 1], [ 2, 2, 3]] g = Graph() g.from_matrix(t) g.draw() |

Great. We’re getting somewhere. Now I need to code-ify the rules I’ve come up with, and see if we can solve this level with it. I started with finding the end point, and quickly found a problem with my implementation: if a node has no vertices leaving it, it doesn’t exist in self.nodes . So I modified from_matrix to initialise every node as an with an empty array as the list of vertices. This also removed the slightly ugly “try…except KeyError” workaround I was using. (I could have also just used a defaultdict, whose existence I managed to forget about)

Overall, rules 1-4 and 6 were really straightforward to implement:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
# Rule 1 def check_for_end(self): endPoints = [] for node in self.nodes: # Grab all the vertices LEAVING the node in question edges = self.nodes[node] # No exits at all if (edges == [] or ( # Just one two-way node that therefore must be entrance len(edges) == 1 and self.twoWay(node, vertices[0])) and self.nodes.values().count(node) == 1): endPoints.append(node) self.endPoints = endPoints return endPoints # Rule 2 - If a node with a two-way vertex is an end point, the vertex can be made into an entry vertex. # i.e. end points shouldn't have any exit nodes def convert_endpoint_edges(self): for node in self.endPoints: self.nodes[node] = [] # Rules 3 - 6 def check_edges(self): for node in self.nodes: # List of nodes that have exits that lead to this node enteringNodes = [x for x in self.nodes.keys() if node in self.nodes[x]] # Rule 3 - If a node has only a two-way vertex and exit edges, # the two-way edge can be converted to an entry edge if len(enteringNodes == 1) and twoWay(node, enteringNodes[0]): self.nodes[node].remove(enteringNodes[0]) # Rule 4 - If a node has only a two-way edge and entry edges, # the two-way edge can be converted to an exit edge if len(self.nodes[node] == 1) and twoWay(node, self.nodes[node][0]): self.nodes[self.nodes[node][0]].remove(node) # Rule 5 - If a node is part of the only path to an end point, # that node can't have any other exits # Rule 6 - If a node has only one exit, all other entrances # to its destination node can be removed. if len(self.nodes[node]) == 1: # Need to grab all the nodes that lead to the destination in question penultimateNodes = [x for x in self.nodes if self.nodes[node][0] in self.nodes[x]] # Now iterate over that list and remove the destination from the other nodes edges for pNode in penultimateNodes: if pNode != node: self.nodes[pNode].remove(self.nodes[node][0]) |

Rule 5 is going to be slightly more tricky – we need a way of testing if a node is part of the only path to an end point. The first thing that occurred to me was this:

- Start at the end point
- Backtrack as long as you have only one option of where to go
- Keep a list of all the nodes you visit

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Rule 5 - If a node is part of the only path to an end point, # that node can't have any other exits if self.endPoints != []: # First we need to build a list of the path to the end point path = [] currentNode = self.endPoints[0] currentEnteringNodes = [x for x in self.nodes.keys() if currentNode in self.nodes[x]] while len(currentEnteringNodes) == 1: path.append(currentNode) currentNode = currentEnteringNodes[0] currentEnteringNodes = [x for x in self.nodes.keys() if currentNode in self.nodes[x]] # Now we check whether any of this node's exits lead to the path onlyValidExit = None for exit in self.nodes[node]: if exit in path: onlyValidExit = exit # If that's the case, we then remove all the remaining exits. if onlyValidExit is not None: self.nodes[node] = [onlyValidExit] |

It’s not the prettiest code I’ve ever written, and it’s rather inefficient, but at this point I’m not too worried about that; the cardinal chains levels are small enough that iterating through the nodes takes a negligible amount of time.

Repeatedly applying my
check_edges() function solves the simple level we’ve been working with in 3 iterations.

In fact, it solves some fairly complex levels in only a few iterations too:

#### Complications….again.

My algorithm runs in to a brick wall *really* hard on some other levels:

That’s it. We remove two nodes in one iteration, and then nothing. Despite the fact that it’s easy to “see” a solution to the level,

Clockwise rotation outwards from centre (starting at 6 o’clock) followed by anticlockwise rotation around the edge.

*Rule 6.5: If a node has only a single entrance, all other exits from the entering node can be destroyed*.

Adding this in takes a single simple if statement and gets us *much* closer to solving the level:

1 2 3 4 |
# Rule 6.5 - If a node has only a single entrance, # all other exits from the entering node can be destroyed if len(enteringNodes) == 1: self.nodes[enteringNodes[0]] = [node] |

We’re still stuck with a little chain on the right, though. Again, to a human, it’s blatantly obvious you can’t take the right-leading vertex when you reach the top-right 2. So *why* is it obvious? Well, once you take that vertex, part of the graph has become unreachable and we’ve therefore failed. This is a more complicated statement to test than it seems though: what we’re actually saying is “*No paths from the node this vertex leads to have access to a part of the graph we have yet to visit*“. To test this, we have to evaluate all the paths from a given node, and since we’re applying all our rules to each node, we’d end up evaluating every possible path in the graph, which would be even less efficient than brute-forcing every possible route from start to end. It seems there isn’t a way deterministically find the correct path using the kind of rules we’ve been following up to this point (at least, I haven’t been able to find one!). Time to leverage the fact that we are indeed using a machine, and apply some brute-force. I found a depth-first-traversal algorithm by Neelam Yadav over at GeeksforGeeks, and modified it to do what I wanted: Find every possible path (without repetition of nodes) from the start to the end point of the graph, and select only the paths that visit every node.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
def brute_force(self): # Dictionary to keep track of which nodes have been visited visited = {} for node in self.nodes.keys(): visited[node] = False # Find all paths between the start and end point of the graph self.findAllPaths(self.startPoints[0], self.endPoints[0], visited, path=[]) # Select only the solutions that visit every node self.solutions = [x for x in self.paths if len(x) == len(self.nodes.keys())] def findAllPaths(self, start, dest, visited, path) # Mark the start node as visited and add it to the current path visited[start] = True path.append(start) # If there's nowhere to go, add a copy of the path to self.paths if start == dest: a = [x for x in path] self.paths.append(a) # Otherwise, recursively visit all available nodes else: for node in self.nodes[start]: if not visited[node]: self.findAllPaths(node, dest, visited, path) # Backtrack: Remove the node from the path, and mark it as unvisited path.pop() visited[start] = False |

Obviously, this solution only works if we’ve found an end point. If we haven’t we have to do it for every possible end point (i.e. every node in the graph that isn’t a start point), which is significantly more computationally expensive. So, now we can evaluate how long it takes to implement the original graph compared to our “simplified” one. Since we’re going to be looking at performance, it’s important we’re only calling check_vertices() until it stops removing edges:

1 2 3 4 5 6 7 8 |
def simplify(self): prev_complexity = len(self.nodes.values()) self.check_vertices() new_complexity = len(self.nodes.values()) while prev_complexity != new_complexity: prev_complexity = len(self.nodes.values()) self.check_vertices() new_complexity = len(self.nodes.values()) |

#### Performance Comparison

In order to test a large number of iterations without creating a new graph object every time, we’re going to need a function to reset the graph to its original state

1 2 3 4 |
def reset(self): self.from_matrix(self.matrix) self.paths = [] self.solutions = [] |

And here’s our test script and results

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
if __name__ == '__main__': setup = ''' from Graph import Graph t = [ [4, 4, 4, 4, 4], [4, 2, 2, 2, 4], [4, 2, 0, 4, 4], [4, 2, 2, 4, 4], [4, 4, 4, 6, 8]] g = Graph() g.from_matrix(t) g.check_for_end() ''' testBrute = ''' g.brute_force() g.reset() ''' testSimplify = ''' g.simplify() g.brute_force() g.reset() ''' its = 1000 repeats = 3 print 'Average of {} iterations, best of {}:'.format(its, repeats) print ' Brute force: {:0.6f}s/iteration'.format( min(timeit.repeat(testBrute, setup=setup, number=its, repeat=repeats))/its) print ' Simplify + brute force: {:0.6f}s/iteration'.format( min(timeit.repeat(testSimplify, setup=setup, number=its, repeat=repeats))/its) |

1 2 3 |
Average of 1000 iterations, best of 3: Brute force: 0.000733s/iteration Simplify + brute force: 0.000497s/iteration |

We’re seeing a reasonably large benefit to simplifying the graph in advance; just brute-forcing takes about 1.5x longer. Let’s add some complexity to our level by placing an additional couple of rows of 4s along the bottom and see how that affects the results.

1 2 3 |
Average of 100 iterations, best of 3: Brute force: 0.016168s/iteration Simplify + brute force: 0.006352s/iteration |

Adding more complexity increased the performance gain to about 2.5x. This is what you’d expect: the more edges in the original graph, the more potential paths you cull by simplifying it. I had to reduce the number of iterations in order to run the test in a reasonable amount of time, but since the difference in results generated between running it for 10 and 100 iterations is negligible, I’m satisfied this hasn’t affected anything.

#### Conclusions

Sadly, I wasn’t able to find a way to solve all the single start-point *Cardinal Chains* levels without resorting to brute force at some point. However, I *was* able to create an algorithm that tangibly speeds up the process of solving them, particularly for large levels with many edges. *Cardinal Chains *has many more levels with multiple start points, that I intend to tackle in a later post. I’d also really like to get my computer to actually *play* the game – that is, read the screen, calculate the solution, then move the mouse to actually implement it. This will require some fun image analysis techniques, so I’m looking forward to doing that, too.

Again, if you fancy playing some *Cardinal Chains*, you can get it here, the app store, or on Google play. Alternatively, if you’d like to play with the Graph class and solving methods I wrote, you can get it here.