Can a sudoku with valid columns and rows be proved valid without evaluating every 3x3 inside it?

2.3k Views Asked by At

I'm trying to solve a computer science challenge and have readily been able to validate whether or not the outside dimensions of a sudoku puzzle are valid. However, it doesn't check the validity of the inside squares and will "validate" the following incorrect sudoku puzzle because the 3x3 squares are not unique 1-9:

[1, 2, 3, 4, 5, 6, 7, 8, 9],

[2, 3, 4, 5, 6, 7, 8, 9, 1],

[3, 4, 5, 6, 7, 8, 9, 1, 2],

[4, 5, 6, 7, 8, 9, 1, 2, 3],

[5, 6, 7, 8, 9, 1, 2, 3, 4],

[6, 7, 8, 9, 1, 2, 3, 4, 5],

[7, 8, 9, 1, 2, 3, 4, 5, 6],

[8, 9, 1, 2, 3, 4, 5, 6, 7],

[9, 1, 2, 3, 4, 5, 6, 7, 8]

My question is this: if a sudoku puzzle has all valid columns and rows in the 9x9, is there a way to grab a single other set of values from the puzzle (say, for instance, the first 3x3) and know the whole puzzle to be correct? Or must one check every 3x3 for an otherwise valid whole puzzle square?

2

There are 2 best solutions below

4
On BEST ANSWER

Suppose you have valid Soduko. Now swap rows 6 and 7.

The "outside measurements" are still all valid. The 3, $3\times3$ boxes along the top are valid, but the remaining 6 likely are not.

0
On

As proved in https://mathoverflow.net/q/129143, it is insufficient in general to additionally check three (or less) of the $3\times3$ blocks.

On the other hand, it is enough to check four blocks: for instance, the three blocks on the diagonal and one more block.

Together with rows and columns, this makes $9+9+4=22$ checks. It is in fact possible to make do with 21 checks (e.g., by checking suitable 6 rows, 6 columns, and 9 blocks). This is the best possible, as is also proved at the linked page.