Erasure-Correcting Codes Derived From Sudoku & Related Combinatorial Structures

This thesis presents the results of an investigation into the use of puzzle-based combinatorial structures for erasure correction purposes. The research encompasses two main combinatorial structures: the well-known number placement puzzle Sudoku and a novel three component construction designed specifically with puzzle-based erasure correction in mind. The thesis describes the construction of outline erasure correction schemes incorporating each of the two structures.<br/><br/>The research identifies that both of the structures contain a number of smaller sub-structures, the removal of which results in a grid with more than one potential solution - a detrimental property for erasure correction purposes. Extensive investigation into the properties of these sub-structures is carried out for each of the two outline erasure correction schemes, and results are determined that indicate that, although the schemes are theoretically feasible, the prevalence of sub-structures results in practically infeasible schemes.<br/><br/>The thesis presents detailed classifications for the different cases of sub-structures observed in each of the outline erasure correction schemes. The anticipated similarities in the sub-structures of Sudoku and sub-structures of Latin Squares, an established area of combinatorial research, are observed and investigated, the proportion of Sudoku puzzles free of small sub-structures is calculated and a simulation comparing the recovery rates of small sub-structure free Sudoku and standard Sudoku is carried out. The analysis of sub-structures for the second erasure correction scheme involves detailed classification of a variety of small sub-structures; the thesis also derives probabilistic lower bounds for the expected numbers of case-specific sub-structures within the puzzle structure, indicating that specific types of sub-structure hinder recovery to such an extent that the scheme is infeasible for practical erasure correction.<br/><br/>The consequences of complex cell inter-relationships and wider issues with puzzle-based erasure correction, beyond the structures investigated in the thesis are also discussed, concluding that while there are suggestions in the literature that Sudoku and other puzzle-based combinatorial structures may be useful for erasure correction, the work of this thesis suggests that this is not the case.

Name dc:type.qualificationname

Doctoral Thesis

Level dc:type.qualificationlevel

Student thesis

Year dc:date.issued

2013

Author dc:creator

• Phillips, Linzy

Advisors dc:contributor.advisor

• Perkins, Stephanie
• Roach, Paul

• Comninatorial analysis Set theory

Language dc:language

eng

Identifier

oai:pure.atira.dk:studenttheses/b359130e-bfc2-4df0-a6f5-55879212010d

OAI identifier oai:identifier

oai:pure.atira.dk:studenttheses/b359130e-bfc2-4df0-a6f5-55879212010d