Sudoku puzzles as erasure correcting codes

In 2007, Soedarmadji and McEliece [1] introduced a new class of erasure-correcting codes based on Latin squares and Sudoku grids. This paper investigates the merit of this proposal. A Sudoku puzzle is based on a square grid of order n. The grid is a Latin square with one further property; the grid is subdivided into n non-overlapping mini-gridsand each of the values 1 to n must appear exactly once within each of these minigrids, in addition to occurring exactly once in each row and each column. Typical published puzzles use n = 9 with the grid subdivided into 9 non-overlapping minigrids of order 3. The values 1, 2, . . . , 9 may occur exactly once in each row, each column and each 3 × 3 minigrid. A Sudoku puzzle is created by removing values from some cells of a valid Sudoku grid, such that the grid can be completed uniquely and the object of the puzzle is for the player to deduce the unique completion by using the structure’s properties and logical reasoning. A smaller 6 × 6 puzzle with six 2×3 mini-grids, often referred to as Rodoku, will also be considered. Examples of a Sudoku puzzle and a Rodoku puzzle are shown in Figure 1. Although originally introduced as a number-placement puzzle, Sudoku is also now an established combinatorial object and the study of the structure is a popular area of combinatorial research.