# 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?)

## marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, GlorfindelJan 24 at 6:56

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.