1. Introduction#
- “If you steal from one author it is plagiarism; if you steal from many it is research.”
— Wilson Mizner
1.1. History#
- Sources:
In July 1895 in France, the Newspaper La France, refined a numbers game puzzle appearing in a rival newspaper Le Siècle. La France called the puzzles Carré Magique Diabolique. They were a precursor to modern Sudoku. La France published these puzzles until about the time of the First World War.
Modern Sudoku started out published in Dell Magazines from about 1979 called Number Place. It is thought that they were designed by Howard Garns, a retired 74-year-old Architect. In 1984 the Nikoli Puzzle Company in Japan introduced Number Place puzzles as Sūji wa dokushin ni kagiru which was later abbreviated (in Kanji) to Sudoku, despite it being ubiquitously called Nanpure in Japan.
In 1997, Wayne Gould, a retired Hong Kong Judge, developed the first computer program to produce unique puzzles rapidly. He then introduced Sudoku to the Times newspaper in Britain. The publicity gained from this exposure in the Times secured the puzzle’s worldwide popularity.
1.2. What is Sudoku#
Sudoku is a puzzle laid out on a 9x9 grid of cells, where each cell is either empty or contains a number between 1 and 9. The puzzle is solved by filling the empty cells with digits 1 to 9 such that each digit only occurs once in each row, column and 3x3 box.
1.3. Sudoku Rule#
1.4. Sudoku Facts#
- Sources:
Sudoku is a finite constraint satisfaction problem (fCSP). A Sudoku grid comprises 9 rows by 9 columns making 81 cells, and each cell can assume one of 9 values. Therefore, the out of a Domain set of 729 (9 rows x 9 columns x 9 Values) elements, any Solution set comprises 81 elements (9 rows x 9 columns x 1 value) that are constrained by the Sudoku Rule and its further constraint propagation (Rule application).
Fraser Jarvis, et al has determined 6670903752021072936960 (6.6709e+21) solved puzzles exist, of which 5472730538 (5.4727e+9) are mathematical unique. Mathematically unique puzzles cannot be created by transforming another puzzle. Also termed non-isomorphic; they are not canonical forms of each other.
Denis Berthier has estimated to within a 0,065% error that the average amount of minimal puzzles that can be from any solved puzzle is 4.6655e+15. Therefore, approximately 6.6709e+21 x 4.6655e+15 = 3,1123e+37 possible minimal puzzles exist, of which 2.5533e+25 are mathematically unique.
To appreciate how large these numbers are, if it is possible to solve a puzzle every second, only 31 557 600 (3,1557e+7) puzzles will be solved in a year. Solving a puzzle every second since the beginning of time (estimated 14 billion years ago), only 4,4180e+15 puzzles will be solved. If everyone on earth (approximately 8 billion people) is solving unique Sudoku puzzles at the rate of one a second since the beginning of time, only 3.5345e+27 puzzles will be solved. This number is an infinitesimally small one 8.8 billionth (8.8055e-9) of all possible puzzles.
To date no unique puzzles have been found with less than 17 givens, and only 49158 - 17 givens puzzles have been found. A method to prove the theoretical minimum givens for any unique puzzle is yet to be found.
Wikipedia claims that the largest minimal puzzle found so far has 40 clues.
In a valid puzzle, at least 8 of the 9 digits must occur one or more times as givens. However, meeting this criterion does not presume a puzzle is valid.
1.5. What’s Ahead?#
Chapter Two develops foundational theory that is used in the solving of Sudoku patterns. Chapter Three applies the theory to the actual practical solving of Sudoku patterns. Chapter Four examines generation of puzzles, and Chapter five, the Grading of Puzzles. Lastly Chapter Six describes the software developed for this project.
1.6. Intended Audience#
The intended audience are people who have at least mastered the basics of Sudoku, and are seeking to improve their skills. Many excellent sources on the internet do a better job than I in covering the basics. I defer to them.
Static pages do not have a comment mechanism like blogs. Please feel free to comment here, and I will endeavour to review and include community comments and contributions.
1.7. Acknowledgements#
I acknowledge the Sudoku Community, the many reports, web-pages, and videos found on the Internet. This tomb brings together many, many related bits of information. If anything is original here, it is the insights and conclusions gained from the collective works before me.
A complete list acknowledging all the media contributing to my understanding would be so vast, incomplete and constantly changing thereby diluting its intent.
Sources of information and puzzles are acknowledged throughout the text. A list of references is included too. Some sources have been lost. I apologise for this. Please contact me if you notice information from a source that needs acknowledgement. I fear that with the passage of time, linked references will disappear, frustrating readers seeking sources. For this too, I apologise in advance.