Sudoku puzzle as an LDPC code

Sudoku is a very popular number placement puzzle. Usually defined on a matrix of size 9 × 9, the puzzle involves the solver to determine the missing elements of the matrix using certain rules. There is a very strong connection between solving Sudoku puzzles and determining the erased symbols of a codeword that was transmitted over an erasure channel. In this paper, we demonstrate this relationship between Sudoku puzzles and LDPC codes and several solving techniques that can be used to solve one are translated to the other domain. The resulting techniques enable a better understanding of the inner workings of the error control code decoding algorithms as well as efficient solving of Sudoku puzzles using error control coding techniques. The proposed sudoku solving algorithms have been employed to solve puzzles with different difficulty levels and the corresponding performance is calculated.