Princeton University
|
Computer Science 345 |
|
Fifteen Puzzle
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 Fifteen numbers from 1 to 15 are written on a 4x4 board, so that the last square is empty (see the picture). Notice that the numbers 14 and 15 are in the wrong order. Every move you can shift any number to the adjacent square, if this square is empty. Your goal is to order all numbers (including 14 and 15). Can you do this? Can you prove that this is impossible? You can play this puzzle online: just click on the number you want to move in the picture.
PuzzleInitially, there are two tokens in a row; the left one is blue and the right one is red. You can change the configuration by performing a number of moves. In each move, you can either insert two successive tokens of the same color (red or blue) or remove two successive tokens of the same color. Is it possible to produce a configuration where there are exactly two tokens, the left token being red, and the right one being blue?
Initial configuration: Final configuration:
