Erasure Correction Capabilities of Sudoku and Related Combinatorial Structures.

This paper aims to discuss and demonstrate the suitability of Sudoku, and related puzzles, for use in erasure-correcting codes. An erasure-correcting code is a code capable of correcting erasure errors that occur in a message during transmission. Erasure correction is generally achieved by adding a specified amount of redundant information to the original message during the encoding process. Using this redundant information the original message can be recovered, post-transmission, from a portion of the transmitted information.
Erasure-correcting codes have many practical applications within the fields of computer science and communication theory, and recent research has identified more areas in which scope exists to incorporate such codes. Sudoku supports the requirements of an erasure-correcting code well. The object of Sudoku is to complete a partially completed grid by exercising logical reasoning and utilising the available information, hence completing the puzzle to arrive at a unique solution from a relatively small number of clues. A coding scheme that successfully incorporates, or is based on, a combinatorial structure such as Sudoku would spawn a new class of erasure-correcting codes which would exploit the ability to complete the puzzle grid from very incomplete information.
In this paper, we describe the requirements of an erasure-correcting code and detail the properties of Sudoku and a related structure - Rudoku, hence outlining the erasure correction capabilities of the puzzles. The paper examines the issues with mapping the original message to a Sudoku grid; and finally, an initial basic coding idea is presented along with a discussion of the direction of future work.