The New Sudoku Players' Forum

[StrmCkr]

pointless

[blue]

Just doing a bit of elementary probability theory shows that picking a correct set of 9 characters 123456789 in any order from all the possible outcomes is 9^9 / 9! which is about 1067 = 2^10 approximately.

(...)

Working out the effective bit content of an elementary check of type xi≠yi given that the sum of the digits in a house must balance to 45 is tricky - I would have to figure out exactly how many ways you can get any assortment of 9 digits 1 - 9 to sum to 45 and it's a bit late at night to do that. Nevertheless, I'm pretty sure it must be less than 1067 which would make the bit content of this type of elementary check much less than 10.

There are 910 different number distributions that work -- e.g. two 7's, two 6's, two 5's and three 3's.
There are 19,610,233 ways to fill the cells.
9^9 / 19,610,233 is about 19.756, or 2^(4.3)

[Leren]

Hi blue,

Thanks for the analysis. My understanding is that there are 19,610,233 ways to fill a house in any order, and there are 910 number distributions that allow the numbers to sum to 45. But they are not all equally probable.

Surprisingly, it seems that the most probable arrangement is the "correct" one, with 9! = 362,880 outcomes.

Your example, for which a representative would be 776655333 can have 9! / 2! / 2! / 2! / 3! = 7,560 outcomes. The least likely outcome, which can be done in exactly one way, is 555555555.

If you checked xi≠yi on 776655333 you would have to do 36 checks and get six failures, and, apart from order, you still wouldn't know what the digits were, they could just as well be 778844333, or some other set of digits with 2-2-2-3 distribution.

So getting back to the "correct" solution, the probability of its outcome is 362,880 / 19,610,233 or about 1/54. Determining a 1/ 54 probability outcome contains about 5.75 information bits. You mentioned earlier that it takes 28 checks to determine this (if you are lucky and the first 28 checks all succeed), so it seems that the average information bit count per check is 5.75 / 28 = about 0.2 bits per check. On the other hand you use this information twice, in carrying out checks on other houses, so it looks like the effective bit rate (to check a correct puzzle) should be doubled to about 0.4 bits per successful check (if they all succeed).

Comparing this with the 555555555 outcome, I think you could determine this with 28 checks, and identify the outcome that has about 24 information bits, so the bit count per failed check in this case is about 0.86.

<edit>

Rethinking this last bit- if you had 555555546 being a minimal deviation from 555555555, then you could carry out as many as [ 6 + 5 + 4+ 3 + 2 + 1 ] 21 checks that all fail. If the 22nd xi≠yi check also failed, you could conclude that what you must have is 555555555, so you have discovered a 24 bit case with at most 22 failed checks, a "bit" more than one bits per failed check.

So, it seems that the bit count per check depends on whether it succeeds or fails.

Any comments ? Is this OK or rubbish ? Leren

PS: It kind of seems obvious that by definition, the average bit content of the 504 xi≠yi checks required to verify a valid Sudoku grid is LOG2 (Total no of grids with all house digits summing to 45 / Total Number of Sudoku grids) / 504 - but only if all 504 checks succeed. Leren

[StrmCkr]

Not sure what your doing or what xi≠yi represents...
all I know is that the bit set jpf uses to verify a solution is correct as all. Sector. The sum =45.*27 is true
When 1111111 is true.

If 101111110 shows up
Digits 2and 9 have a sector that is missing
Which means. You can look up from the 0 information keyed to 27 sectors for each digit 2 and 9
the exact sector with missing digits is identified with a zero
Then identy which of the 9 digits have mutiple placements in that sector. Which translates in the list of cells for that digit

Meaning the probability of guessing the false cells by trial and error can be reduced to a direct search for error conditions.

[Mathimagics]

Not sure what your doing or what xi≠yi represents...

"xi ≠ yi" refers to a generic cell comparison operation. xi and yi are grid entries, assuming a linear grid array, xi = G[xi], or xi = G(ri, ci) for 2d representation.

