3 ms·
It's not explicitly stated in the article, but it's very important that we can ask for a whole row or column. If we can only ask for rows, then Peggy can cheat
by jlebar 10y ago
It's not explicitly stated in the article, but it's very important that we can ask for a whole row or column. If we can only ask for rows, then Peggy can cheat by constructing a "solution" that duplicates a number within a column.
- jstanley 10y agoIs it then also important that we are able to ask for a whole 3x3 square? Or does the availability of rows+columns cover this case implicitly?
- Manishearth 10y agoNo, you can construct sudoku solutions where the row/column thing is satisfied but not 3x3 (the simplest one is by staggering the rows by 1. subsquares are mentioned in the post (and are a part of the interactive prover)
- heinrich5991 10y agoI think it is explicitly mentioned here: >The procedure can be repeated (with a new permutation each time) to minimize this chance, with Victor asking to reveal a row, column, or 3x3 subsquare each time, until he is certain that Peggy has a solution.
- Manishearth 10y agoYeah, the first round in the post is just an example. General rounds can ask for anything.