5 ms·
Mathematicians Solve Minimum Sudoku Problem
- ctdonath 15y agoSudoku: crack for intellectuals.
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- Almaviva 15y agoSuppose there is a unique 15-clue solution. Then add another clue by adding any number from the unique solution. The solution must still be unique (because it contains the 15 clues), so we now have a unique 16-clue solution, which is impossible. So isn't this article missing the obvious?
- kingatomic 15y agoThe implication (not entirely clearly stated in the article) is that if a puzzle with n clues is solvable, a puzzle with n+1 clues is also solvable. Conversely, if a puzzle with n clues is unsolvable, any puzzle with n-1 clues is similarly unsolvable.
- joshzayin 15y agoI think they addressed this in the edit they made: >Correction: this post was edited on the 6 January to reflect the argument that if an n-clue grid is uniquely solvable then adding a digit to make an n+1-clue grid must also be uniquely solvable. So if there are no uniquely solvable 16-clue grids, there cannot be any grids with fewer clues that are uniquely solvable. Thanks to RealMurph and abooij.
- its_so_on 15y agoI don't get where the article makes this assumption: "It's easy to see why. A grid with 7 clues cannot have a unique answer because the two missing digits can always be interchanged in any solution." let's say these are your 7 clues: (row 1) 123 456 7 the article suggests that IF there is a full solution with 123 456 789 then there is a full solution with 123 456 798 but what guarantees that the second (or first) of these 9 clues don't lead to an "impossible" scenario, so that only one of the two is actually possible to solve? Maybe I am misunderstanding the article. Turning to what you say: "Suppose there is a unique 15-clue solution. Then add another clue by adding any number from the unique solution. The solution must still be unique (because it contains the 15 clues), so we now have a unique 16-clue solution, which is impossible." Can you elaborate on why a unique 16-clue solution is impossible?
- Jtsummers 15y agoRegarding 7 hints provided. Suppose you have a puzzle which contains 7 digits for hints. Assumming the provided digits are 1-7 placed around the grid and that they permit you to produce a unique solution for those digits (that is you can fill up all but 18 spaces). If you then fill in those remaining spaces with 9 8s and 9 9s, then, however you arranged them, the opposite arrangement is valid. Essentially those two remaining hints would be variables that you could then substitute either symbol for yielding 2 potential solutions making it an invalid sudoku puzzle.
- its_so_on 15y agothanks. it's like why a system of three variables for which you have two equations (like x = 2y + z and x = 3y + 2z + 7) isn't solvable.
- SatvikBeri 15y agoFor the first question, about why 123 456 7 doesn't have a unique solution: Let's say there is a unique solution to 123 456 789 . In that solution, swap every 8 and 9. It's not hard to see that this will be a correct solution of 123 456 798. Therefore, 123 456 7 must have an even number of solutions. For the second question, about why a unique 16-clue solution is impossible: that's the result mentioned in the article, with the proof that took a year to calculate.
- deleted 15y ago[deleted]
- yread 15y ago7.100.000 hours on a 640 hexcore Xeon cluster is only 1.848 hours. That is ~6 hours a day for January-December. I always had a suspicion that all these super powerful grids are only used to play Sudoku..
- supar 15y ago"These guys have solved the problem using the tried and trusted mathematical technique of sheer brute force. In essence these guys have examined every potential 16-clue solution for every possible Sudoku grid." I was actually hoping for a formal solution or proof here by reading the title.
- pgmcgee 15y agoI believe that would have far-reaching implications, seeing that Sudoku has been proven to be an NP-Complete problem. http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Games_and_puzzles http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Ga...
- Someone 15y agoProving something about a NxN grid does not have much to do with a problem being NP-complete. For example, the fact that it is not very hard to proof that a 1x1 sudoku requires 1 clue does not prove that sudoku is not NP-complete.
- pbhjpbhj 15y agoSurely a 1x1 grid requires 0 clues?!
- ohgodthecat 15y agoNo because then you wouldn't be able to arrive at a fixed solution there would be 9 solutions with 0 clues.
- SatvikBeri 15y agoIn a 1x1 grid you would only use one digit, not 9. A 1x1 grid requires 0 clues, a 2x2 requires 1 clue.
- deleted 15y ago
- arctangent 15y agoThis article reminded me of the computer-assisted proof of the Four-colour Theorem: http://en.wikipedia.org/wiki/Four_color_theorem#Proof_by_computer http://en.wikipedia.org/wiki/Four_color_theorem#Proof_by_com...
- dxbydt 15y agoIt reminded me of what Dr. Doron Zeilberger has been repeating ad-nauseam ( eg: http://www.math.rutgers.edu/~zeilberg/Opinion36.html http://www.math.rutgers.edu/~zeilberg/Opinion36.html ) Ultimately automated theorem provers are going to rule. Dr.Z actually takes the very radical stand of calling all paper-pencil math proofs of Paul Erdos trivial, whereas "Theorems that only computers can prove...are not quite as trivial". The fact that we have to reach out to a computer to assist in solving min-sudoko is unfortunate but at the same time, inevitable. Dr. Z mentions Four Color Theorem, Kepler's Conjecture, and Conway's Lost Cosmological Theorem as other theorems only computers can solve.
- nandemo 15y agoBut note that the proofs for the 4-Color Theorem and this Sudoku theorem are "merely" computer-assisted. The part of reducing the Sudoku search space, for instance, seems to have been done pencil-and-paper style. What Zeilberger wants is completely automated proving. Oh, and thanks for introducing me to Conway's Cosmological Theorem. Very interesting! http://mathworld.wolfram.com/LookandSaySequence.html http://mathworld.wolfram.com/LookandSaySequence.html
- joshuahedlund 15y agoIt's interesting that we are reaching an era where we can prove things through computational brute force before coming up with an elegant proof, even if it means running computers for 12 months. I wonder what implications this has for other mathematical complexities. Obviously it helps that Sudoku involves concepts that are very discrete... you can't really do brute force regarding the number line... but there have to be other discrete issues. (For example, every now and then I have the occasional fleeting terror that a sudden technology breakthrough will instantly render all pre-existing SSL encryption worthless.) Back to the Sudoku, I'm also now interested in how many 17-clue solutions there are, and how many 18-clue, and if there's any sort of pattern.
- jakewalker 15y agoIt's funny because the way I play Sudoku is often through sheer brute force as well.
- fennecfoxen 15y agoIn college I wrote a little Sudoku solver for an algorithms class which was more or less brute-force with backtracking (and a little intelligence about which part was the weakest and should be brute-forced first). A fun exercise, but for better or worse, I don't play Sudoku anymore. I solved it; the slowest part of getting the computer to do it for me now is the data entry. I've lost all motivation to do it by hand. (Online + GPL'd: http://random.fennecfoxen.org/webtoys/sudo/sudo.html http://random.fennecfoxen.org/webtoys/sudo/sudo.html )
- Tossrock 15y agoI wrote an intelligent solver (doing set elimination, etc) in Java back in high school, but couldn't get it to solve the harder puzzles. Clearly I was lacking one of the essential implications that allow you solve them manually. I actually never even considered brute forcing it.
- stevewillows 15y agoI'm glad we've got our top minds on this.
- nradov 15y agoThis has been posted before, but for those who haven't read it Peter Norvig has an excellent article on Sudoku solving algorithms. http://norvig.com/sudoku.html http://norvig.com/sudoku.html