Name Date Period

← CS Unplugged

CS Unplugged activity

The Swap Puzzle

About 20 minutesSolo, or pair to compare solutionsPencil (coins or scraps of paper help, but pencil marks work fine)

Trial and error can solve this puzzle, eventually, but a good solver does better: they find the shortest way and write it down as an exact list of steps, so anyone could follow it and get the same result. That list is an algorithm. This page has you build one.

How it works

1. Draw a strip of squares like the one below, or use the one printed here. Mark H in the H squares, T in the T squares, and leave the empty square blank.
2. A piece can slide into an empty square right next to it.
3. A piece can also jump over one piece next to it, landing in an empty square just beyond.
4. Swap every H with every T using as few moves as possible.
5. Write your moves as a numbered list, like “square 0 to square 1,” so someone else could follow them without watching you play.

Worked example: 3 squares in 3 moves

0	1	2
H		T

Goal: end up with T, empty, H, the two pieces swapped.

Start

H

T

Done, in 3 moves

T

H

1. Slide the piece in square 0 to square 1.
2. Jump the piece in square 2 over square 1 to square 0.
3. Slide the piece in square 1 to square 2.

Three moves is the fewest possible for this strip. No shorter algorithm exists.

Your turn: 5 squares

0	1	2	3	4
H	H		T	T

Target: swap every H with every T in 8 moves. Write one move per line.

1
2
3
4
5
6
7
8

Check yourself. Play your list back on the strip above, one move at a time. If it really ends with T, T, empty, H, H in 8 moves or fewer, you found the shortest algorithm. If it takes more than 8, it still works, but a faster one exists. Look at your worked example above: the same pattern of slides and jumps, just repeated, gets you there.