I'm sure, positive, that this is a common question and has a known answer but, I do not know how to ask the question in the right way. (If I did, I could probably work out an answer for myself)
For simplicity: We have a checkered game board of, say, $4\times 4$. Assuming one can only go left, right, up, or down, and assuming that one can not go off-board, and assuming that one can go back on one's own moves, how many possible moves/ways are there to cover the board with valid moves?
So, counting valid moves for only one go at a $4\times 4$ board we have: \begin{matrix} 2&3&3&2 \\ 3&4&4&3 \\ 3&4&4&3 \\ 2&3&3&2 \\ \end{matrix} And, more to the question at hand, what is the count for an arbitrarily large $N\times M$ board?