8
$\begingroup$

This isn't something I read in a book or anything, it's more of a puzzle I thought up for myself.

However, I am unable to find a solution.

Here's my problem:

If I create a 9x9 checkerboard, and want to walk a path across it, where each block is walked upon only once, and there are only 90° turns, it's easy enough to create any path. (See first image example:)

enter image description here

However, if I want to create an entrance and exit point NEXT TO EACH OTHER, I am stumped. I can't do it:

enter image description here

Can someone help me think of a path ac cross a 9x9 area, where the entrance and exit points are directly next to each other, and yet each block is used only once and only 90° turns are used?

Thanks again.

$\endgroup$
  • 2
    $\begingroup$ From a glance I believe that it is impossible to do, but I have no proof other then just my intuition. $\endgroup$ – Rewan Demontay May 22 at 20:02
  • 1
    $\begingroup$ I also think that it is impossible to do. From the appearance of the problem I think that there will be an elegant mathematical proof $\endgroup$ – Adam May 22 at 20:07
9
$\begingroup$

It’s not possible.

Moving (stepping) only horizontally or vertically (never moving diagonally or jumping over squares), successive steps are always on squares of alternate colors.  For example, in your first illustration, the first step is blue, the second is pink, the third is blue again, and so on.  In general, the odd-numbered steps are blue and the even-numbered steps are pink.

Since both dimensions of your board are odd (9), the total size is odd (9×9=81), and so the last step, the 81st, is an odd number.  Therefore, it must be the same color as the first square (as seen in your first illustration).  And, since adjacent (next-to-each-other) squares are always different colors, the exit square on an odd-sized board cannot be next to the entrance square.

$\endgroup$
  • $\begingroup$ Thanks. I guessed so, but I wasn't sure. Thanks for confirming it! $\endgroup$ – etsnyman May 22 at 20:39
  • 2
    $\begingroup$ The start and end squares must also both be blue, since there are one more blue square in total. $\endgroup$ – Kruga May 23 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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