Completed my thesis under the supervision of Félix Balado Pumariño and moderation of Shen Wang and Damian Dalton, over the course of two modules totalling 15 ECTS due to University College Dublin (UCD)’s new Final Year Project (FYP) structure: FYP Foundations (COMP30900) at 5 ECTS and FYP Design and Implementation (COMP30910) at 10 ECTS.
My thesis is titled "Finding the Minimum Number of Sudoku Clues Through Information Theory" and focussed on deriving an information theoretic explanation for the results at the state-of-the-art (SOTA) of the Minimum Sudoku Clue Problem (MSCP). That explanation would then be used to lay the foundation for improvements beyond the SOTA of the MSCP.
Submitted two deliverables as part of requirements consisting of a 28-page foundations report and 10-minute presentation which both summarized my plan of action and were presented to both moderators.
-
Foundations Report (28 Pages): Wrote foundaitions report under the following headings; Abstract, Introduction, Groundwork, Data Considerations, Outline of Approach, Summary and Conclusions, Acknowledgements and Bibliography
-
Presentation (10 Minutes): Gave a 10-minute presentation on my thesis to my moderators.
- Thesis (39 pages) Wrote thesis under the following headings; List of Figures, List of Tables, Glossary, Abstract, Introduction, Project Specification, Groundwork, Data & Context, Core Contribution, Evaluation, Summary and Conclusions, Acknowledgements, Appendices and Bibliography.
Sudoku is a puzzle game where the player is presented with a 9 x 9 square grid called a Sudoku grid such that every row, column, and 3 x 3 square subgrid contain a permutation of the numbers 1 to 9. In a Sudoku puzzle, a few squares out of the 81 forming a chosen Sudoku grid are given as clues to the player, who has to guess the content of the remaining ones. In 2013, McGuire et al. found through a mathematically informed empirical search that 17 is the minimum number of clues for a Sudoku puzzle to be uniquely solvable. However, there is no formula yet that tells us why this should be so. This research project aims to investigate the Minimum Number of Clues for a Sudoku puzzle to be uniquely solvable from a theoretical perspective; using the tools of Information Theory to model Sudoku as an erasure channel in an effort to produce theoretical results that can give insight into why exactly it is that 17 is the minimum number of clues for a Sudoku puzzle to be uniquely solvable.