Timeline for Verifying the correctness of a Sudoku solution
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 17, 2013 at 10:09 | comment | added | Ralph | @Tony: Very interesting. You already showed that one needs to check $4 \le s \le 9$ squares and that in the cases $s=9,8,7$ 21 checks are necessary. I think, with some more work, the other cases for $s$ can be treated, too. In particular, this gives a nice systematic for the resulting case-by-case analysis. | |
| May 3, 2013 at 11:24 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 2 characters in body; added 49 characters in body
|
| May 3, 2013 at 11:17 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 1627 characters in body; deleted 1 characters in body; Post Made Community Wiki
|
| May 2, 2013 at 7:28 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 1062 characters in body
|
| May 1, 2013 at 7:38 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 14 characters in body; added 9 characters in body
|
| May 1, 2013 at 7:32 | comment | added | Tony Huynh | @Francois: Following Zack's suggestion, I think we can avoid the use of Symmetric Sudokus to get $s \geq 4$. I edited my answer accordingly. | |
| May 1, 2013 at 7:30 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 1253 characters in body
|
| Apr 30, 2013 at 22:22 | comment | added | François Brunault | Symmetric Sudokus can be used to show that $s \geq 4$. For example, start from the grid given in Figure 5 of this article : math.cornell.edu/~connelly/bcc_sudokupaper.pdf and swap the digits 4 and 6 in each of the following rows : 2, 5, 8. Then all rows, all columns as wells as the three squares along the diagonal are correct, but the six other squares are incorrect. You can adapt this for other sets of squares of size 3. | |
| Apr 30, 2013 at 18:47 | comment | added | Zack Wolske | I think you can do $1$ better for s, assuming I have the right construction in mind which works except on a corner set (flip pairs of elements along each side of the rectangle, so that rows keep the same elements on horizontal flips, and the number of vertical flips is even, and vice versa for columns). This just requires an even number of squares be chosen in each row and column, which you do with a corner set, taking $2$, $2$, and $0$. You can make the same construction with $2$ squares in each row and column (like the complement of a minimal set of squares that meets all corner sets). | |
| Apr 30, 2013 at 18:24 | comment | added | Tony Huynh | @Marek: I also cannot see a transformation that swaps rows and squares. | |
| Apr 30, 2013 at 18:16 | comment | added | Tony Huynh | @Francois: Agreed. My bounds are absolute lower bounds on r,c and s (where r, c and s are what you think they are), while the quantity we are actually interested in is r+c+s. By considering the interaction between cells, rows and columns the bound can be improved (probably to 21). | |
| Apr 30, 2013 at 12:12 | comment | added | François Brunault | @Tony : If we only check 6 rows and 6 columns, then there are 9 cells which can be altered indifferently, so we need to check all 9 squares. Using this kind of reasoning, it seems you can improve your lower bound to 18. | |
| Apr 30, 2013 at 9:14 | comment | added | Marek | @Denis: sudoku works on 81 squares, not $3^3 = 27$ as you propose. I think there is no symmetry between rows and squares. E.g., every row intersects 9 distinct columns but every square only intersects three columns. Could you elaborate? | |
| Apr 30, 2013 at 6:34 | comment | added | Tony Huynh | Thanks for the comment. The proposed solution in the original question shows that it is possible to get away with only checking 4 squares (provided you check all the rows and columns also), so I am a bit confused. | |
| Apr 30, 2013 at 1:06 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 56 characters in body; edited body
|
| Apr 30, 2013 at 0:53 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 63 characters in body
|
| Apr 30, 2013 at 0:44 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 83 characters in body
|
| Apr 30, 2013 at 0:30 | history | answered | Tony Huynh | CC BY-SA 3.0 |