Blocking Intercalates In Sudoku Erasure Correcting Codes

A Sudoku grid is a square grid of size n, further subdivided into n mini-grids and into which the symbols 1, 2, . . . , n are placed such that each symbol appears exactly once in each row, column and mini-grid. It has been suggested that Sudoku puzzles may have applications in Coding Theory, specifically in the recovery of erasures [1, 2]. By encoding a message within a Sudoku grid, a received grid containing erasures can be treated as a puzzle, the solution of which will enable the original message to be recovered. However, the received values must be sufficient to specify a unique solution, or the message may not be recovered correctly. Every Sudoku grid possesses a number of unavoidable sets, which are patterns of cell values that, if all are absent from a puzzle, prevent unique completion of that puzzle. The presence of the smallest size of unavoidable set, patterns of cells of size 2 × 2 also known as intercalates, has been shown to prevent the practical application of Sudoku grids for erasure correction [3]. This paper proposes a scheme that employs meta-data derived from a Sudoku grid as an efficient means of fixing, or ‘blocking’, its intercalates through the use of additional symbols, and evaluates the scheme in the context of erasure correction. Programs developed to locate and enumerate the intercalates of a grid, and to relabel cell values, are described, and results are presented on the numbers of additional symbols required and on the improvement in the successful recovery of erased cell values. As an alternative approach to the ‘blocking’ of intercalates, consideration is also given to a subset of Suduko grids, known as 2-Quasi-Magic Sudoku, which have specific intercalate properties; the suitability of this subset for erasure correction is evaluated.