A recent article by Agnes M. Herzberg and M. Ram Murty in the Notices of the American Mathematical Society confirms what many of us have known for years: there's more than one way to solve a Sudoku puzzle. Unfortunately, most of them are still wrong [Sudoku Squares and Chromatic Polynomials]. However—and here's the encouraging part—there are sometimes more than one right answer. The puzzle shown on the right is an example. Try it. (Answer below.)
There are two different ways to fill in the blank cells. Both of them are valid solutions.
I've always thought that the Sudoku puzzles were more like logic puzzles than mathematical puzzles and the article confirms that impression. The puzzles can be solved using colors instead of numbers. Here's what the authors say about the popularity of these puzzles.It is interesting to note that the Sudoku puzzle is extremely popular for a variety of reasons. First,it is sufficiently difficult to pose a serious mental challenge for anyone attempting to do the puzzle. Secondly, simply by scanning rows and columns, it is easy to enter the “missing colors”, and this gives the solver some encouragement to persist. The novice is usually stumped after some time. However, the puzzle can be systematically solved by keeping track of the unused colors in each row, in each column, and in each sub-grid. A simple process of elimination often leads one to complete the puzzle. Some of the puzzles classified under the “fiendish” category involve a slightly more refined version of this elimination process, but the general strategy is the same. One could argue that the Sudoku puzzle develops logical skills necessary for mathematical thought.How many of you are hooked?
To be considered well-constructed, a sudoku puzzle must have one unique answer. Some advanced solving techniques use that fact.
ReplyDeleteAnd, yes, sudoku puzzles have nothing to do with arithmetic. They are puzzles in logic (which is, after all, a subset of mathematics), and work equally well with letters or symbols in place of numbers. Numbers happen to be easier to manipulate because people all over the world recognize the digits from 1-9.
"I've always thought that the Sudoku puzzles were more like logic puzzles than mathematical puzzles and the article confirms that impression. The puzzles can be solved using colors instead of numbers."
ReplyDeleteEh, no.
I think the key words of "chromatic polynomials" in the title, the key sentences "We will reformulate many of these questions in a mathematical context and attempt to answer them. More precisely, we reinterpret the Sudoku puzzle as a vertex coloring problem in graph theory", the authors as mathematicians, and the publication in "Notices of the AMS" is a tip off. :-)
What you are probably trying to say, correctly I believe, is that this game as so many other doesn't yet have a known best strategy. So we can still play with it.
Btw, the coloring is just a map to a large class of "coloring problems" in mathematics. See for example http://en.wikipedia.org/wiki/Map-coloring_problem and http://en.wikipedia.org/wiki/Graph_coloring. As Exterminator says, formal logic is considered math, so are many logical problems at the core, while logic at large as for example as fallacies in reasoning is in the philosophical domain.
Is it inevitable that the last squares in this example to be filled in are the 4/9-9/4--9/4-4/9 squares?
ReplyDeleteOnly if you refuse to hazard a guess. Since you can't know there are supposed to be 2 solutions left, those 4 boxes should remain empty to the very end.
DeleteI just played one like it, and that's why I found this article. Because I read somewhere that sodokus are supposed to only have 1 solution.
This makes sense, though, that the thing which so often is a bar to progress should create the possibility of 2 solutions.
Yes it is inevitable these squares are the last ones remaining because at that point the puzzler has to decide: "there is no clue available to decide whether each of these squares contains a 4 or a 9, therefore either must be the correct answer." Since the clue as to their position does not exist at the point where only 4 spaces remain there could not have been a clue earlier in the puzzle either.
DeleteThe next question is then can there be puzzles with more than just 2 pairs of numbers that are interchangeable. I suspect that 3 pairs would not work but am not sure about that. Atleast additional pairs can be added 2 pairs at a time.
When there are too many such pairs does it become impossible to solve for the remaining spot because of confusion caused by the empty spots left by switchable spots?
You mentioned 3 pairs, and yes that is an open question. I found a sudoku that had 4 pairs, that is a 3/7-7/3 and a 4/5-5/4. Garbage sudoku publishing on the web these days. I would vote that they should be unique
DeleteHow many of you are hooked?
ReplyDeleteOh, yeah. To the limits of my recognition/inference skills. I'm not very quick and I sometimes make a careless error that screws up the puzzle. Often I find with difficult puzzles I'm reduced to making a guess and seeing if it works out.
Nonetheless, my favorite version uses 4x4 sub-grids filled in with 0-9 and A-F. Hex!
I also found a puzzel which ended like yours only with 4 and 7 above each other. Even weirded is that when I checked the solution in the paper it was completely different than mine. Has anyone else found that to be true. You can email me at stickswood@cruzio.com with comments or if you want to see the puzzle I can forward it and the solutions to you.
ReplyDeleteI found the same thing on a Sudoku puzzle I just solved. There were two solutions with flipped pairs of digits 5 and 2, but the answer key had a completely different solution. All three solutions proved to be correct. I have found that these puzzles with accidental multiple solutions are much harder to solve as they don't fall into place as simply as the ones with a single solution.
DeleteMcC,
ReplyDeleteI came across a puzzle last night that had the same scenario of leaving the last 4 squares with the option of filling in 2&8 in two different ways. It seems to happen very rarely, and I expect it requires a unique placement of just two specific numbers.
I came across a puzzle a few minutes ago that had the last four squares open and I could find no reason that either of the two options for number placement would not work equally well....that is, I could fill in the squares either of two ways without messing up the puzzle.
DeleteSo I just filled them in with one of the two possible numbers and solved it from there.. But the interesting thing was, when I checked my solution with the answer sheet in the back, I found that even before I filled in those last four squares I had put different numbers in many of the squares than the official solution showed. Yet I could find no place in the puzzle as I had solved it, that would produce an error anywhere in the puzzle. Everything added up just as well as it did in the solution on the answer page. This is the first time I have noticed that happening, but I suppose this means that there can be more than one right way to solve at least some Sudoku puzzles.
I just completed a puzzle from the Wednesday 14 of April, 2012 USA today and I have 17 different answers than the answers in the newspaper and both my answers and the papers add up in box, length, and across..This is something I will hold on to in case anyone wants to see it. What a surprise, because I always thought there was only 1 right answer per square.
DeleteI just completed a puzzle from the January 2015 issue of Xfinity CableGuide magazine that had 19 different answers from the published solution. Could it have been the same puzzle reprinted in both magazines? I was very surprised, and had never seen such a thing before. I emailed the editor who never responded. I wanted to know if anyone else brought it to her attention. I am still very curious!
DeleteI just did the same thing! I had over 8 numbers wrong according to the solution, but everything fit. Was puzzled.
ReplyDeleteI just finished a puzzle that had a different solution than the back of the book. There is no doubt in my mind there is more than one solution to a puzzle.
ReplyDeleteIt is a great satisfaction to see that in addition to a multitude of ways to solve a Sudoku incorrectly there are (in some cases) more than one way to do so correctly.
ReplyDeleteNow the next question I have is: have some Sudoku been (incorrectly) generated and published where there is no possible solution to solving them? And if they were, how would we know :)
I found this article while looking up to se how common sudoko puzzles with more than one solution were, since I have just found one in a newspaper, with two adjacent squares in each of two adjacent blocks having the possibility of 6,3 and 3,6, or 3,6 and 6,3.
ReplyDeleteJust happened again, Toronto Star May-6-16. Block 6 and 9 (counting from top left across) interchange squares 1 and 2. Why does the instructions state - "There is only one solution for each puzzle." Editor please note!
ReplyDeleteI found this page because I, also, encountered a sudoku puzzle with two possible solutions. In this case though the four digits (4,5 and 5,4) were not adjacent but separated by 1 row and 4 columns. This leads me to hypothesize that any arrangement of digits a, b and b, a arranged as a rectangle indicates a sudoku with at least two correct solutions. A sudoku with two such rectangles would have at least four correct solutions.
ReplyDeleteNewsday sudoku of feb 3 2018 is an example of this.
ReplyDeleteIn a book "Sudoku 215 Puzzles from beginner to expert" by Marcel Danesi, I have just completed 97 puzzles. The last four had different solutions to those published in the answer key, yet every square, row, and column added correctly. I wanted to see if my brain was malfunctioning because I was always told there can be only one solution. Clearly, and by these comments, that statement is false. Good to know my brain is fine.
ReplyDelete