3
$\begingroup$

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Danny Yaroslavski Jan 23 at 21:02
  • $\begingroup$ 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? $\endgroup$ – Danny Yaroslavski Jan 23 at 21:07
  • $\begingroup$ well the simplest tree graphs disprove that $\endgroup$ – JMP Jan 23 at 21:10
  • $\begingroup$ 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? $\endgroup$ – Danny Yaroslavski Jan 23 at 21:12
  • $\begingroup$ 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. $\endgroup$ – JMP Jan 23 at 21:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.