Domino Eulerian path problem using backtracking

A Euler path (Eulerian path) is a path in a graph that you visit each edge exactly once. You can visit the same vertex multiple times though. Dominoes is one example of finding Euler path problem. A domino is a game piece that has 2 numbers on it, one number on top and another underneath. Given a set of dominoes, order them so that number on bottom of the domino in front is equal to the number on top of the domino behind.

dominoes euler path

Note dominoes is not an Eulerian circuit in which the start and the end should be the same. Meanwhile, it is undirected. A domino (2,3) is the same as (3,2). It allows duplicated pieces. Traditionally, there are some algorithms to solve Euler path, such as Fleury’s algorithm and Hierholzer’s algorithm. The time complexity is O(E^2) and O(E) respectively. Here we use another method to solve, backtracking.

Actually Hierholzer’s algorithm is using backtracking. When you reach dead end, you return and find another routes. This is the same idea, except here you use recursion. You pick dominoes one by one. Compare itself with the last one. If they match, save it in an output list and remove it from the input set. Then call itself with a smaller set of input. Since the dominoes are undirected, you switch up side down and repeat the same process.

When the recursive function returns, that means this is not a good route. You backtrack by removing the domino piece from the output list and add it back to the input list. On the other hand, if the output list reaches the length of the original input list, that means the function finds a Euler path. You can return from the program. The time complexity is O(E^2).

Using recursive backtracking is a quick brute force solution when you don’t know anything about graph data structure or algorithms in graph. However, it is not efficient. The solution only works fine when the input set is small. Recursive function requires memory space for call stacks. In a case a set is big and there is no Euler path, the recursive function will cause stack overflow.





[1, 1] [3, 1] [2, 1] [1, 3] [2, 2] [1, 2]
[1, 1] [1, 3] [3, 1] [1, 2] [2, 2] [2, 1]

O Notation:
Time complexity: O(E^2), E is number of dominoes
Space complexity: O(E^2)

Download FindDominosChain.js

Comments are closed