Earlier today I set you two puzzles based on Hamiltonian paths in a square grid. A Hamiltonian path is one which visits every cell exactly once. (If you want a print out of the puzzles, click here.)
1. The Hamiltonian path
Place the numbers from 1 to 49 on the grid below such that all consecutive numbers are either horizontal or vertical neighbours. In other words, 1 is horizontally or vertically adjacent to 2, which is horizontally or vertically adjacent to 3, and so on up to 49.
The shaded squares are the prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47
Solution
The numbers 2 and 3 are the only consecutive prime numbers, so they must make up two of the three adjacent shaded cells in the bottom right of the grid. By trying the different permutations it should become clear the only possible way they can be arranged is for the 1 to be in the bottom right square. The keep on going. There are four solutions; they all start and end on the same cell.
Illustration: Nick Berry
If a Hamiltonian path joins up to make a loop, it is called a Hamiltonian circuit.
2. The Hamiltonian circuit
Place the numbers from 1 to 64 on the grid below such that all consecutive numbers are either horizontal or vertical neighbours, and 1 also is either a horizontal or vertical neighbour of 64. As above, the shaded squares are prime numbers, which the ones mentioned in the previous puzzle plus 53, 59, and 61.
Solution
I hope you enjoyed the puzzles. I’ll be back in two weeks.
Thanks to Nick Berry of DataGenetics for the first puzzle and Bernardo Recamán, author of The Bogotá Puzzles, for the second.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me. I also give school talks about maths and puzzles (restrictions allowing). If your school is interested please get in touch.