The original question (from which this thread has long since departed) asked "how many generic cell comparisons are needed to verify any sudoku grid?", and specifically "if we know that all houses sum to 45, can we reduce the # of comparisons needed".

[Leren]

StrmCkr wrote : Not sure what your doing or what xi≠yi represents... all I know is that the bit set jpf uses to verify a solution is correct as all.

We're not questioning the correctness or efficiency of jpf's verification methods. On the contrary, what we are trying to find out is just how inefficient the xi≠yi method really is. It's just a quirky question that denis originally asked and it's a fun exercise to find out the answer. I'm sure that blue's requirement for 504 xi≠yi checks is correct. The question is, why so many ?

Leren

[blue]

Hi blue,

Thanks for the analysis. My understanding is that there are 19,610,233 ways to fill a house in any order, and there are 910 number distributions that allow the numbers to sum to 45. But they are not all equally probable.

Surprisingly, it seems that the most probable arrangement is the "correct" one, with 9! = 362,880 outcomes.

Your example, for which a representative would be 776655333 can have 9! / 2! / 2! / 2! / 3! = 7,560 outcomes. The least likely outcome, which can be done in exactly one way, is 555555555.

If you checked xi≠yi on 776655333 you would have to do 36 checks and get six failures, and, apart from order, you still wouldn't know what the digits were, they could just as well be 778844333, or some other set of digits with 2-2-2-3 distribution.

(...)
Any comments ? Is this OK or rubbish ?

The first part, I understand.
I'm out of my depth on the 2nd part.
You could say just about anything, and I wouldn't know what to make of it.

I don't know what this is worth, but for the ~19.6M cases where the sum is 45, you only need to do an average of ~8.51 "xi≠yi" checks before you know whether it is or isn't an "all 9 digits" case.
[ For the 9^9 cases with "mystery sums", the average is ~7.77 "xi≠yi" checks. ]

Blue.

[Leren]

blue wrote : I'm out of my depth on the 2nd part.

I'll take that as "proof" that it's probably rubbish. That's OK, my thinking is often woolly headed on a new topic. Not only that, there is a lot of parallel thinking and cross posting going on, so it's hard to keep up. We've all been there, done that.

Your last post (I think), gave me what I was looking for. So, there are 19,610,233 ways to fill a house so that the sum is 45 (in any order) and 910 digit distributions that do it. Of these, 362,880 are accounted for by the one digit distribution 123456789. The remainder, 19,247,353 are accounted for by the 909 digit distributions that have at least one digit in the set more than once, and hence at least one missing (in fact at least two digits must be missing, to maintain the sum at 45).

So, in your last post, you say that it takes on average ~8.51 "xi≠yi" checks before you can distinguish between these two parts. And I assume that any one of the 19,610,233 cases is chosen randomly. So there is a 1 in ~ 54 chance that it's one of the 362,880 non-repeating digit cases. So, deciding between which of 54 cases has been chosen equates to about 5.75 bits of information. So, 5.75/8.51 = ~0.67 information bits per "xi≠yi" check, including cases where you are "lucky" and not so lucky, in decising whether a house is Sudoku compliant or not.

I suppose the original "504" problem has taken the "randomness" out of the choice of case issue, and for the whole puzzle, not just one house, so calculating the information bits for a complete Sudoku grid is really a conditional probability issue, and the information bits per "xi≠yi" check would be different for that specific case than for the averages you have calculated (I think).

This is getting so complex I think I'll stop there. Leren

[blue]

Returning to the topic in the opening post ...

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*|
+-------+-------+-------+

[StrmCkr]

Was working on it, on paper logged in to post and blue posted similar to me... Better explained probably..

my numbers match blue so i removed most of what i originally had in this post and went right into practical testing
(6 * 2 * 28) + (9 *16) = 480 <- theoretical minimal


practical test: maximum
selecting 2 cells from each row or Col Or Box list
Row (0,1,3,4,6,7)
Col (0,1,3,4,6,7)
Box ( 0,1,2,3,4,5,6,7,8)
{6*3*36= 648}

Hidden Text: Show

Code: Select all

0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 0,10 0,11 0,18 0,19 0,20 0,27 0,36 0,45 0,54 0,63 0,72
1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 1,10 1,11 1,18 1,19 1,20 1,28 1,37 1,46 1,55 1,64 1,73
2,3 2,4 2,5 2,6 2,7 2,8 2,9 2,10 2,11 2,18 2,19 2,20
3,4 3,5 3,6 3,7 3,8 3,12 3,13 3,14 3,21 3,22 3,23 3,30 3,39 3,48 3,57 3,66 3,75
4,5 4,6 4,7 4,8 4,12 4,13 4,14 4,21 4,22 4,23 4,31 4,40 4,49 4,58 4,67 4,76
5,6 5,7 5,8 5,12 5,13 5,14 5,21 5,22 5,23
6,7 6,8 6,15 6,16 6,17 6,24 6,25 6,26 6,33 6,42 6,51 6,60 6,69 6,78
7,8 7,15 7,16 7,17 7,24 7,25 7,26 7,34 7,43 7,52 7,61 7,70 7,79
8,15 8,16 8,17 8,24 8,25 8,26
9,10 9,11 9,12 9,13 9,14 9,15 9,16 9,17 9,18 9,19 9,20 9,27 9,36 9,45 9,54 9,63 9,72
10,11 10,12 10,13 10,14 10,15 10,16 10,17 10,18 10,19 10,20 10,28 10,37 10,46 10,55 10,64 10,73
11,12 11,13 11,14 11,15 11,16 11,17 11,18 11,19 11,20
12,13 12,14 12,15 12,16 12,17 12,21 12,22 12,23 12,30 12,39 12,48 12,57 12,66 12,75
13,14 13,15 13,16 13,17 13,21 13,22 13,23 13,31 13,40 13,49 13,58 13,67 13,76
14,15 14,16 14,17 14,21 14,22 14,23
15,16 15,17 15,24 15,25 15,26 15,33 15,42 15,51 15,60 15,69 15,78
16,17 16,24 16,25 16,26 16,34 16,43 16,52 16,61 16,70 16,79
17,24 17,25 17,26
18,19 18,20 18,27 18,36 18,45 18,54 18,63 18,72
19,20 19,28 19,37 19,46 19,55 19,64 19,73

21,22 21,23 21,30 21,39 21,48 21,57 21,66 21,75
22,23 22,31 22,40 22,49 22,58 22,67 22,76

24,25 24,26 24,33 24,42 24,51 24,60 24,69 24,78
25,26 25,34 25,43 25,52 25,61 25,70 25,79

27,28 27,29 27,30 27,31 27,32 27,33 27,34 27,35 27,36 27,37 27,38 27,45 27,46 27,47 27,54 27,63 27,72
28,29 28,30 28,31 28,32 28,33 28,34 28,35 28,36 28,37 28,38 28,45 28,46 28,47 28,55 28,64 28,73
29,30 29,31 29,32 29,33 29,34 29,35 29,36 29,37 29,38 29,45 29,46 29,47
30,31 30,32 30,33 30,34 30,35 30,39 30,40 30,41 30,48 30,49 30,50 30,57 30,66 30,75
31,32 31,33 31,34 31,35 31,39 31,40 31,41 31,48 31,49 31,50 31,58 31,67 31,76
32,33 32,34 32,35 32,39 32,40 32,41 32,48 32,49 32,50
33,34 33,35 33,42 33,43 33,44 33,51 33,52 33,53 33,60 33,69 33,78
34,35 34,42 34,43 34,44 34,51 34,52 34,53 34,61 34,70 34,79
35,42 35,43 35,44 35,51 35,52 35,53
36,37 36,38 36,39 36,40 36,41 36,42 36,43 36,44 36,45 36,46 36,47 36,54 36,63 36,72
37,38 37,39 37,40 37,41 37,42 37,43 37,44 37,45 37,46 37,47 37,55 37,64 37,73
38,39 38,40 38,41 38,42 38,43 38,44 38,45 38,46 38,47
39,40 39,41 39,42 39,43 39,44 39,48 39,49 39,50 39,57 39,66 39,75
40,41 40,42 40,43 40,44 40,48 40,49 40,50 40,58 40,67 40,76
41,42 41,43 41,44 41,48 41,49 41,50
42,43 42,44 42,51 42,52 42,53 42,60 42,69 42,78
43,44 43,51 43,52 43,53 43,61 43,70 43,79
44,51 44,52 44,53
45,46 45,47 45,54 45,63 45,72
46,47 46,55 46,64 46,73

48,49 48,50 48,57 48,66 48,75
49,50 49,58 49,67 49,76

51,52 51,53 51,60 51,69 51,78
52,53 52,61 52,70 52,79

54,55 54,56 54,57 54,58 54,59 54,60 54,61 54,62 54,63 54,64 54,65 54,72 54,73 54,74
55,56 55,57 55,58 55,59 55,60 55,61 55,62 55,63 55,64 55,65 55,72 55,73 55,74
56,57 56,58 56,59 56,60 56,61 56,62 56,63 56,64 56,65 56,72 56,73 56,74
57,58 57,59 57,60 57,61 57,62 57,66 57,67 57,68 57,75 57,76 57,77
58,59 58,60 58,61 58,62 58,66 58,67 58,68 58,75 58,76 58,77
59,60 59,61 59,62 59,66 59,67 59,68 59,75 59,76 59,77
60,61 60,62 60,69 60,70 60,71 60,78 60,79 60,80
61,62 61,69 61,70 61,71 61,78 61,79 61,80
62,69 62,70 62,71 62,78 62,79 62,80
63,64 63,65 63,66 63,67 63,68 63,69 63,70 63,71 63,72 63,73 63,74
64,65 64,66 64,67 64,68 64,69 64,70 64,71 64,72 64,73 64,74
65,66 65,67 65,68 65,69 65,70 65,71 65,72 65,73 65,74
66,67 66,68 66,69 66,70 66,71 66,75 66,76 66,77
67,68 67,69 67,70 67,71 67,75 67,76 67,77
68,69 68,70 68,71 68,75 68,76 68,77
69,70 69,71 69,78 69,79 69,80
70,71 70,78 70,79 70,80
71,78 71,79 71,80
72,73 72,74
73,74

75,76 75,77
76,77

78,79 78,80
79,80
Total := 648

practical test: minimal when excluding already checked objects.
selecting 2 cells from each row or Col Or Box list
Row (0,1,3,4,6,7)
Col (0,1,3,4,6,7)
Box ( 0,1,2,3,4,5,6,7,8) Skipping applicable Row cols already checked above , Skipping 1 cell as row/col checks prove it can only be 1 digit

(6*2 * 28) + (9 *14) = 480

Hidden Text: Show

Code: Select all

0,1 0,2 0,3 0,4 0,5 0,6 0,7
1,2 1,3 1,4 1,5 1,6 1,7
2,3 2,4 2,5 2,6 2,7
3,4 3,5 3,6 3,7
4,5 4,6 4,7
5,6 5,7
6,7

9,10 9,11 9,12 9,13 9,14 9,15 9,16
10,11 10,12 10,13 10,14 10,15 10,16
11,12 11,13 11,14 11,15 11,16
12,13 12,14 12,15 12,16
13,14 13,15 13,16
14,15 14,16
15,16

27,28 27,29 27,30 27,31 27,32 27,33 27,34
28,29 28,30 28,31 28,32 28,33 28,34
29,30 29,31 29,32 29,33 29,34
30,31 30,32 30,33 30,34
31,32 31,33 31,34
32,33 32,34
33,34

36,37 36,38 36,39 36,40 36,41 36,42 36,43
37,38 37,39 37,40 37,41 37,42 37,43
38,39 38,40 38,41 38,42 38,43
39,40 39,41 39,42 39,43
40,41 40,42 40,43
41,42 41,43
42,43

54,55 54,56 54,57 54,58 54,59 54,60 54,61
55,56 55,57 55,58 55,59 55,60 55,61
56,57 56,58 56,59 56,60 56,61
57,58 57,59 57,60 57,61
58,59 58,60 58,61
59,60 59,61
60,61

63,64 63,65 63,66 63,67 63,68 63,69 63,70
64,65 64,66 64,67 64,68 64,69 64,70
65,66 65,67 65,68 65,69 65,70
66,67 66,68 66,69 66,70
67,68 67,69 67,70
68,69 68,70
69,70

0,9 0,18 0,27 0,36 0,45 0,54 0,63
9,18 9,27 9,36 9,45 9,54 9,63
18,27 18,36 18,45 18,54 18,63
27,36 27,45 27,54 27,63
36,45 36,54 36,63
45,54 45,63
54,63

1,10 1,19 1,28 1,37 1,46 1,55 1,64
10,19 10,28 10,37 10,46 10,55 10,64
19,28 19,37 19,46 19,55 19,64
28,37 28,46 28,55 28,64
37,46 37,55 37,64
46,55 46,64
55,64

3,12 3,21 3,30 3,39 3,48 3,57 3,66
12,21 12,30 12,39 12,48 12,57 12,66
21,30 21,39 21,48 21,57 21,66
30,39 30,48 30,57 30,66
39,48 39,57 39,66
48,57 48,66
57,66

4,13 4,22 4,31 4,40 4,49 4,58 4,67
13,22 13,31 13,40 13,49 13,58 13,67
22,31 22,40 22,49 22,58 22,67
31,40 31,49 31,58 31,67
40,49 40,58 40,67
49,58 49,67
58,67

6,15 6,24 6,33 6,42 6,51 6,60 6,69
15,24 15,33 15,42 15,51 15,60 15,69
24,33 24,42 24,51 24,60 24,69
33,42 33,51 33,60 33,69
42,51 42,60 42,69
51,60 51,69
60,69

7,16 7,25 7,34 7,43 7,52 7,61 7,70
16,25 16,34 16,43 16,52 16,61 16,70
25,34 25,43 25,52 25,61 25,70
34,43 34,52 34,61 34,70
43,52 43,61 43,70
52,61 52,70
61,70

0,10 0,11 0,19
1,9 1,11 1,18
2,9 2,10 2,11 2,18 2,19
9,19
10,18
11,18 11,19
18,19

3,13 3,14 3,22
4,12 4,14 4,21
5,12 5,13 5,14 5,21 5,22
12,22
13,21
14,21 14,22
21,22

6,16 6,17 6,25
7,15 7,17 7,24
8,15 8,16 8,17 8,24 8,25
15,25
16,24
17,24 17,25
24,25

27,37 27,38 27,46
28,36 28,38 28,45
29,36 29,37 29,38 29,45 29,46
36,46
37,45
38,45 38,46
45,46

30,40 30,41 30,49
31,39 31,41 31,48
32,39 32,40 32,41 32,48 32,49
39,49
40,48
41,48 41,49
48,49

33,43 33,44 33,52
34,42 34,44 34,51
35,42 35,43 35,44 35,51 35,52
42,52
43,51
44,51 44,52
51,52

54,64 54,65 54,73
55,63 55,65 55,72
56,63 56,64 56,65 56,72 56,73
63,73
64,72
65,72 65,73
72,73

57,67 57,68 57,76
58,66 58,68 58,75
59,66 59,67 59,68 59,75 59,76
66,76
67,75
68,75 68,76
75,76

60,70 60,71 60,79
61,69 61,71 61,78
62,69 62,70 62,71 62,78 62,79
69,79
70,78
71,78 71,79
78,79

Total := 480

[Serg]

Hi, Blue!

I'm glad I wrote that 504 was (just) "another upper bound".
It can be done with 480 checks.

Impressive result! Well done!
Paper "Redundant Sudoku Rules" by Bart Demoen and Maria Garcia de la Banda (cited by Mladen) desribes 39 "21 minimum houses" valid configurations for Sudoku solution grids. Did you check all those configurations and found that one configuration only from that list ("skip {r3,r6,r9,c3,c6,c9}") provides 480 checks?

Serg

[blue]

Hi Serg,

I'm sorry it has taken so long for me to respond.
I started to writing something, and instead, ended up asking myself some questions and writing some code to test some new ideas.
I made a very interesting discovery !

Aside: I made an argument, earlier, about the 39 valid configurations ... about how counting each "2 cells" check only once, gave different results for different configurations. The range was 648-690, with only ""skip {r3,r6,r9,c3,c6,c9}"" having the 648 count. Then I mentioned the idea that the "house sums = 45" fact, probably can only reduce the count by no more than 168 (21*8), and so 480 was probably the best that could be done. At that point, it seemed like the 480 count, could only happen for that one configuration.

It turns out, though, that the other 38 configurations, all have redundancies, and that for each one, the count can be reduced to 648.
(More below).

Anway, that opened up the possiblity that using the "house sums" could reduce the count to 480 for each of the configurations !

Old, incorrect comment:

It turns out that for sure, the count can be reduced to 480 for 35 of the 39, and to 484 for the other 4.
The ones where it's only 484, have 3 unchecked boxes and one uncheked row in a band (or the similar thing in a stack).

Updated:

It turns out that for sure, the count can be reduced to 480 for 21 of the 39, and to 484 for 4 others.
The 21 cases where the 480 is definite, are all of the cases where at least one row and at least one column are skipped.
The remaining cases, including the 4 that reduced to 484, have N rows (or N columns) and (6-N) boxed skipped.

I had also written some "solver" code to verify that the 648-168=480 checks for the one configuaration, were minimal in the sense that removing any one of them, allows some bad grids to pass the remaining checks.
I want to try that code on the 4 cases where the lowest ("house sum"-reduced) count seems to be 484.
I'll be too busy, for a day or so, though.

--

The basic idea that leads to the reduction of each of the "649-690" range counts, to 648 is this: Supppse the configuration calls for checking three rows, but only two boxes, in some band. If all of those checks passed, you would know that the 3rd box (also) has 9 distinct entries ... and in particular, the entries in each of its mini-columns are distinct. You can use that, to eliminate some of the checks in the columns that intersect that box. The configuration, in cases like that, will always call for all 3 columns to be checked, and the end result is that 3*3=9 checks can be removed from the list.

More later,
Blue.

[Serg]

Deleted

[Serg]

Hi, Blue!

The basic idea that leads to the reduction of each of the "649-690" range counts, to 648 is this: Supppse the configuration calls for checking three rows, but only two boxes, in some band. If all of those checks passed, you would know that the 3rd box (also) has 9 distinct entries ... and in particular, the entries in each of its mini-columns are distinct. You can use that, to eliminate some of the checks in the columns that intersect that box. The configuration, in cases like that, will always call for all 3 columns to be checked, and the end result is that 3*3=9 checks can be removed from the list.

Yes, I catched your idea. Good point!
I suspected that all other 38 checking schemes should have 480 checks, but I couldn't find your nice elimination for original checking algorithm. It's curious that 4 checking schemes from 39 are still not reducible to "480 checks" checking schemes.

Serg

[Edited. I was wrong saying that checking scheme "skip {r3,r6,r9,b1,b2,b3}" requires 480 checks. (But I cannot still get 484 checks...)]

[StrmCkr]

removed