Returning to the topic in the opening post ...
blue wrote:504 (xi ≠ yi) checks, is another upper bound.
It's 28 checks in 9 boxes, plus 21 checks in 6 rows (r1,r2,r4,r5,r7,r8, say), and 21 checks in 6 columns (c1,c2,c4,c5,c7,c8).
For boxes, if the 1st 8 positions contain distinct numbers (7*8/2 = 28 checks), and the sum is correct, then the 9th position can only contain the mssing number.
For rows, if, for example, boxes 1,2,3 each contain the full set of numbers, 1..9, and if rows 1&2 also contain the full set, then row 3 doesn't need to be checked: the numbers in row 3 are what's left after 2 copies of 1-9 for the rows, are removed from 3 copies of 1-9 from the boxes ... leaving a full set in row 3.
[ The "row sum" for row 3, is redundant for the same reason ... it's 3 * 45 - 2 * 45 = 45, if the other sums are correct ]
Columns are similar.
For rows & columns ... take r1, for example: from the box checks we would know that there are distinct numbers in c123, distinct numbers in c456 and distinct numbers in c78. If the c123 numbers are distinct from the c456 numbers (3*3 checks), and the c78 numbers are distinct from the c123456 numbers (2*6 checks), then there are distinct numbers in columns 1-8, and like with boxes, since the row sum is correct, the 9th column can only contain the missing number.
9 * (7 * 8 / 2) + (6 + 6) * (3 * 3 + 2 * 6) = 504 checks total.
I'm glad I wrote that 504 was (just) "another upper bound".
It can be done with 480 checks.
The six "skipped" house checks being {r3,r6,r9,c3,c6,c9} is still the right idea.
Checking the rows and columns first, instead of the boxes, gives the improved result.
Like in was for boxes in the argument above, the 6 rows + 6 columns, need 28 checks each.
For the boxes, and for box 1 for example: After the row & column checks, we know that r1c123 contains 3 distinct numbers, and similarly r2c123, r123c1 and r123c2, contain 3 distinct numbers. The accounts for 4*3 = 12 of the usual 36 checks for the box.
Also, r3c3 hasn't been checked against any other cell, and using the house sum, we can remove the 8 checks for r3c3 -vs- the other cells.
That leaves 36 - 12 - 8 = 16 checks for the box (and for each of the remaining boxes).
(6 + 6) * 28 + 9 * 16 = 480 checks !
---------
An agrument for why 480 is (likely ?) to be the absolute minimum:
- If we forget about the house sums for the moment, It turns out different (valid) ways of choosing which 6 houses to skip, have different "(xi≠yi)" counts, when we count a check only once, when in the list for two overlapping houses -- a row or column, overlapping a box.
- For the "skip {r3,r6,r9,c3,c6,c9}" option and it's isomorphic equvalents, that count is 648.
- For any other option, the count is strictly larger than 648.
For "skip {r1,c1,c4,b3,b6,b9}", the count is 690, for example. - Bringing house sums into play, it seems like the best we can hope for, is to eliminate eight (xi≠yi) checks for each house checked.
- 648 - 21 * 8 = 480
What's lacking here, is an example along the lines of the one that eleven proposed earlier -- a proposed "grid with errors", where the first 479 checks would pass, and only the 480th would fail. [
Added: below. ]
Cheers,
Blue.
- Code: Select all
If the last check is r9c8 -vs- r8c9, this grid passes the first 479 checks, and fails on #480.
+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3*|
| 7 8 9 | 1 2 3 | 4 5 6 |
+-------+-------+-------+
| 2 3 1 | 5 6 7 | 9 4 8 |
| 5 6 4 | 2 9 8 | 3 1 7 |
| 8 9 7 | 3 1 4 | 2 6 5 |
+-------+-------+-------+
| 3 4 5 | 6 7 1 | 8 9 2*|
| 9 1 2 | 8 4 5 | 6 7 3*|
| 6 7 8 | 9 3*2*| 5 3*2*|
+-------+-------+-------+