Application of Hamming Code Theory in Prisoner 's Chessboard Puzzle

Abstract

This work proposed a universal algorithm based on the parity-check theory of Hamming code for solving the Prisoner's Chessboard Puzzle (PCP) which is known as an unsolvable mathematical problem. The solution to the simplest two-dimensional PCP is first given. However, no suitable strategy is available when the 3D PCP is transformed into a 3D cube coloring problem. To explore the existence and structure of the solution of PCP, we make the rows of the whole chessboard into a line and then uses the idea of Hamming code parity check. After proving the agreement of parity check results and XOR operation ones, we carry out XOR operation to get a universal solution for PCP. The results show that the method can solve any dimension PCP effectively.