Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Write down a Hamiltonian cycle for the (undirected) graph where the nodes are given by the squares of the chessboard and are connected by edges if they are (orthogonally) adjacent. Notice that because the squares are different colors, deleting them from the Hamiltonian cycle partitions it into two even length paths. Cover each even length path with dominoes.

The part where you notice the two paths are even length feels a bit like dark magic the first time you see it. Notice that if you have two different coloured squares which are consecutive on the cycle the paths you get are length 64-2 and 0, then if as you move one of them further and further along the path you have to move in steps of 2 to keep them opposite colours.



Holy shit that's slick. Wow.

You have to verify though that the Hamiltonian cycle exists. An induction proof seems to do the job.


You can draw a big "C" shape that goes around 3 edges of the board and then fill in the middle with wiggles. This works for any rectangular board where one of the edge lengths is even. You already need one of the side lengths to be even to solve the problem because if both sides are odd then the number of squares is odd, and good luck covering an odd number of squares with dominoes.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: