Sudoku: http://www.sudoku.com
"Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. "
Suppose I have just completed a puzzle, and want to verify that my solution is correct.
[list=a][li]I read every row to make sure it has all numbers from 1 to 9.[/li][li]Then I read every column to make sure that it has all numbers from 1 to 9.[/li][li]Then I read every 3x3 box to make sure it has all numbers from 1 to 9.[/list][/li]
Do verify my solution, do I really need to do all three steps, or are two out of three sufficient? In other words, would it be possible to have a grid filled in fitting two out of the three conditions but failing the third?
So clearly you can’t get away with just checking rows and columns, or just checking rows and boxes, or just checking boxes and columns.
In other words, you have to check at least some of each (some rows, some boxes, some columns.) But does that mean you have to check all of each?
For instance, is it possible to have nine rows correct, and nine columns correct, but only eight boxes correct? (By “correct”, I mean “containing 1-9”)
Of course, Xema & ultrafilter, the counterexample was obvious now that you’ve shown it to me. :smack:
I’m changing my question to tim314’s question now - if I am checking the grid, what’s the minimal aount of checking I need to do to verify correctness?
That one, at least, is not possible. If you have all rows correct, then you must have exactly 9 of each digit. If you also have eight boxes correct, then you must have 8 of each digit accounted for in those boxes. The last box must therefore contain one of each digit. The same argument goes for columns. So it’s adequate to check all nine of one category (rows, columns, and boxes), and then check only eight each of the other two categories.
Personally, though, in the rare event that it is useful to check a sudoku, I prefer to check by digits, rather than by rows/columns/boxes. I scan through the 1s in the first three rows (= the first three boxes), making sure that there’s a 1 in each box, and that they’re all in different rows. Then I check the middle three boxes the same way, and the bottom three boxes. Then I do the vertical equivalent, and then I repeat the process for all the other digits.
But even that isn’t usually necessary. The method of guess-and-check is seldom useful in solving sudoku, and most of the times when it’s useful, it’s useful because you quickly reach a contradiction. If you only fill in a digit when you’re certain that it must be correct, then when you have everything filled in, it must be correct, without any need for further checking.
You can do even better. Once you’ve checked that the top three boxes and the top two rows contain one of each digit, you know that the third row must also have one of each. This lets you check, say, all nine boxes, six rows, and six columns, for a total of 21 checks; I think this is minimal. (This won’t work for the variants where the “boxes” are replaced by arbitrarily-shaped regions, though.)