Timeline for Verifying the correctness of a Sudoku solution
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 5, 2017 at 2:26 | history | suggested | jeq | CC BY-SA 3.0 |
Copied images to imgur.com, as they not being displayed because of broken link. Added link to original image sources via Wayback Machine.
|
| Nov 5, 2017 at 2:03 | review | Suggested edits | |||
| S Nov 5, 2017 at 2:26 | |||||
| May 17, 2013 at 10:04 | vote | accept | Ralph | ||
| May 17, 2013 at 9:49 | vote | accept | Ralph | ||
| May 17, 2013 at 10:04 | |||||
| May 17, 2013 at 9:49 | vote | accept | Ralph | ||
| May 17, 2013 at 9:49 | |||||
| May 6, 2013 at 19:12 | answer | added | Emil Jeřábek | timeline score: 19 | |
| May 4, 2013 at 8:27 | history | edited | Tony Huynh |
added the sudoku tag
|
|
| May 4, 2013 at 2:09 | answer | added | François Brunault | timeline score: 19 | |
| May 2, 2013 at 13:58 | answer | added | Emil Jeřábek | timeline score: 14 | |
| Apr 30, 2013 at 20:14 | comment | added | Zack Wolske | @Ralph: how would one verify anything other than a complete set of $9$ elements? You can check that subsets of them do not contain repeats, but knowing that can only verify a full array after you check at least $3$ subsets (when the subsets are 8/9), which seems to be a lot more work. | |
| Apr 30, 2013 at 16:52 | comment | added | Emil Jeřábek | I didn’t think about it in terms of algorithms, I simply considered subsets of the 27 standard row, column, and block checks. There is obviously room for more general strategies, but on the other hand, making it too general may trivialize the question: for example, if you’d count access to individual cells instead of the standard checks, the answer is 81, which is not very illuminating. | |
| Apr 30, 2013 at 14:04 | comment | added | Ralph | Emil, that's very interesting. It would be great if you still have your notes. BTW: Have you specified a formal definition of what a "check" is ? (e.g. did you only consider algorithms that always check full columns, rows, etc. or did you also take algorithms into account that check only parts of them ?) | |
| Apr 30, 2013 at 13:11 | comment | added | Emil Jeřábek | I have entertained this very question some time ago. (Being a logician, I also axiomatized the consequence relation “if checks $x_1,\dots,x_n$ are correct, then check $x$ is correct”.) If I remember correctly, the optimal number was indeed 21. I’ll try to look for my notes, but I’m not sure I still have them, I cleaned up my desk recently. | |
| Apr 30, 2013 at 5:33 | comment | added | Benjamin Dickman | Related on at least a superficial level: mathoverflow.net/questions/104714/… | |
| Apr 30, 2013 at 0:30 | answer | added | Tony Huynh | timeline score: 17 | |
| Apr 29, 2013 at 21:44 | comment | added | user30304 | I think the tag compressed-sensing could be added to this post. nuit-blanche.blogspot.co.uk/2013/04/… goo.gl/xl3EQ | |
| Apr 29, 2013 at 21:35 | comment | added | Ralph | @Denis: Thanks. I'll correct it later. | |
| Apr 29, 2013 at 21:30 | comment | added | Ralph | @François: Exactly! I think your conclusion in the 2nd comment is just the row-version of what I described for columns in the paragraph after the pics. | |
| Apr 29, 2013 at 21:03 | comment | added | Denis Serre | (A2) doesn't work if three of the four subsquares are aligned. | |
| Apr 29, 2013 at 20:55 | comment | added | François Brunault | If we consider the $c_i$, $r_j$ and $s_k$ as elements in the free abelian group with basis $\{1,\ldots,9\}$, then relations of the form $r_1+r_2+r_3=s_1+s_2+s_3$ show that e.g. correctness of $r_1,r_2,r_3,s_1,s_2$ implies correctness of $s_3$. | |
| Apr 29, 2013 at 20:45 | comment | added | François Brunault | You can recognize a mathematician in that he always checks his Sudoku is correct because he knows that at this point he has only proved unicity :) | |
| Apr 29, 2013 at 19:15 | history | asked | Ralph | CC BY-SA 3.0 |