Did you solve it? Hamiltonian ingenuity on the grid

The solutions to today’s puzzles

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

hamiltonian path

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.

solution
Berry puzzle solution

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.

hamiltonian circuit

Solution

Screenshot 2021-10-17 at 20.57.21

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.

Contributor

Alex Bellos

The GuardianTramp

Related Content

Article image
Can you solve it? Hamiltonian ingenuity on the grid
Mental chicanery

Alex Bellos

18, Oct, 2021 @6:38 AM

Article image
Did you solve it? Puzzlebombed!
The solutions to today’s teasers

Alex Bellos

21, Sep, 2020 @4:00 PM

Article image
Can you solve it? Puzzlebombed!
Bamboozling bar graphs and brain busting bees

Alex Bellos

21, Sep, 2020 @6:10 AM

Article image
Can you solve it? Domino dancing
A riddle about rectangles

Alex Bellos

15, Jun, 2020 @6:10 AM

Article image
Did you solve it? Domino dancing
The solution to today’s puzzle

Alex Bellos

15, Jun, 2020 @4:00 PM

Article image
Can you solve it? Clueless sudoku
Puzzles where less is more

Alex Bellos

26, Jul, 2021 @6:10 AM

Article image
Did you solve it? Logical philosophers
The solutions to today’s puzzles

Alex Bellos

23, Aug, 2021 @4:00 PM

Article image
Can you solve it? World Cup arithmetic
The puzzle that shoots and scores

Alex Bellos

04, Jun, 2018 @6:10 AM

Article image
Did you solve it? The Zoom puzzle
The solution to today’s puzzles

Alex Bellos

01, Jun, 2020 @4:00 PM

Article image
Can you solve it? 2020 in numbers
The new year deconstructed, and a prize challenge

Alex Bellos

30, Dec, 2019 @7:10 AM