Longest sequence of dominoes Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the same as $\langle 0, 3\rangle$.
A sequence of length $n$ of dominoes is a sequence $(d_0, d_1, …, d_{n-1})$ where $d_i = \langle a_i, b_i\rangle$ is a domino, and $\forall i \in [\![0, n-2]\!], b_i = a_{i+1}$. For example, $\langle 2,3\rangle\langle 3,5\rangle\langle 5,2\rangle\langle 2,1\rangle$ is a sequence of length 4.
Given $k$ and $N$, and a set $S$ of $N$ distincts $k$-dominoes, I want to find the longest sequence of dominoes constructible using each domino in the set $S$ at most once.
My ideas so far are to use some kind of backtracking algorithm: I try to complete a sequence of dominoes with a new domino – among those not used, or not eliminated – and if it is valid, I continue; if there is no valid domino, I delete and elimininate the last domino to try again. I am using hash table to keep track of the remaining dominoes.
I wondered if there is a more efficient/elegant way to do it, maybe by pre-sorting the set $S$ before trying to construct sequences of dominoes, or using dynamic programming in a way I haven't found yet.
I also thought of constructing a graph with each domino as a vertex, but I don't really know how to put edges because of the two faces of the domino: if I add an edge between two dominoes that have a common value, then I risk to find $\langle 1,2\rangle\langle 2,3\rangle\langle 2,0\rangle$ as a valid sequence…
One of the ideas proposed in the comments is to construct a graph where vertices are integers of $[\![0,k-1]\!]$ and edges are dominoes of $S$ (domino $\langle a , b\rangle$ is an edge between $a$ and $b$, possibly a loop if $a = b$). The question is now equivalent to finding a longest path in this graph. The problem is that it is not similar to longest path problem because the path are not necessarily simples (meaning a path can cross the same vertex multiple times). One would need to keep track of used edges to find the longest path, so it does not really simplify the problem.
The problem is difficult and seems even $NP$-hard, but I still want to find an efficient algorithm solving it. My current backtracking solution find the answer for $k = 20$ and $N = 30$ in 10 sec (for a randomly generated set of distinct dominoes), but it increases quickly if I lower the value of $k$ or increase the value of $N$ (even $k = 15$ and $N = 30$ is taking ~30 minutes).
Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of degree at most $2$ (the problem remains hard in this case).
W.l.o.g., let $V=\{3,\dots,k-4\}$, $s=3$, and $t=k-4$.
Create the dominoes $(0,1)$, $(1,2)$, $(2,3)$, $(k-4, k-3)$, $(k-3, k-2)$, and $(k-2, k-1)$. Create one &quot;edge&quot; domino $(a,b)$ for each edge $(a,b) \in E$.
There exists an Hamiltonian path in $G$ if and only if there is a sequence of $k-1$ dominoes.
Indeed, notice that any sequence of dominoes that only uses the dominoes from $E$ traces a (not-necessarily simple) path $P$ in $G$.
But then, all vertices except the endpoints of $P$ must be traversed at most once (since their degree is at most $3$). The two endpoints can extend the path by at most $2$. Then the number of edges of $P$ can be at most $|V|+1 = k-6+1 = k-5$. This implies that a sequence of $k-1$ dominoes must use all &quot;non-edge&quot; dominoes, i.e., the sequence of dominoes must start with $(0,1), \dots, (2,3)$ and end with $(k-4, k-4), \dots, (k-2, k-1)$.
Then, the path induced by the sub-sequence obtained by dropping the &quot;non-edge&quot; dominoes must be simple and traverses $k-1-6 = k-7 = |V|-1$ edges of $G$, i.e., it is an Hamiltonian path in $G$.
Conversely, we can create a sequence of $\ell+6$ dominoes from any simple path of length $\ell$ from $s$ to $t$ in $G$ (simply prepend $(0,1), \dots, (2,3)$ and append  $(k-4, k-4), \dots, (k-2, k-1)$). For an Hamiltoniam path we have $\ell=|V|-1=k-7$, therefore the sequence has length $k-1$.