A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has to check by definition 27 arrays of length 9.

Q1: Are there verification strategies that reduce this number of checks ?

Q2: What is the minimal number of checks that verfify the correctness of a (correct) solution ?

http://imageshack.us/a/img542/1809/sudoku1.jpg http://imageshack.us/a/img607/9485/sudoku2.jpg

The following simple observation yields an improved verfication algorithm: At first enumerate rows, columns and subsquares as indicated in pic 2. Suppose the columns $c_1,c_2,c_3$ and the subsquares $s_1, s_4$ are correct (i.e. contain exactly the numbers 1 to 9). Then it's easy to see that $s_7$ is correct as well. This shows:

(A1) If all columns, all rows and 4 subsquares are correct, then the solution is correct.

Now suppose all columns and all rows up to $r_9$ and the subsquares $s_1,s_2,s_4,s_5$ are correct. By the consideration above, $s_7,s_8,s_9$ and $s_3,s_6$ are correct. Moreover, $r_9$ has to be correct, too. For, suppose a number, say 1, occurs twice in $r_9$. Since the subsquares are correct, the two 1's have be in different subsquares, say $s_7,s_8$. Hence the 1's from rows $r_7, r_8$ both have to lie in $s_9$, i.e. $s_9$ isn't correct. This is the desired contradiction.

Hence (A1) can be further improved to

(A2) If all columns and all rows up to one and 4 subsquares are correct, then the solution is correct.

This gives as upper bound for Q2 the need of checking 21 arrays of length 9.

Q3: Can the handy algorithm (A2) be further improved ?