Cracking the Safe - Core idea

Core idea: Same as De Bruijn sequence, but with alphabet $\{0, 1,., k-1\}$.

Graph construction:

• $k^{n-1}$ vertices (each is an $(n-1)$-digit string)
• $k^n$ edges (each is an $n$-digit string)
• Vertex has $k$ outgoing edges (append $0, 1,., k-1$)
• Each vertex has in-degree $=$ out-degree $= k$

Euler circuit exists: All vertices have equal in/out degrees.

The result string has length $k^n + n - 1$.