Re: [math-fun] Lower Limit Found For Sudoku Puzzle Clues
James Cloos <cloos@jhcloos.com> writes:
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.
OK, I'm not following something here. Doesn't the existence of a uniquely solvable 15-clue puzzle imply the existence of a uniquely solveable 16-clue puzzle? (Just fill in any blank.) So, contrapositively, the non-existence of 16s would imply the non-existence of 15s (and 14s and 13s, etc.) -- Tom Duff. This was just a preliminary test.
I believe an "N-clue puzzle" is defined to mean "A puzzle with N clues all of which are essential". If it is possible to remove one clue, then give it to another person who hasn't seen it and then that person could solve it, then you don't have an N-clue puzzle, but you might have an N-1 clue puzzle. So, redundant clues are not allowed. Interlinked clues are allowed (where there are more than the minimum number, but yet if you removed any one clue the puzzle would then be ambiguous, i.e. not solvable in the ordinary Sudoku sense.) Think about the three rings that are mutually linked, yet none intersects the other: If you break any one ring the entire thing falls apart. [1] That is why 15 might still be possible even though 12 has been disproven (for example). - Robert [1] http://en.wikipedia.org/wiki/Borromean_rings On Mon, Jan 9, 2012 at 13:19, Tom Duff <td@pixar.com> wrote:
James Cloos <cloos@jhcloos.com> writes:
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.
OK, I'm not following something here. Doesn't the existence of a uniquely solvable 15-clue puzzle imply the existence of a uniquely solveable 16-clue puzzle? (Just fill in any blank.) So, contrapositively, the non-existence of 16s would imply the non-existence of 15s (and 14s and 13s, etc.)
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
That's certainly not the definition used in the paper under discussion (at http://www.math.ie/McGuire_V1.pdf). Their computational approach involves iterating over all completed sudoku grids (up to symmetry), enumerating all sets of 16 clues that touch every unavoidable set, and then handing each such 16-clue puzzle to a sudoku solver to check whether or not it has a unique solution. So any 15-clue puzzle would have been found (many times over). --Michael On Mon, Jan 9, 2012 at 5:12 PM, Robert Munafo <mrob27@gmail.com> wrote:
I believe an "N-clue puzzle" is defined to mean "A puzzle with N clues all of which are essential".
If it is possible to remove one clue, then give it to another person who hasn't seen it and then that person could solve it, then you don't have an N-clue puzzle, but you might have an N-1 clue puzzle.
So, redundant clues are not allowed. Interlinked clues are allowed (where there are more than the minimum number, but yet if you removed any one clue the puzzle would then be ambiguous, i.e. not solvable in the ordinary Sudoku sense.) Think about the three rings that are mutually linked, yet none intersects the other: If you break any one ring the entire thing falls apart. [1]
That is why 15 might still be possible even though 12 has been disproven (for example).
- Robert
[1] http://en.wikipedia.org/wiki/Borromean_rings
On Mon, Jan 9, 2012 at 13:19, Tom Duff <td@pixar.com> wrote:
James Cloos <cloos@jhcloos.com> writes:
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.
OK, I'm not following something here. Doesn't the existence of a uniquely solvable 15-clue puzzle imply the existence of a uniquely solveable 16-clue puzzle? (Just fill in any blank.) So, contrapositively, the non-existence of 16s would imply the non-existence of 15s (and 14s and 13s, etc.)
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
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.
Just to add to my last mail - or indeed Sudoku startup clues that have no solution unless say 1 of the initial clues is corrected, or 2, or 3.....
I'm with Tom here, the test is referring to the number of starting clues given in Sudoku specifically and obviously if there are no unique solutions for 16 clues then neither are there any unique solutions for fewer initial clues. The rationale for this is straightforward *if* there were a unique solution with only 15 or fewer start clues then one could take any of those start setups for Sudoku and convert it to a 16 clue start that has that unique solution *but we now know that there aren't any for any 16 clue starts* therefore there are no unique solutions to Sudoku with 16 *or fewer* initial clues. As Tom said "but <blank>" ?? An alternative form of Sudoku would be to provide clues such that there are multiple solutions and the game is to find all of them ;) On 9 Jan 2012, at 22:12, Robert Munafo wrote:
I believe an "N-clue puzzle" is defined to mean "A puzzle with N clues all of which are essential".
If it is possible to remove one clue, then give it to another person who hasn't seen it and then that person could solve it, then you don't have an N-clue puzzle, but you might have an N-1 clue puzzle.
So, redundant clues are not allowed. Interlinked clues are allowed (where there are more than the minimum number, but yet if you removed any one clue the puzzle would then be ambiguous, i.e. not solvable in the ordinary Sudoku sense.) Think about the three rings that are mutually linked, yet none intersects the other: If you break any one ring the entire thing falls apart. [1]
That is why 15 might still be possible even though 12 has been disproven (for example).
- Robert
[1] http://en.wikipedia.org/wiki/Borromean_rings
On Mon, Jan 9, 2012 at 13:19, Tom Duff <td@pixar.com> wrote:
James Cloos <cloos@jhcloos.com> writes:
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.
OK, I'm not following something here. Doesn't the existence of a uniquely solvable 15-clue puzzle imply the existence of a uniquely solveable 16-clue puzzle? (Just fill in any blank.) So, contrapositively, the non-existence of 16s would imply the non-existence of 15s (and 14s and 13s, etc.)
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just to add to my last mail - or indeed Sudoku startup clues that have no solution unless say 1 of the initial clues is corrected, or 2, or 3.....
participants (5)
-
Dave Makin -
David Makin -
Michael Kleber -
Robert Munafo -
Tom Duff