Blocking Intercalates In Sudoku Erasure Correcting Codes

Daniel Williams, Sian-Kathryn Jones, Paul Roach, Stephanie Perkins

Research output: Contribution to journalArticlepeer-review

74 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)183 - 191
Number of pages8
JournalInternational Journal of Computer Science (IJCS)
Volume38
Issue number3
Publication statusPublished - 24 Aug 2011

Keywords

  • sudoku
  • intercalates
  • unavoidable sets
  • coding theory
  • erasure correction

Fingerprint

Dive into the research topics of 'Blocking Intercalates In Sudoku Erasure Correcting Codes'. Together they form a unique fingerprint.

Cite this