Timeline for Minimal-information description of sudoku solution (Latin square)
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2018 at 23:04 | comment | added | Gerhard Paseman | Not much more. There are some universal patterns (33 squares, I think) which guarantee a Sudoku solution if it exists. I think it is easy to find these patterns, and possibly work ones way down. Gerhard "Unpublished And Half Remembered Work" Paseman, 2018.10.24. | |
| Oct 24, 2018 at 22:16 | comment | added | David G. Stork | @GerhardPaseman: What is becoming clear is that the assumption that a fixed $17$ cells together with the minimum-information assignment of digits to those cells cannot lead to a tight bound on the number of bits needed to describe a latin square. ZachTeitler's improvement of the question is: How few cells need be specified ahead of time ($k = 23?$) such that an assignment of digits leads to a unique solution such that the total information (in bits) of the cell sub-selection and digit assignments can describe all Latin squares. Presumably the total information will be $\log_2 N$. | |
| Oct 24, 2018 at 21:54 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 199 characters in body
|
| Oct 24, 2018 at 21:46 | comment | added | David G. Stork | @ZachTeitler: Good point: Some of the assignments of digits to $17$ cells will lead to unsolvable puzzles. Indeed, perhaps the better question is how few ($23$?) cells suffice such that some subset can be chosen (with digit assignments) such that the expected information content (in bits) is minimal. (I'll revise the question.) Thanks. | |
| Oct 24, 2018 at 19:19 | comment | added | Zach Teitler | No single selection of $17$ locations will come close to determining all puzzles. Your bit count shows this. On top of that, a lot of bits are "wasted" on unsolvable clues (e.g., two $1$s in the same row). Here's a question. Is there some set of, say, $23$ squares that does uniquely determine all puzzles? $23$ is the least integer greater than $\log_9(N)$, so there are $>N$ ways to fill clues into a set of $23$ squares. My guess is no, you would need more than $23$. | |
| Oct 24, 2018 at 19:07 | comment | added | David G. Stork | @ZachTeitler: My guess/ansatz was that a unique selection of 17 cell locations might uniquely determine all sudoku puzzles, but that set would be arranged like the set in my example, certainly not a row and a column. (Frankly, that would be one of the least constraining arrangements. | |
| Oct 24, 2018 at 18:54 | comment | added | Zach Teitler | ... counting these seems like a challenge, to put it mildly. It will certainly depend on which $17$ squares are chosen for the clue locations. E.g., if the $17$ squares are the first row and first column, then very, very few clue fillings will uniquely determine puzzle solutions! | |
| Oct 24, 2018 at 18:53 | comment | added | Zach Teitler | 1. Can you please explain where $\binom{17}{9}/(2!)^8$ comes from? The number of ways to put $1,1,2,2,\dotsc,8,8,9$ into $17$ squares is $17!/(2!)^8$. If you allow a choice of which digit is the "odd" one ($9$) then you get $9 \cdot 17!/(2!)^8$. Have I misunderstood what you are counting? 2. Presumably the large majority of placements into those $17$ squares fail to uniquely determine a puzzle solution. Either they admit more than one solution (failure of uniqueness) or they admit no solutions — e.g., if the $17$ clue squares have a duplicated digit in a row, column, or region. ... | |
| Oct 24, 2018 at 17:59 | comment | added | Gerhard Paseman | Suppose I give you k bits of information to represent a Sudoku solution. If k is less than log_2 N, how would I use k bits or fewer to distinguish each of the other N-1 solutions? Are you asking about equivalence classes of solutions instead? Gerhard "Finds The Question Itself Puzzling" Paseman, 2018.10.24. | |
| Oct 24, 2018 at 17:27 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 27 characters in body
|
| Oct 24, 2018 at 0:22 | history | edited | David G. Stork | CC BY-SA 4.0 |
added 2 characters in body
|
| Oct 23, 2018 at 22:23 | comment | added | j.c. | You might enjoy reading this old question and its answers: mathoverflow.net/questions/129143 | |
| Oct 23, 2018 at 21:43 | history | asked | David G. Stork | CC BY-SA 4.0 |