Suppose we have an $n$ by $n$ square checkerboard with a game piece in one corner, and at each move, we can move it to a square adjacent to its current square. How many paths are there taking the piece to the opposite corner that visit each square of the board exactly once?
I know that this problem could be solved algorithmically for each value of $n$, and writing a program for this would likely not be difficult. However, if I wanted to approach this problem combinatorically, how would I do it? I would start by superimposing the board on top of a coordinate plane... but where would I go from there? I have no idea how to find the number of paths that don't leave the board, and I also don't know how to exclude the paths in which the piece ends up getting trapped in a corner where it cannot move to any square which it has not already visited. I have no idea how to approach this. Please help!
I think this is a hard problem, and the exact values don't seem to be known for large $n$.
However, you can use a parity argument to handle the even $n$ cases.