Consider a $3\times 3$ grid with numbers $1$ to $9$ filled in order (i.e $1$ to $3$ in the first row and so on). Now, given an integer $m$ and another integer $k$, I need to find the number of ways to visit $k$ squares beginning from the square containing $m$ with the constraint being that I can move only to the adjacent squares and a square can be visited more than once.
I have solved a similar problem with the constraint of only moving to either right or downwards beginning from one of the corners by simply adding the number of ways to visit the previous adjacent squares but I am finding it hard to arrive at a solution to the above problem.
I would be grateful if you could help me solve the above problem.
Treat the grid as a graph with $n=9$ vertices. Let $A=\left(a_{ij}\right)_{n\times n}$ be the adjacency matrix of the graph. That is, ${a_{ij}}=1$ if vertices $i$ and $j$ are adjacent, and $0$ if they are not. Now consider $A^2=\left(b_{ij}\right)_{n\times n}$. We have $$b_{ij}=\sum_{k=1}^n a_{ik}a_{kj},$$ and we see that $b_{ij}$ is the number of paths of length $2$ from $i$ to $j$. In a similar way, if $A^k=\left(c_{ij}\right)_{n\times n}$, then $c_{mj}$ is the number of paths of length $k$ from vertex $m$ to vertex $j$.
So to answer your question, compute $A^k$ and add up all the elements in row $m$.