Games have inspired mathematical puzzles since people began playing them. A puzzle is a kind of solitaire, after all. Today, I’d like to explore a few puzzles that are inspired by checkers. Only loosely inspired, however: there are no kings, no taking other pieces, and no diagonal movement. There are two colours of checkers, though, and there is jumping.
Your goal in these puzzles is to switch the red and black checkers. Red can either slide one space to the left, or jump left over a checker. Black moves right, either by sliding one space or by jumping. Checkers can only move to vacant spaces.
For example, it takes just three moves to switch one black and one red checker.
It takes, as you can check, 8 moves to switch two black checkers with two red checkers.
But be careful: it is possible to hit a dead end as you try to solve the puzzle, like this one.
Puzzle 1.
Find a way to switch three black and three red checkers. How many moves does it take?
Puzzle 2.
How many moves does it take to switch four black and four red checkers?
Research. Can you find a general formula for the number of moves it takes to switch n black and n red checkers, on a line with 2 n + 1 spots (so there is just one vacant spot in the center).
Puzzle 3.
Let's extend this puzzle into two dimensions! Find a way switch the black and red checkers now, assuming the same rules; here the red checkers must move left or up, and the black checkers must move right or down. How many moves does it take to complete the puzzle?
Solutions:
Puzzle 1.
It takes 15 moves to switch the three red with the three black checkers. It can be somewhat tricky to actually perform the moves that make the switch happen, and easy to run into dead ends. Therefore, I want to start with an argument that proves it will take 15 moves if it can be done.
Consider any one of these checkers, and imagine how it would fair on a board by itself. Individually each one needs to travel exactly four spots to get home. With 6 pieces, that would require 6 x 4 = 24 moves.
But we're forgetting about the jumps! Is there some way to predict the number of jumps to expect? The answer is yes: every time a red checker and a black checker meet, there will be exactly one jump: either red jumps black or black jumps red. So how many jumps should we expect? Each red checker must meet each black checker to get to its end spot, so that is 3 x 3 meetings. Each jump moves a checker two spaces instead of one, which means they each save us one move. So the total should be 24 - 9 = 15 moves.
Of course, this argument doesn't tell you how to solve the puzzle, or even that you can solve the puzzle. Still, it's quite powerful, since it allows us a framework to generalize, and essentially solve all the problems.
For example, for puzzle 2, with 4 black and 4 red checkers, each check needs to move 5 spaces, and there will be 4 x 4 jumps. That gives (8 x 5) - (4 x 4) = 24 moves. We can generalize this calculation to any number of checkers.
Let C = the number of red checkers. Then each checker needs to travel C + 1 spaces, and there are 2C checkers (C red + C black). Any pair of checkers will meet once and create one jump, that that’s C x C jumps.
This means the total number of moves is:
(the number of checkers) x (the space each checker needs to travel) - (the number of jumps)
=2C x (C+1) - (C x C).
If you do a little algebra, this simplifies to C^2 + 2C, or C x (C + 2).
That’s all wonderful, but can the problems actually be done? The answer is yes, and there’s a nice structure to the ordering of moves as well. Here are instructions to solve each puzzle. Note that after the first move, I don't need to specify which color moves; I just need to say whether the move is a slide (S) or a jump (J). So assume that black moves first, and see what you notice about the solutions below.
Puzzle 1.
SJSJJSJJJSJJSJS
Puzzle 2
SJSJJSJJJSJJJJSJJJSJJSJS
Lo and behold, there’s a tidy pattern here as well. It might be easier to see if I abbreviate how many jumps happen in a row with a number. So instead of JJJ I’ll just write 3.
Then the answer to puzzle 1 is S1S2S3S2S1S
And the answer to puzzle 2 is S1S2S3S4S3S2S1S
The jumps increase from 1 to the number of checkers, and then back to 1. Keep this pattern going and you’re got a recipe to solve a checker puzzle of any length.
What about two dimensions then? This problem is surprisingly tractable if you observe one thing: we already know how to solve the 1-D version in the middle (circles below), and if that middle horizontal line was clear, we could solve all the vertical lines as well. After all, each column is the same 1-D puzzle again as well!
This gives us the key to complete the puzzle. Solve the middle row, and when a gap opens up in column, solve that column. So solve the middle column first (8 moves), then slide a black forward in the middle row. Then solve the 2nd column now that you have a gap, and so on. In the end, you’ll just be solving 6 versions of the 1-D puzzle, which will take 6 x 8 = 48 moves.
Of course, you don't have to stop there! You can find a formula to solve larger versions of this square puzzle, or take these puzzles to cubes and beyond! But I’ll sign off for now. Till next time, happy puzzling!
