Label the vertices of this graph with numbers 1 to 16 in such a way that the edges between any two vertices whose sum and absolute difference are both primes are precisely the edges of a hamiltonian circuit of the graph, that is a tour of all of the graph's vertices that visits each vertex exactly once, and returns to the vertex from where it started.

For your convenience, five of the numbers have been placed.

Primes in a Diamond


First, I found all pairs that satisfy the criteria:

enter image description here

Next, we can start making some deductions:

1 must connect both southwest and south, and 15 must connect both northeast and southeast. Since 15 only connects to {2,4,8}, and 8 is already used, 4 must go northeast of it and 2 must go southeast.

That gives this new grid:

enter image description here


1 must connect to 16 or 12, neither of which connects to 8. So that resolves more of the path. Additionally, 2 connects to 9 only out of the leftovers, which connects to 14 only, which connects to 3 only, which does not connect to the 13 it is adjacent to.

That resolves the rest of the path, but not the numbers:

enter image description here

For the numbers,

the 1 must have a 2-chain leading to 8. Out of the remaining numbers, that can only be 1-6-11-8. And finally, the 5 only connects to 12, which only connects to 7, which only connects to 10, and so the chain can be completed.

The final answer to the puzzle:

enter image description here

And to double-check the result:

The only extra lines we're concerned about are when an odd and an even number are adjacent, but not connected. These pairs are 11-14, 11-16, 7-16, and 1-8. None of these have both sum and difference prime, so the puzzle is solved.

  • $\begingroup$ 7 and 12 should be swapped in the final answer. $\endgroup$ – BolteAltamont Jun 4 at 0:33
  • $\begingroup$ @BolteAltamont Whoops, you're completely right - good catch! Fixed. $\endgroup$ – Deusovi Jun 4 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.