How many Latin squares also happen to be sudoku puzzles? Counting up the total possible number of 9-by-9 Latin squares turns out to be quite difficult, and determining the total possible number of sudokus is even harder. If a Latin square contains subgrids that also contain the n numbers once each, then it’s a sudoku. A Latin square is simply a grid of numbers from 1 to n arranged so that each row and each column contain precisely one instance of each number. Sudoku puzzles are an example of a type of graph known as a Latin square, which mathematicians have studied for centuries. Then in any solution, all the 1’s could be switched with all the 2’s, so there would be at least two valid solutions. Suppose that neither 1 nor 2 appears in the initial entries. Herzberg and Murty have established, however, that for a puzzle to have precisely one solution, the initial entries need to include at least eight of the nine digits. Unfortunately, there’s a glitch: although the mathematicians proved that the formula exists, they weren’t able to figure out what it is. Such a formula might help a stumped puzzle-solver make sure that a certain sudoku really does have a solution, and that it has only one solution. If the puzzle is designed correctly, it has only one possible solution. Herzberg and Murty used techniques from graph theory to show that a mathematically simple formula exists for the number of possible solutions to a given sudoku puzzle. Thus, in the language of graph theory, solving a sudoku means extending a partial coloring of the graph into a proper coloring. Once each vertex is colored and no two connected vertices have the same color, the coloring is called “proper.” When graph theorists label the vertices, they call it a “coloring.” A sudoku puzzle begins with a partial coloring, since only a few spots have numbers. For example, a puzzle could have nine letters, shapes, or colors instead of numbers. An article in the June Notices of the American Mathematical Society lays a mathematical framework for addressing some basic questions about sudokus.Īlthough sudoku puzzles almost always use the digits 1 through 9, any nine symbols will suffice. Herzberg and Murty, Notices of the American Mathematical SocietyĪlthough the puzzles are often billed as requiring no math to solve, some of the questions they raise call for mathematical analysis. Despite having 29 initial entries, it has two possible solutions. Herzberg and Murty, Notices of the American Mathematical Society Murty found this poorly-designed sudoku puzzle in Air Canada’s in-flight magazine. So far, no one has figured out whether or not a solvable puzzle exists with only 16 initial entries. Further questions may come to mind: How many different sudoku puzzles are possible in the standard 9-by-9 format? Can a puzzle with few initial entries be easier to solve than one with more entries? What’s the smallest number of initial entries necessary to guarantee that there’s one, and only one, solution? This sudoku puzzle has 17 initial entries, the smallest number known to be possible on a 9-by-9 grid. At another moment, aglow in the triumph of a clever deduction, you might have a sneaking suspicion that there may be a simpler, more systematic way of finding the answer. When you get stuck on a fiendishly difficult sudoku, it’s hard not to wonder if the puzzle really has a solution.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |