![]() It was not a Sudoku because it contained double-digit numbers and required arithmetic rather than logic to solve, but it shared key characteristics: each row, column, and subsquare added up to the same number. Le Siècle, a Paris daily, published a partially completed 9×9 magic square with 3×3 subsquares on November 19, 1892. Number puzzles appeared in newspapers in the late 19th century, when French puzzle setters began experimenting with removing numbers from magic squares. ![]() newspaper, and then The Times (London), in 2004, thanks to the efforts of Wayne Gould, who devised a computer program to rapidly produce unique puzzles.įrom La France newspaper, July 6, 1895: The puzzle instructions read, "Use the numbers 1 to 9 nine times each to complete the grid in such a way that the horizontal, vertical, and two main diagonal lines all add up to the same total." Predecessors However, the modern Sudoku only began to gain widespread popularity in 1986 when it was published by the Japanese puzzle company Nikoli under the name Sudoku, meaning "single number". The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.įrench newspapers featured variations of the Sudoku puzzles in the 19th century, and the puzzle has appeared since 1979 in puzzle books under the name Number Place. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contain all of the digits from 1 to 9. If the problem can be solved relatively quickly, then so can every problem that satisfies property (1).Įven though checking a solution of an NP-complete problem can be done relatively quickly and easily, there is no known algorithm for finding a solution to begin with, because the time needed for computation increases so fast compared to the size of the problem.Sudoku ( / s uː ˈ d oʊ k uː, - ˈ d ɒ k-, s ə-/ Japanese: 数独, romanized: sūdoku, lit.'digit-single' originally called Number Place) is a logic-based, combinatorial number-placement puzzle.Any solution to the problem can be checked relatively quickly, i.e.An NP-complete problem satisfies the following two properties: This places the game of solving rank-n Sudoku puzzles in a class of problems that computer scientists have named NP-complete. As the rank of a Sudoku increases from n to n+1, the extra computational time needed to find a solution increases quite fast. Find two different solutions.įor 4×4 Sudoku, a case-by-case analysis utilizing the two essentially different grids proves that a well-formed puzzle must have a minimum of four distinct digits in the givens.įinally, it is intriguing to note that even though there are computer programs that can quickly and easily solve rank-3 Sudokus by employing a backtracking method, solving a Sudoku of arbitrary rank n is a much more difficult problem. The next exercise illustrates this with a specific example.Įxercise: The following rank-2 Sudoku has 2 2-1=3 distinct digits among the givens. Recall that the converse of a true statement is not necessarily true. It is important to note that this is not the same as stating that if a Sudoku of rank n has n 2-1 distinct digits in the givens, then it is well-formed. The fact discussed above can be restated as follows: If a Sudoku of rank n is well-formed, then it must have n 2-1 distinct digits among the givens. In particular, for the usual rank-3 Sudoku, at least 3 2-1=8 distinct digits must be used in the givens for the puzzle to be well-formed otherwise, the puzzle will have more than one solution. This is because if we had a rank-n puzzle where only n 2-2 symbols were used and we found a solution, then interchanging the places of the two symbols missing from the givens would result in another, different solution. However, the minimum number of givens for which a rank-3 Sudoku can be well-formed is not known.Įxercise: Can you come up with a Sudoku puzzle that is not well-formed?Īnother interesting question (that you may have considered when solving the above exercise) is how many distinct symbols need to be used among the givens for a puzzle to be well-formed? It turns out that for a Sudoku of rank n, at least n 2-1 distinct symbols must be used for the puzzle to have a unique solution. ![]() ![]() There are examples of rank-3 Sudoku puzzles with 17 givens that are well-formed. A Sudoku puzzle can have more than one solution, but in this case the kind of logical reasoning we described while discussing solving strategies may fall short. The Math Behind Sudoku Some More Interesting FactsĪ well-formed Sudoku puzzle is one that has a unique solution. ![]()
0 Comments
Leave a Reply. |