Solving Dad's Puzzle: Overview
Dad's Puzzle is a traditional 4×5 sliding puzzle where the objective is
to slide the largest piece to the lower left corner of the puzzle board.
It dates back to the early 20th century. The shortest solution consists
of 83 moves from the starting position (a move of length 2 is considered
two moves, not one). The puzzle was recently mentioned on Slashdot and The
Economist.
Try an interactive version
(apparently requires IE).
The python program below solves the puzzle by iterating all possible positions
from the starting position in a breadth-first search. It stops when the 2x2 block
has reached the target position. Since each iteration inspects all possible positions
up to that point, the first solution found is guaranteed to be the shortest one.
The program's output consists of a series of diagrams that show the solution
as a sequence of moves.
Program Output
Number of end-points: 3 (depth: 1), positions seen: 3 Number of end-points: 6 (depth: 2), positions seen: 9 Number of end-points: 4 (depth: 3), positions seen: 13 Number of end-points: 3 (depth: 4), positions seen: 16 Number of end-points: 3 (depth: 5), positions seen: 19 Number of end-points: 3 (depth: 6), positions seen: 22 Number of end-points: 2 (depth: 7), positions seen: 24 Number of end-points: 2 (depth: 8), positions seen: 26 Number of end-points: 3 (depth: 9), positions seen: 29 Number of end-points: 7 (depth: 10), positions seen: 36 Number of end-points: 10 (depth: 11), positions seen: 46 Number of end-points: 10 (depth: 12), positions seen: 56 Number of end-points: 9 (depth: 13), positions seen: 65 Number of end-points: 6 (depth: 14), positions seen: 71 Number of end-points: 7 (depth: 15), positions seen: 78 Number of end-points: 7 (depth: 16), positions seen: 85 Number of end-points: 7 (depth: 17), positions seen: 92 Number of end-points: 7 (depth: 18), positions seen: 99 Number of end-points: 7 (depth: 19), positions seen: 106 Number of end-points: 7 (depth: 20), positions seen: 113 Number of end-points: 5 (depth: 21), positions seen: 118 Number of end-points: 4 (depth: 22), positions seen: 122 Number of end-points: 2 (depth: 23), positions seen: 124 Number of end-points: 4 (depth: 24), positions seen: 128 Number of end-points: 6 (depth: 25), positions seen: 134 Number of end-points: 8 (depth: 26), positions seen: 142 Number of end-points: 10 (depth: 27), positions seen: 152 Number of end-points: 12 (depth: 28), positions seen: 164 Number of end-points: 10 (depth: 29), positions seen: 174 Number of end-points: 12 (depth: 30), positions seen: 186 Number of end-points: 16 (depth: 31), positions seen: 202 Number of end-points: 16 (depth: 32), positions seen: 218 Number of end-points: 14 (depth: 33), positions seen: 232 Number of end-points: 14 (depth: 34), positions seen: 246 Number of end-points: 20 (depth: 35), positions seen: 266 Number of end-points: 26 (depth: 36), positions seen: 292 Number of end-points: 34 (depth: 37), positions seen: 326 Number of end-points: 36 (depth: 38), positions seen: 362 Number of end-points: 28 (depth: 39), positions seen: 390 Number of end-points: 30 (depth: 40), positions seen: 420 Number of end-points: 36 (depth: 41), positions seen: 456 Number of end-points: 38 (depth: 42), positions seen: 494 Number of end-points: 50 (depth: 43), positions seen: 544 Number of end-points: 44 (depth: 44), positions seen: 588 Number of end-points: 34 (depth: 45), positions seen: 622 Number of end-points: 42 (depth: 46), positions seen: 664 Number of end-points: 50 (depth: 47), positions seen: 714 Number of end-points: 50 (depth: 48), positions seen: 764 Number of end-points: 50 (depth: 49), positions seen: 814 Number of end-points: 56 (depth: 50), positions seen: 870 Number of end-points: 50 (depth: 51), positions seen: 920 Number of end-points: 44 (depth: 52), positions seen: 964 Number of end-points: 42 (depth: 53), positions seen: 1006 Number of end-points: 46 (depth: 54), positions seen: 1052 Number of end-points: 58 (depth: 55), positions seen: 1110 Number of end-points: 66 (depth: 56), positions seen: 1176 Number of end-points: 60 (depth: 57), positions seen: 1236 Number of end-points: 58 (depth: 58), positions seen: 1294 Number of end-points: 64 (depth: 59), positions seen: 1358 Number of end-points: 78 (depth: 60), positions seen: 1436 Number of end-points: 90 (depth: 61), positions seen: 1526 Number of end-points: 106 (depth: 62), positions seen: 1632 Number of end-points: 92 (depth: 63), positions seen: 1724 Number of end-points: 82 (depth: 64), positions seen: 1806 Number of end-points: 76 (depth: 65), positions seen: 1882 Number of end-points: 82 (depth: 66), positions seen: 1964 Number of end-points: 96 (depth: 67), positions seen: 2060 Number of end-points: 118 (depth: 68), positions seen: 2178 Number of end-points: 142 (depth: 69), positions seen: 2320 Number of end-points: 146 (depth: 70), positions seen: 2466 Number of end-points: 128 (depth: 71), positions seen: 2594 Number of end-points: 138 (depth: 72), positions seen: 2732 Number of end-points: 172 (depth: 73), positions seen: 2904 Number of end-points: 186 (depth: 74), positions seen: 3090 Number of end-points: 158 (depth: 75), positions seen: 3248 Number of end-points: 134 (depth: 76), positions seen: 3382 Number of end-points: 120 (depth: 77), positions seen: 3502 Number of end-points: 144 (depth: 78), positions seen: 3646 Number of end-points: 160 (depth: 79), positions seen: 3806 Number of end-points: 162 (depth: 80), positions seen: 3968 Number of end-points: 172 (depth: 81), positions seen: 4140 Number of end-points: 174 (depth: 82), positions seen: 4314 Number of end-points: 172 (depth: 83), positions seen: 4486 Solution found in 83 moves -------------------- | A | A | B | B | -------------------- | A | A | C | C | -------------------- | D | E | | | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 1: E Right -------------------- | A | A | B | B | -------------------- | A | A | C | C | -------------------- | D | | E | | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 2: D Right -------------------- | A | A | B | B | -------------------- | A | A | C | C | -------------------- | | D | E | | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 3: E Right -------------------- | A | A | B | B | -------------------- | A | A | C | C | -------------------- | | D | | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 4: D Right -------------------- | A | A | B | B | -------------------- | A | A | C | C | -------------------- | | | D | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 5: A Down -------------------- | | | B | B | -------------------- | A | A | C | C | -------------------- | A | A | D | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 6: B Left -------------------- | | B | B | | -------------------- | A | A | C | C | -------------------- | A | A | D | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 7: B Left -------------------- | B | B | | | -------------------- | A | A | C | C | -------------------- | A | A | D | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 8: C Up -------------------- | B | B | C | C | -------------------- | A | A | | | -------------------- | A | A | D | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 9: D Up -------------------- | B | B | C | C | -------------------- | A | A | D | | -------------------- | A | A | | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 10: D Right -------------------- | B | B | C | C | -------------------- | A | A | | D | -------------------- | A | A | | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 11: A Right -------------------- | B | B | C | C | -------------------- | | A | A | D | -------------------- | | A | A | E | -------------------- | F | G | H | H | -------------------- | F | G | I | I | -------------------- 12: F Up -------------------- | B | B | C | C | -------------------- | | A | A | D | -------------------- | F | A | A | E | -------------------- | F | G | H | H | -------------------- | | G | I | I | -------------------- 13: F Up -------------------- | B | B | C | C | -------------------- | F | A | A | D | -------------------- | F | A | A | E | -------------------- | | G | H | H | -------------------- | | G | I | I | -------------------- 14: G Left -------------------- | B | B | C | C | -------------------- | F | A | A | D | -------------------- | F | A | A | E | -------------------- | G | | H | H | -------------------- | G | | I | I | -------------------- 15: H Left -------------------- | B | B | C | C | -------------------- | F | A | A | D | -------------------- | F | A | A | E | -------------------- | G | H | H | | -------------------- | G | | I | I | -------------------- 16: E Down -------------------- | B | B | C | C | -------------------- | F | A | A | D | -------------------- | F | A | A | | -------------------- | G | H | H | E | -------------------- | G | | I | I | -------------------- 17: D Down -------------------- | B | B | C | C | -------------------- | F | A | A | | -------------------- | F | A | A | D | -------------------- | G | H | H | E | -------------------- | G | | I | I | -------------------- 18: I Left -------------------- | B | B | C | C | -------------------- | F | A | A | | -------------------- | F | A | A | D | -------------------- | G | H | H | E | -------------------- | G | I | I | | -------------------- 19: E Down -------------------- | B | B | C | C | -------------------- | F | A | A | | -------------------- | F | A | A | D | -------------------- | G | H | H | | -------------------- | G | I | I | E | -------------------- 20: D Down -------------------- | B | B | C | C | -------------------- | F | A | A | | -------------------- | F | A | A | | -------------------- | G | H | H | D | -------------------- | G | I | I | E | -------------------- 21: A Right -------------------- | B | B | C | C | -------------------- | F | | A | A | -------------------- | F | | A | A | -------------------- | G | H | H | D | -------------------- | G | I | I | E | -------------------- 22: F Right -------------------- | B | B | C | C | -------------------- | | F | A | A | -------------------- | | F | A | A | -------------------- | G | H | H | D | -------------------- | G | I | I | E | -------------------- 23: G Up -------------------- | B | B | C | C | -------------------- | | F | A | A | -------------------- | G | F | A | A | -------------------- | G | H | H | D | -------------------- | | I | I | E | -------------------- 24: G Up -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | | H | H | D | -------------------- | | I | I | E | -------------------- 25: H Left -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | H | H | | D | -------------------- | | I | I | E | -------------------- 26: D Left -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | H | H | D | | -------------------- | | I | I | E | -------------------- 27: E Up -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | H | H | D | E | -------------------- | | I | I | | -------------------- 28: I Right -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | H | H | D | E | -------------------- | | | I | I | -------------------- 29: H Down -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | | | D | E | -------------------- | H | H | I | I | -------------------- 30: D Left -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | | D | | E | -------------------- | H | H | I | I | -------------------- 31: D Left -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | D | | | E | -------------------- | H | H | I | I | -------------------- 32: E Left -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | D | | E | | -------------------- | H | H | I | I | -------------------- 33: E Left -------------------- | B | B | C | C | -------------------- | G | F | A | A | -------------------- | G | F | A | A | -------------------- | D | E | | | -------------------- | H | H | I | I | -------------------- 34: A Down -------------------- | B | B | C | C | -------------------- | G | F | | | -------------------- | G | F | A | A | -------------------- | D | E | A | A | -------------------- | H | H | I | I | -------------------- 35: C Down -------------------- | B | B | | | -------------------- | G | F | C | C | -------------------- | G | F | A | A | -------------------- | D | E | A | A | -------------------- | H | H | I | I | -------------------- 36: B Right -------------------- | | B | B | | -------------------- | G | F | C | C | -------------------- | G | F | A | A | -------------------- | D | E | A | A | -------------------- | H | H | I | I | -------------------- 37: B Right -------------------- | | | B | B | -------------------- | G | F | C | C | -------------------- | G | F | A | A | -------------------- | D | E | A | A | -------------------- | H | H | I | I | -------------------- 38: F Up -------------------- | | F | B | B | -------------------- | G | F | C | C | -------------------- | G | | A | A | -------------------- | D | E | A | A | -------------------- | H | H | I | I | -------------------- 39: E Up -------------------- | | F | B | B | -------------------- | G | F | C | C | -------------------- | G | E | A | A | -------------------- | D | | A | A | -------------------- | H | H | I | I | -------------------- 40: D Right -------------------- | | F | B | B | -------------------- | G | F | C | C | -------------------- | G | E | A | A | -------------------- | | D | A | A | -------------------- | H | H | I | I | -------------------- 41: G Down -------------------- | | F | B | B | -------------------- | | F | C | C | -------------------- | G | E | A | A | -------------------- | G | D | A | A | -------------------- | H | H | I | I | -------------------- 42: F Left -------------------- | F | | B | B | -------------------- | F | | C | C | -------------------- | G | E | A | A | -------------------- | G | D | A | A | -------------------- | H | H | I | I | -------------------- 43: E Up -------------------- | F | | B | B | -------------------- | F | E | C | C | -------------------- | G | | A | A | -------------------- | G | D | A | A | -------------------- | H | H | I | I | -------------------- 44: D Up -------------------- | F | | B | B | -------------------- | F | E | C | C | -------------------- | G | D | A | A | -------------------- | G | | A | A | -------------------- | H | H | I | I | -------------------- 45: E Up -------------------- | F | E | B | B | -------------------- | F | | C | C | -------------------- | G | D | A | A | -------------------- | G | | A | A | -------------------- | H | H | I | I | -------------------- 46: D Up -------------------- | F | E | B | B | -------------------- | F | D | C | C | -------------------- | G | | A | A | -------------------- | G | | A | A | -------------------- | H | H | I | I | -------------------- 47: G Right -------------------- | F | E | B | B | -------------------- | F | D | C | C | -------------------- | | G | A | A | -------------------- | | G | A | A | -------------------- | H | H | I | I | -------------------- 48: F Down -------------------- | | E | B | B | -------------------- | F | D | C | C | -------------------- | F | G | A | A | -------------------- | | G | A | A | -------------------- | H | H | I | I | -------------------- 49: E Left -------------------- | E | | B | B | -------------------- | F | D | C | C | -------------------- | F | G | A | A | -------------------- | | G | A | A | -------------------- | H | H | I | I | -------------------- 50: B Left -------------------- | E | B | B | | -------------------- | F | D | C | C | -------------------- | F | G | A | A | -------------------- | | G | A | A | -------------------- | H | H | I | I | -------------------- 51: F Down -------------------- | E | B | B | | -------------------- | | D | C | C | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 52: E Down -------------------- | | B | B | | -------------------- | E | D | C | C | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 53: B Left -------------------- | B | B | | | -------------------- | E | D | C | C | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 54: C Up -------------------- | B | B | C | C | -------------------- | E | D | | | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 55: D Right -------------------- | B | B | C | C | -------------------- | E | | D | | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 56: D Right -------------------- | B | B | C | C | -------------------- | E | | | D | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 57: E Right -------------------- | B | B | C | C | -------------------- | | E | | D | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 58: E Right -------------------- | B | B | C | C | -------------------- | | | E | D | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 59: B Down -------------------- | | | C | C | -------------------- | B | B | E | D | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 60: C Left -------------------- | | C | C | | -------------------- | B | B | E | D | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 61: D Up -------------------- | | C | C | D | -------------------- | B | B | E | | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 62: E Right -------------------- | | C | C | D | -------------------- | B | B | | E | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 63: B Right -------------------- | | C | C | D | -------------------- | | B | B | E | -------------------- | F | G | A | A | -------------------- | F | G | A | A | -------------------- | H | H | I | I | -------------------- 64: F Up -------------------- | | C | C | D | -------------------- | F | B | B | E | -------------------- | F | G | A | A | -------------------- | | G | A | A | -------------------- | H | H | I | I | -------------------- 65: F Up -------------------- | F | C | C | D | -------------------- | F | B | B | E | -------------------- | | G | A | A | -------------------- | | G | A | A | -------------------- | H | H | I | I | -------------------- 66: G Left -------------------- | F | C | C | D | -------------------- | F | B | B | E | -------------------- | G | | A | A | -------------------- | G | | A | A | -------------------- | H | H | I | I | -------------------- 67: A Left -------------------- | F | C | C | D | -------------------- | F | B | B | E | -------------------- | G | A | A | | -------------------- | G | A | A | | -------------------- | H | H | I | I | -------------------- 68: E Down -------------------- | F | C | C | D | -------------------- | F | B | B | | -------------------- | G | A | A | E | -------------------- | G | A | A | | -------------------- | H | H | I | I | -------------------- 69: D Down -------------------- | F | C | C | | -------------------- | F | B | B | D | -------------------- | G | A | A | E | -------------------- | G | A | A | | -------------------- | H | H | I | I | -------------------- 70: C Right -------------------- | F | | C | C | -------------------- | F | B | B | D | -------------------- | G | A | A | E | -------------------- | G | A | A | | -------------------- | H | H | I | I | -------------------- 71: E Down -------------------- | F | | C | C | -------------------- | F | B | B | D | -------------------- | G | A | A | | -------------------- | G | A | A | E | -------------------- | H | H | I | I | -------------------- 72: D Down -------------------- | F | | C | C | -------------------- | F | B | B | | -------------------- | G | A | A | D | -------------------- | G | A | A | E | -------------------- | H | H | I | I | -------------------- 73: B Right -------------------- | F | | C | C | -------------------- | F | | B | B | -------------------- | G | A | A | D | -------------------- | G | A | A | E | -------------------- | H | H | I | I | -------------------- 74: F Right -------------------- | | F | C | C | -------------------- | | F | B | B | -------------------- | G | A | A | D | -------------------- | G | A | A | E | -------------------- | H | H | I | I | -------------------- 75: G Up -------------------- | | F | C | C | -------------------- | G | F | B | B | -------------------- | G | A | A | D | -------------------- | | A | A | E | -------------------- | H | H | I | I | -------------------- 76: G Up -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | | A | A | D | -------------------- | | A | A | E | -------------------- | H | H | I | I | -------------------- 77: A Left -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | A | A | | D | -------------------- | A | A | | E | -------------------- | H | H | I | I | -------------------- 78: D Left -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | A | A | D | | -------------------- | A | A | | E | -------------------- | H | H | I | I | -------------------- 79: E Up -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | A | A | D | E | -------------------- | A | A | | | -------------------- | H | H | I | I | -------------------- 80: I Up -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | A | A | D | E | -------------------- | A | A | I | I | -------------------- | H | H | | | -------------------- 81: H Right -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | A | A | D | E | -------------------- | A | A | I | I | -------------------- | | H | H | | -------------------- 82: H Right -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | A | A | D | E | -------------------- | A | A | I | I | -------------------- | | | H | H | -------------------- 83: A Down -------------------- | G | F | C | C | -------------------- | G | F | B | B | -------------------- | | | D | E | -------------------- | A | A | I | I | -------------------- | A | A | H | H | --------------------
Back to software page