[math-fun] Lower Limit Found For Sudoku Puzzle Clues
http://idle.slashdot.org/story/12/01/08/1845258/lower-limit-found-for-sudoku... Posted by <http://www.monkey.org/%7Etimothy/>timothy on Sunday January 08, @10:46AM from the 17-ain't-young dept. ananyo writes "An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 19 according to certain rules. Gary McGuire of University College Dublin shows in a <http://www.math.ie/McGuire_V1.pdf>proof posted online [PDF] that the minimum number of clues or starting digits needed to complete a puzzle is 17; <http://www.nature.com/news/mathematician-claims-breakthrough-in-sudoku-puzzle-1.9751>puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given." --- co-chair http://ocjug.org/
The earlier report I read on this (possibly in arxivblog) said that they had only proven that there were no 16-clue puzzles with unique solutions, and that <13 clue puzzles had been ruled out by others. Whether 13, 14, or 15 clue puzzles with unique solutions exist is still, according to that report, an open question. The brute force search on 16 clue puzzles took a year; I believe it said 7 million core-hours. -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
That doesn't make any sense: if you have a 15-clue puzzle with a unique solution, you can fill in any remaining square with its correct value to produce a 16-clue one. --Michael On Mon, Jan 9, 2012 at 10:39 AM, James Cloos <cloos@jhcloos.com> wrote:
The earlier report I read on this (possibly in arxivblog) said that they had only proven that there were no 16-clue puzzles with unique solutions, and that <13 clue puzzles had been ruled out by others.
Whether 13, 14, or 15 clue puzzles with unique solutions exist is still, according to that report, an open question.
The brute force search on 16 clue puzzles took a year; I believe it said 7 million core-hours.
-JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
[Repying to a random mail in the thread. -JimC] It was arxivblog where I first read about this: http://www.technologyreview.com/blog/arxiv/27469/ My excuse shall be that I was only just awake both the day it was in arxivblog and the next day when it hit /. and here. :-( The only just awake is, at least, accurate. It seems the arxivblog post was edited after it was mailed (I subscribe to an email feed) to agree with the discussion here. -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
participants (3)
-
James Cloos -
Michael Kleber -
Ray Tayek