In a study published in the Journal of the American Mathematical Society, researchers used tools from graph theory to systematically analyze Sudoku puzzles and discovered that Sudoku leads to unsolved problems in graph theory
Sudoku puzzle solved. The numbers in black are the data.
Have you ever tried to solve Sudoku, and suddenly a feeling of despair took over you: "Maybe it doesn't have a solution?". And even if you found a solution, how can you know it's the only solution? What if half an hour ago you had written 5 instead of 3, maybe you would have reached a completely different solution?
These and other questions occupy Agnes M. Herzberg and Ram Murty, in their article "Sudoku Squares and Chromatic Polynomials", published in the latest issue of the American Mathematical Society (AMS). The authors used tools from a branch of mathematics called graph theory to systematically analyze Sudoku puzzles. The researchers also discovered that Sudoku analysis leads to unsolved problems in graph theory.
In the framework of the Torah, "graph" is a term for a group of points (or nodes) connected by segments (called arcs). Graphs are also sometimes called 'networks'. You can think of the 81 squares in a sudko puzzle, as 81 nodes in a graph. Beyond that, each of the numbers 1-9 will be represented by a different color: 1 will be red, 2 blue, 3 green and so on; So each node gets a color, just as each slot has a number. Here, we have created a graphical representation for Sudoku, let's call it "Sudoku Graph". If in a sudoku puzzle, two squares are in the same row, the same column, or the same 3 x 3 square, then an arc is drawn between the two nodes that represent them. Since, according to the rules of Sudoku, no two numbers are the same in the same row, column or 3x3 square, no two nodes of the same color are connected. (An example will help to clarify the meaning. Let's say that we assigned the color red to the number 1. If two red nodes are connected to each other, this means that there are two squares (they are the nodes) with the number 1 (it is the color red) in the same row or in the same column or within the same square of size 3 x 3 (because that's how we defined a connection using an arc), and this is forbidden according to the sudoku rules).
In graph theory, coloring a graph so that there are no arcs between nodes of the same color is called "adequate coloring". Sudoku solvers all over the world, therefore, try to extend a partially-colored graph (the original puzzle has empty squares, that is, uncolored nodes) to a fully-colored graph.
With this analogy between graphs and Sudoku puzzles, Herzberg and Morty could use mathematical tools from graph theory to prove theorems about Sudoku. For example, they proved that the number of ways to expand a partially colored graph is given by a polynomial. If the value of the polynomial is 0 for a particular sudoku puzzle, then the puzzle has no solution, if the value of the polynomial is 1, then there is a single solution, and so on. Another test that the pair proved, which the reader can perform himself: a given sudoku puzzle will have a unique solution only if at least eight numbers out of the nine (1-9) appear in the puzzle. If only seven of the nine numbers appear, then the puzzle will have at least two possible solutions. And here we came to an open problem in mathematics: "It would be fascinating to find out under what conditions a partially colored graph can be extended to a unique [adequate] coloring," wrote Herzberg and Morty.
Some puzzles are more difficult than others, and the hardest ones contain a large number of blank squares. "What is the minimum number of given squares, which guarantees that the crossword puzzle has an arrangement that will lead to a unique solution?" Herzberg and Morty gave an example of a crossword puzzle with a unique solution, where 17 squares are given. Therefore, the minimum number will be less than or equal to 17. But what is the minimum number? No one else knows that. You might think that a crossword puzzle with a larger number of given squares has a greater chance of a single solution. It is not so; Herzberg and Moretti gave an example of a crossword with two possible solutions, in which 29 given squares.
And if you've been wondering when your local paper's Sudoku stash will run out, researchers say there are about 5.5 billion different Sudoku puzzles - enough to keep Sudoku enthusiasts around the world busy for a long time.
Graph theory is a relatively young field with many open problems. Similar to elementary number theory, it also has open problems that are easy to understand but difficult to solve. Mathematical discoveries will probably continue to excite humanity for many years to come.
The article Sudoku Squares and Chromatic Polynomials” An online version can be viewed on the AMS announcements website.
2 תגובות
to donate
We thank you for your vigilance, but there is no mistake in the article.
Your comment in parentheses: "Obviously, as the number of given numbers increases, the number of Sudoku solutions decreases" is incorrect and this is exactly the point the researchers were trying to convey. While Sudoku with 17 given numbers has a single solution, the researchers presented a Sudoku with 29 (and not 27 as you wrote) given numbers, which has exactly two different solutions.
The link to the article is at the end of the article. The example in question is on page 711, photo three.
I think you have a mistake in the article here
In part of the article you wondered which sudoku with a maximum number of given squares would still allow more than one solution
(That is, it is clear that as you increase the number of given numbers, the number of advantages to Sudoku decreases)
In the article we gave an example of Sudoku with two possible solutions when only 4 squares are missing, which means there are 77 filled squares in Sudoku and 2 possible solutions
You wrote that there is a sudoku with 27 given numbers and there are two solutions. Where does this number come from?