# 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.

• Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete) Jan 23 '19 at 21:02
• I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right? Jan 23 '19 at 21:07
• well the simplest tree graphs disprove that
– JMP
Jan 23 '19 at 21:10
• Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs? Jan 23 '19 at 21:12
• I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
– JMP
Jan 23 '19 at 21:16