# Find a specific path on an n x n grid [duplicate]

Given a puzzle of the following form:

Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.

x  .  .

.  .  .

.  .  x


For a 3 x 3 grid, this yields two solutions:

x--.--.
|
.--.--.
|
.--.--x

x  .--.
|  |  |
.  .  .
|  |  |
.--.  x


There are mul olutions for a 5x5 grid, 7x7, and so on.

But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.

How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)

• This feels like a duplicate question. Jan 23 '19 at 20:32
• Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works. Jan 23 '19 at 20:44
• More specific duplicate might be Can the rook pass every square just once? Jan 23 '19 at 22:40

Imagine the grid as a chessboard. Then for a $$2k\times2k$$ board, the two corners are the same colour, say white. Any path must travel $$WBWB\dots WBW$$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.