Paths on Checkerboards – 2
In the Puzzle of the Week “Paths on Checkerboards – 1” we looked at when it was possible, starting at a given point, to make a path on a checkerboard that visited every square. Starting at the black dot, the first 3 by 4 checkerboard has a path and the second 3 by 5 checkerboard does not.
For this puzzle we have both a starting and ending point, and ask the question of whether there is a path that starts at one point and visits every point exactly once on the way to ending at the other point.
THE CHALLENGE
For these two checkerboards, identify which pairs of starting and ending positions have a path that links them that visits every square in the board once, and which ones do not. What is the difference?
EXPLORATION
Create some other sizes of checkerboards and try various starting positions on these. Do you
see any patterns for which starting positions work on each board?
Notes
THE CHALLENGE & EXPLORATION
In “Paths on Checkerboards – 1” we saw that the sequence of colors on a path will alternate as one moves along the path.
As we saw in that earlier puzzle, for checkerboards with an even number of squares, such as the 3 by 4 board, we must end on the opposite color from what we started on. For checkerboards with an odd number of squares, such as the 3 by 5 board, we must begin and end on the color that is in one of the corners of the board.
That leaves the question – If we follow those rules, is that enough?
One way to analyze this question is to set the position of one of the points and see what all the endpoints are for good paths. We can exploit mirror symmetry (flipping around the middle of the board in one direction or the other) to reduce the number of possible cases to look at. Here is what we get for the two boards. The red dot is a fixed starting point, and the black dots are places with successful endpoints.
As you can see, most positions work. For the ones that fail, it is not a matter of having trouble with alternating colors, it is a problem with getting boxed into corners. This confinement problem is even more troublesome for boards with only two rows. For four or more rows, I believe the confinement problems go away.