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?
Improve this question
$\endgroup$
4
  • $\begingroup$ An caterpillar hatches on one corner of a chessboard. Yet your example picks a non-corner square. $\endgroup$
    – CodeNewbie
    Commented Sep 9, 2015 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
    Commented Sep 9, 2015 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
    Commented Sep 9, 2015 at 12:35
  • $\begingroup$ @CodeNewbie Oops, corrected. $\endgroup$
    – Rohcana
    Commented Sep 9, 2015 at 14:50

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Sep 9, 2015 at 11:09
  • 1
    $\begingroup$ @WaKai Unless m and n are both 1 $\endgroup$
    – Joel Rondeau
    Commented Sep 9, 2015 at 12:30
  • $\begingroup$ @JoelRondeau you are right :) $\endgroup$
    – Wa Kai
    Commented Sep 9, 2015 at 13:02
  • $\begingroup$ @WaiKai, That's true, I didn't consider that. I'll mention it. $\endgroup$
    – Ben Frankel
    Commented Sep 9, 2015 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
    Commented Sep 9, 2015 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Was editing it just before your comment. $\endgroup$
    – Nautilus
    Commented Sep 9, 2015 at 12:30
  • 1
    $\begingroup$ Yeah, and it didn't register until after it was posted so I deleted it lol. $\endgroup$
    – Kingrames
    Commented Sep 9, 2015 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.

Improve this answer
$\endgroup$
2
  • 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 ♦
    Commented Sep 9, 2015 at 9:53
  • $\begingroup$ I will think about that next time :). $\endgroup$
    – Tarrom
    Commented Sep 9, 2015 at 10:49

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