Re: [math-fun] sudoku
Thanks, Scott.
From the link you provided I see that another interesting question is, What is the smallest number n such that *every* sudoku solution can be reduced to n entries having that solution as its unique completion?
Also: Is there a consensus about how to evaluate the "difficulty" of a given sudoku puzzle? (I was suprised to read at that URL that some feel that a large proportion of puzzles of least known size -- 17 -- are "easy".) --Dan ---------------------------------------------------------------------------------------- <<
What is the smallest number of filled squares that can uniquely determine an extension filling all 81 squares?
--Dan
There are many 17-clue sudokus known. The jury is still out whether a 16-clue sudoku exists. Specific sudoku grids which require 17+ clues are known. If you require rotational symmetry of initial clue positions I think 18-clues in the minumum known. Most of the 17-clue sudokus are not very difficult, so globally minimal clue count doesn't seem to correlate with difficulty. See http://www.sudoku.com/forums/viewtopic.php?t=605 for an extensive discussion.
Hi Dan, There's a partial consensus on evaluating sudoku difficulty. People typically order logic techniques by perceived difficulty, then rate a puzzle by the most difficult technique it requires. Some sets of techniques have an obvious ranking, but disparate techniques have no universal consensus on difficulty. Many basic logic techniques are equivalent to a 9 rooks problem on one of four subgrids: a single value in rows/columns, or the set of all values in a row, a column, or a box. Finding a unique value in a cell or in a row/column/box is a rank 1 rooks deduction. Inferences requiring pairs are rank 2 deductions. Sudoku-ans give names like naked pair, hidden pair, or X-wing to rank 2 deductions. Any rank k rooks deduction has a dual rank 9-k deduction, so rank 4 deductions exhaust this set for standard sudokus. The set of basic sudoku deductions is generally agreed to consist of some N-rook deductions plus deductions based on box/row or box/column interactions. Most people exclude rank 4 rook deductions from the basic set, and some even exclude certain rank 3 deductions. The next addition to "advanced" deductions is "forcing chains". These are deductions of candidate exclusion or inclusion in the transitive closure of basic pairwise candidate implications. Sudoku-ans give names to subsets of forcing chains (e.g., bivalue or bilocation chains) and techniques that handle forcing chain subsets (e.g., simple coloring). The techniques above are not universal, but there's not much understanding of difficulty refinement beyond forcing chains. And from forcing chains and above there's little consensus on difficulty rating. I think the question of sudoku difficulty gives some interesting math questions to investigate. Best, - Scott
Thanks, Scott.
From the link you provided I see that another interesting question is, What is the smallest number n such that *every* sudoku solution can be reduced to n entries having that solution as its unique completion?
Also: Is there a consensus about how to evaluate the "difficulty" of a given sudoku puzzle? (I was suprised to read at that URL that some feel that a large proportion of puzzles of least known size -- 17 -- are "easy".)
--Dan --------------------------------------------------------------------------------
<<
What is the smallest number of filled squares that can uniquely determine an extension filling all 81 squares?
--Dan
There are many 17-clue sudokus known. The jury is still out whether a 16-clue sudoku exists. Specific sudoku grids which require 17+ clues are known.
If you require rotational symmetry of initial clue positions I think 18-clues in the minumum known.
Most of the 17-clue sudokus are not very difficult, so globally minimal clue count doesn't seem to correlate with difficulty.
See http://www.sudoku.com/forums/viewtopic.php?t=605 for an extensive discussion.
dasimov@earthlink.net wrote:
From the link you provided I see that another interesting question is, What is the smallest number n such that *every* sudoku solution can be reduced to n entries having that solution as its unique completion?
The answer to this is 19, although I can't prove it. There is a canonical grid 123456789 456789123 789123456 231564897 564897231 897231564 312645978 645978312 978312645 which requires 19 clues. Here is a proof that at least 18 are required: The grid can be partitioned into 9 disjoint 3x3 Latin squares of the form 123 231 312 (three of these in each stack of three columns). At least 2 clues must be included from each of the 3x3 Latin squares - if only one clue then the other two digits could be interchanged within that Latin square to obtain another completed sudoku grid. (This has been discovered by lots of people.) It's feasible on the computer to run through all possible ways of choosing two clues from each 3x3 Latin square, and none of these give a puzzle with a unique solution. So at least 19 are required. Guenter did this check, and found one with 19. Finally, if this grid has a 19, then all grids have a 19 (and probably an 18). This completed grid has the largest symmetry group of all grids, and there's a principle that grids with higher symmetry don't have puzzles with smaller numbers of clues. Of course I can't prove that part... Gary McGuire
A set of clues C is "legal" if there is no repetition of a digit in any row column or box. It's not hard to give a legal set C of five elements which cannot be extended to a sudoku solution. Is there an example of this with #C<5? DG At 03:25 AM 11/14/2005, you wrote:
dasimov@earthlink.net wrote:
From the link you provided I see that another interesting question is, What is the smallest number n such that *every* sudoku solution can be reduced to n entries having that solution as its unique completion? The answer to this is 19, although I can't prove it.
There is a canonical grid 123456789 456789123 789123456 231564897 564897231 897231564 312645978 645978312 978312645 which requires 19 clues. Here is a proof that at least 18 are required: The grid can be partitioned into 9 disjoint 3x3 Latin squares of the form 123 231 312 (three of these in each stack of three columns). At least 2 clues must be included from each of the 3x3 Latin squares - if only one clue then the other two digits could be interchanged within that Latin square to obtain another completed sudoku grid. (This has been discovered by lots of people.)
It's feasible on the computer to run through all possible ways of choosing two clues from each 3x3 Latin square, and none of these give a puzzle with a unique solution. So at least 19 are required. Guenter did this check, and found one with 19.
Finally, if this grid has a 19, then all grids have a 19 (and probably an 18). This completed grid has the largest symmetry group of all grids, and there's a principle that grids with higher symmetry don't have puzzles with smaller numbers of clues. Of course I can't prove that part...
Gary McGuire
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I've summarized many of the posts and discoveries here about Multiplicative Magic Squares in my latest maa.org column http://www.maa.org/editorial/mathgames/mathgames_11_07_05.html Ed Pegg Jr
Excellent column, and proud to see my name! Ed, I was not aware that you planned to write a column on the subject, I worked without informing you on my latest results. Main recent results: 1) Yes, additive-multiplicative magic squares are improvable. I have examples of 8x8 and 9x9 additive-multiplicative magic squares with smaller constants than the previously known examples http://mathworld.wolfram.com/Addition-MultiplicationMagicSquare.html (40 times smaller for the 8x8 square) 2) Probably the smallest possible example of 11x11 pandiagonal multiplicative magic square. Ed (or others), I can send you Excel files including these squares, if you are interested. Let me know. And thanks for your mention of my 100$ prize + bottle of Champagne. Who will win the prize? Christian. -----Message d'origine----- De : math-fun-bounces+cboyer=club-internet.fr@mailman.xmission.com [mailto:math-fun-bounces+cboyer=club-internet.fr@mailman.xmission.com] De la part de ed pegg Envoyé : lundi 14 novembre 2005 21:15 À : math-fun Objet : [math-fun] Multiplicative magic squares I've summarized many of the posts and discoveries here about Multiplicative Magic Squares in my latest maa.org column http://www.maa.org/editorial/mathgames/mathgames_11_07_05.html Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
2) Probably the smallest possible example of 11x11 pandiagonal multiplicative magic square.
Christian
Did you fill in any of the smaller values?
--Ed Pegg Jr
My two best examples of 11x11 pandiagonal multiplicative squares, meaning that each square has 44 alignments to get the same product: -with the smallest possible product (P=160986670580736000000, SLE=580): 260 160 85 38 345 200 116 1 84 54 33 14 135 88 52 16 204 114 69 500 290 5 100 29 12 42 27 220 130 80 34 285 184 102 57 460 250 145 2 105 72 44 13 192 110 65 32 255 152 92 25 348 6 21 180 15 56 36 11 156 96 51 380 230 125 58 23 300 174 3 140 90 55 26 240 136 76 48 340 190 115 50 435 8 28 9 132 78 45 22 195 128 68 19 276 150 87 20 70 232 4 7 108 66 39 320 170 95 46 375 228 138 75 580 10 35 18 165 104 64 17 -with the smallest largest entry: (P=1441031935035813120000, SLE=341): 104 85 38 220 161 100 27 252 174 93 11 290 217 4 13 153 114 66 253 200 135 56 25 243 168 87 341 8 65 34 190 154 92 57 242 184 125 54 280 203 124 1 117 102 5 26 170 133 88 23 225 162 84 319 248 196 116 31 9 78 51 209 176 115 50 270 207 150 81 308 232 155 2 130 119 76 22 187 152 110 46 250 189 112 29 279 6 39 62 10 91 68 19 198 138 75 297 224 145 108 28 261 186 3 143 136 95 44 230 175 132 69 275 216 140 58 310 7 52 17 171 First square checked OK by Edwin Clark and Don Reble. But first time that I send the second square = not checked by somebody else. The 44 products should be OK, and all integers should be distinct. I think that it will be impossible to construct 11x11 pandiagonal multiplicative squares with best values. Christian.
participants (6)
-
Christian Boyer -
dasimov＠earthlink.net -
David Gale -
ed pegg -
Gary McGuire -
Scott Huddleston