Hamiltonian path in bike-lock graph with $1$ known digit Motivation. My youngest son has a bike lock with dials, and he forgot the unlocking combination completely, except that he remembered that digit $0$ appeared somewhere in the combination. So it was my task to go through all the zillions (but, fortunately, finitely many) possible combinations. Which led to the following problem.
Formal statement. Let $n \geq 2$ be an integer, so we have $n = \{0, \ldots, n-1\}$. For any integer $k>1$ let $$V^0_k = \{x \in n^k: (\exists j\in k)x(j) = 0\}, $$ and let two distinct elements $a\neq b \in V^0_k$ form an edge iff there is $j\in k$ such that

*

*$a(i) = b(i)$ for all $i\in n\setminus\{j\}$, and

*$\{a(j), b(j)\} = \{x, x+1\}$ for some $x\in n-1$, or $\{a(j), b(j)\} = \{0, n-1\}$.

Denote the set of edges by $E_k$.
For what positive integers $k, n$ does the graph $(V^0_k, E_k)$ have a Hamiltonian path? And, if there is a Hamiltonian path, can also a Hamiltonian cycle be found? (The second question doesn't need to be answered for acceptance.)
 A: If $k=2$, then a Hamiltonian path is constructed easily.
In the case $k=3$ and $n\equiv1\pmod2$ a Hamiltonian path is constructed as follows:
\begin{align*}\label{cycle}
   %%%%%%%%%%%%%%% x=0
   & x_1=0\\
   &(0,n-1,n-1)-(0,n-2,n-1)-\ldots-(0,0,n-1)-\\ % z=n-1
  -&(0,0,n-2)-(0,1,n-2)-\ldots-(0,n-1,n-2)-\\  % z=n-2
  -&(0,n-1,n-3)-(0,n-2,n-3)-\ldots-(0,n-1,n-3)-\\  % z=n-3
   &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
  -&(0,0,1)-(0,1,1)-\ldots-(0,n-1,1)-\\ % z=1
  -&(0,n-1,0)-(0,n-2,0)-\ldots-(0,0,0)-\\ % z=0
   %%%%%%%%%%%%%%% z=0,x\neq0
   \\
   & x_3=0,\,x_1\neq0\\
  -&(1,0,0)-(1,1,0)-\ldots-(1,n-1,0)-\\ % x=1
  -&(2,n-1,0)-(2,n-2,0)-\ldots-(2,0,0)-\\ % x=2
   &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
  -&(n-2,0,0)-(n-2,1,0)-\ldots-(n-2,n-1,0)-\\ % x=n-2
  -&(n-1,n-1,0)-(n-1,n-2,0)-\ldots-(n-1,0,0)-\\ % x=n-1
   %%%%%%%%%%%%%%% y=0
   \\
   & x_2=0,x_1\neq0,x_3\neq0\\
  -&(n-1,0,1)-(n-1,0,2)-\ldots-(n-1,0,n-1)-\\ % x=n-1
  -&(n-2,0,n-1)-(n-2,0,n-2)-\ldots-(n-2,0,1)-\\ % x=n-2
   &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
  -&(2,0,n-1)-(2,0,n-2)-\ldots-(2,0,1)-\\ % x=2
  -&(1,0,1)-(1,0,2)-\ldots-(1,0,n-1). % x=1
\end{align*}
In this table, the points are written out in the order they are traversed. The little comments make the table easier to read (I think so).
If $n\equiv0\pmod2$, then the Hamiltonian path is constructed similarly.
It seems to me that in the case $k>3$ the Hamiltonian path can also be constructed in a similar way.
Edit.
I tried to make the above Hamiltonian path more visual. The picture shows all vertices of the two graphs at $n=9$ and $n=10$ and almost all edges. Only edges of type $(0,i,j)-(n-1,i,j)$ are not shown. We see that the Hamiltonian path exists without these edges.

