Imagine a prison consisting of 64 cells arranged like the squares of an 8-by-8 chessboard. There are doors between all adjoining cells. A prisoner in one of the corner cells is told that he will be released, provided he can get into the diagonally opposite corner cell after passing through every other cell exactly once. Can the prisoner obtain his freedom?
This problem is provided in Richard A. Brauldi's book on Introductory combinatorics. I took my time tackling the problem on my own. First of all, I tried to solve it, of course. After a few tries I conjectured it to be impossible. Then, I wondered how exactly I could rigorously prove it. The hard part was constructing an appropriate mathematical model of the situation. What comes first to mind is the $8\times8$ chessboard. Since any pathway that the prisoner can take can be represented by perfectly covering the board by dominoes, then the problem can be concluded impossible if there exist no tilings (perfect covers) for the board by dominoes. Unfortunately, there, of course, are perfect covers by dominoes for an $8\times8$ board. This is due to the fact that while all pathways do indeed correspond to a tiling, not all tilings correspond to a path. I then thought of making a model more specific to the problem. If we cut the cell that the prisinor initially begins in, and also the cell that is his final destination. Now, tiling this mutilated board with dominoes is impossible, for each domino will cover $1$ white and $1$ black square; if we cut two squares diagonally opposite each other, we will have cut 2 squares of the same color, and hence have $32$ black and $30$ white squares. This unevenness deems it impossible for dominoes to form a perfect cover.
The only problem in my reasoning is: how do I show that any path the prisoner traces corresponds to a tiling of the mutilated chessboard and that any tiling of the mutilated chessboard corresponds to a path that the prisoner traces? Moreover, how are such problems usually solved? Thank you in advance.