3
$\begingroup$

An caterpillar hatches on one corner of a checkerboard. At every second, it moves from one square to another adjacent (sharing a side) one. However, it can not return to any cell it has visited before except the starting cell. The caterpillar wishes to visit every cell of the board exactly once and then return to the starting square.

For example for a $4 \times 4$ board one possible path for the caterpillar is:

enter image description here


  • Can the caterpillar do so in $8 \times 8$ board?
  • Can the caterpillar do so in $7 \times 7$ board?
  • Can you generalize for a $m \times n$ board?
$\endgroup$
  • $\begingroup$ An caterpillar hatches on one corner of a chessboard. Yet your example picks a non-corner square. $\endgroup$ – CodeNewbie Sep 9 '15 at 4:48
  • 1
    $\begingroup$ @CodeNewbie, You're right, but technically if you have a loop that covers every square, it doesn't matter where it "starts". $\endgroup$ – Ben Frankel Sep 9 '15 at 4:58
  • $\begingroup$ Incidentally there are 192 paths for that 4x4 board. They are shaped like: C, U, n, and backwards c, along with H and uppercase i with hat and feet (this font shows uppercase i as just a vertical bar). For each of the six shapes you can start at one of the 16 points and go clockwise or counterclockwise, for 6 x 16 x 2 = 192 total path solutions. (Cue the "The More You Know" jingle) $\endgroup$ – Kingrames Sep 9 '15 at 12:35
  • $\begingroup$ @CodeNewbie Oops, corrected. $\endgroup$ – Rohcana Sep 9 '15 at 14:50
19
$\begingroup$

Let's just go straight to the $m\times n$ board.

If $n$ is even, start in the bottom left corner. Go up all the way, right 1, down almost all the way (just 1 block from the bottom), right 1, up all the way, and so on. As we are going up at column 1 and we are alternating between up and down, at column $n$ we will be going down. This time go all the way down and then all the way left.

Otherwise if $m$ is even, rotate the rectangle 90 degrees and do the algorithm above.

Otherwise $n$ is odd and $m$ is odd. If we color the board black and white in a checkerboard pattern, each move to an adjacent square will alternate between black and white. In position 1 we are on a black square, so in position $n\cdot m + 1$ we should be on a white square. But in a tour of the board both of those positions should be the bottom left corner and the same color. Thus we cannot tour the board.

EDIT: In the above, $m$ and $n$ should both be greater than 1 (notes Wa Kai). If one of $n$ and $m$ is 1 while the other is greater than $2$, it is obviously impossible. If the other is 2 it is possible (notes Darrel Hoffman).

The case of $1\times1$ might be up for debate, but I would argue that it is impossible. An allowed move is to an adjacent square, so there are no possible moves and thus nothing can happen.

$\endgroup$
  • $\begingroup$ Very nice answer! You should consider to say that m and n must be > 2. For m or n = 1 it is not solvable, no matter if the other is odd or even $\endgroup$ – Wa Kai Sep 9 '15 at 11:09
  • 1
    $\begingroup$ @WaKai Unless m and n are both 1 $\endgroup$ – Joel Rondeau Sep 9 '15 at 12:30
  • $\begingroup$ @JoelRondeau you are right :) $\endgroup$ – Wa Kai Sep 9 '15 at 13:02
  • $\begingroup$ @WaiKai, That's true, I didn't consider that. I'll mention it. $\endgroup$ – Ben Frankel Sep 9 '15 at 13:29
  • $\begingroup$ Actually, m=1, n=2 or the reverse is also still possible if you want to be complete. How about - if either m or n is 1, then the other must be no more than 2? $\endgroup$ – Darrel Hoffman Sep 9 '15 at 14:42
1
$\begingroup$

It's not possible if there are an odd number of squares, because when we paint them like a checkerboard, the last move must lead to a square of the same color as the first one, with the color changing every move. However, then the number of moves must be odd, which is a contradiction. When it's even, it's always possible.

$\endgroup$
  • $\begingroup$ Was editing it just before your comment. $\endgroup$ – Nautilus Sep 9 '15 at 12:30
  • 1
    $\begingroup$ Yeah, and it didn't register until after it was posted so I deleted it lol. $\endgroup$ – Kingrames Sep 9 '15 at 12:31
-1
$\begingroup$

I am new here, but I want to give it a shot!

Isn't it just as simple as: As long as either m or n mod 2 == 0, it is possible? Of course this is only applicable for squares and rectangles only.

Edit: So I also figured over lunch that my answer was Incorrect. When you enter the values in a scenario where either n or m == 1. Sadly the caterpillar is stuck.

$\endgroup$
  • 2
    $\begingroup$ Hey, welcome to Puzzling.SE! Yes, that's correct, but generally here we like to see explanation for why an answer is correct. Most of the time, answers without explanation will be deleted. $\endgroup$ – Deusovi Sep 9 '15 at 9:53
  • $\begingroup$ I will think about that next time :). $\endgroup$ – Tarrom Sep 9 '15 at 10:49

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.