The New Sudoku Players' Forum

[denis_berthier]

Minimum number of checks
On another forum, I've found a meaningless question leading to an interesting one.
Suppose a 9x9 Sudoku grid is filled with digits from 1 to 9.
At this point, don't suppose any constraint (different values) on rows/columns/blocks (if we assumed all of them, no more test would be needed).

Now suppose one wants to check that the grid is indeed a valid Sudoku solution and one has already checked that the 27 sums for each row/column/block is 45. These 27 checks can't be enough for all the possible grids (otherwise Sudoku would be an integer linear programming problem with 81 unknowns and 27 linear constraints). There must be some counter-example, but I don't know any.

Now the question: what's the minimum number of elementary checks of type xi≠yi (where xi and yi are the digits in different cells in the same row/column/block) necessary to be sure in all possible cases that the grid is a valid Sudoku solution?
To be more precise, all the xi≠yi must be preceded by a universal quantifier: find the minimum n such that for all such (sum-checked) grids and for all n choices of xi≠yi constraints, these additional tests are enough to make sure the grid is a valid Sudoku solution.

(At first, I thought the answer would be almost trivial if we chose existential quantifiers instead: choose the cell-pairs for which the constraint is not satisfied. But the way to the final answer may not be so trivial finally. So, it might be a second question. No time to investigate now.)

[Leren]

Well, I've got some spare time on my hands, so I'll take the bait on this one.

First of all, the "digits" in a Sudoku aren't really numbers at all, they are un-ordered symbols, of which there are nine and a valid Sudoku grid is one in which every row, column and box has all the nine different symbols.

So, a check that the sum of the "digits" is 45 being a single check is meaningless, there are no doubt many ways that this could be accomplished with not all "digits" represented.

What you actually do, to check that a house is OK is to check that all the symbols are different. In each house this takes 8+7+6+5+4+3+2+1 = 36 xi≠yi checks.

So, naively, for the full grid, this would take 36 x 27 = 972 checks. The only shortcut I can see at the moment is that you can subtract at least 2 from this number. This is because, if there is one duplicated symbol in a row, it must also be duplicated in its column and box, so the minimum number of "errors" is 3.

So my first stab at an answer is 970. That would be an upper bound. How did I do ?

Leren

PS - I've already thought of something that will reduce that number. Let's just take an example. If you check, for example, that r1c1 <> r1c2 & r1c3 and also that r1c2 <> r1c3, these three checks are also valid as checks in Box 1.

So, I think that row/column - box intersections will reduce the number by quite a lot. By how much ? I'm to tired to figure that out right now.

Leren

PPS - OK I've had my tea, and I couldn't stop thinking about this silly problem (as you do).

Let's see if this works. If you carry out the xi≠yi checks for each row and each column, how many xi≠yi checks have you implicitly carried out for each box ? I think the answer is 18 (3 in each row and column of the box). So you've only got to do 18 more in each box (essentially that for each symbol in the box you only have to carry out the checks for the symbols that don't share same row or column in the box)

So my new upper bound is 970 - 9 *18 = 808.

Leren

[denis_berthier]

the "digits" in a Sudoku aren't really numbers at all, they are un-ordered symbols, of which there are nine and a valid Sudoku grid is one in which every row, column and box has all the nine different symbols. So, a check that the sum of the "digits" is 45 being a single check is meaningless, there are no doubt many ways that this could be accomplished with not all "digits" represented.

Obviously, if we speak of sums, we can't replace digits by arbitrary symbols. You are making the question meaningless by changing it. The real question is, does a sum being 45 carry any useful information? Obviously it does: for instance, the 9 digits can't be all the same, except if they are all 5. But it excludes many more combinations (with duplicates) than this. The whole problem is computing the information carried together by the 27 sum constraints.

[Leren]

OK just for fun I'll have one more go at this.

From your previous post I realised that, if you are told that the sum of all the house digits is 45, and there is a mistake somewhere, at least two digits must be repeated in the house and two digits are missing.

Code: Select all

+-------+-------+-------+
| 5 7 6 | 8 2 1 | 3 4 9 |
| 8 1 2 | 9 3 4 | 5 6 7 |
| 9 3 4 | 5 7 6 | 1 8 2 |
+-------+-------+-------+
| 7 4 1 | 3 5 8 | 2 9 6 |
| 3 5 8 | 6 9 2 | 4 7 1 |
| 6 2 9 | 1 4 7 | 8 5 3 |
+-------+-------+-------+
| 4 6 3 | 7 1 5 | 9 2 8 |
| 1 8 5 | 2 6 9 | 7 3 4 |
| 2 9 7 | 4 8 3 | 6 1 5 |
+-------+-------+-------

Here is a correct grid, and along the lines I outlined in my previous post, the number of xi≠yi checks you would carry out, all correct, would be 972 - 9*18 = 810.

Code: Select all

+-------+-------+-------+
| 5#7 6 | 8 2 1 | 3 4 9 |
| 8 1 2 | 9 3 4 | 5 6 7 |
| 9 3 4 | 5 7 6 | 1 8 2 |
+-------+-------+-------+
| 7 4 1 | 3 5 8 | 2 9 6 |
| 3 5 8 | 6 9 2 | 4 7 1 |
| 6 2 9 | 1 4 7 | 8 5 3 |
+-------+-------+-------+
| 4*7 3 |#7#1 5 | 9*1 8 |
| 1#8 5 | 2 6 9 | 7 3 4 |
| 2*8 7 | 4 8 3 | 6*2 5 |
+-------+-------+-------

Here is the same grid, with what I think is a minimum number of errors. What I've done is changed r9c2 from 9 to 8 and to compensate, r9c8 = 2, r7c2 = 7 and r7c8 = 1.

These 4 cells are marked with a *. Now you'll note that the sum of each row, column and box is 45.

But there are bad pairings in Column 2 - r17c7 are both 7 and r89c7 are both 8 and in Row 7 - r7c24 are both 7 and r7c58 are both 1. I've marked the extra cells in the bad pairings with #.

Now suppose you carry out xi≠yi checks as before, but you are unlucky and you carry out 806 checks without finding the errors. On the 807 th check you must find an error.

So, if I'm right, and this arrangement is the minimal error set consistent with your statement of the problem, the answer is 807.

Leren

[dobrichev]

Hi Denis,

An interesting article Redundant Sudoku Rules might be related to your question.

[denis_berthier]

An interesting article Redundant Sudoku Rules might be related to your question.

Yes, it's related. It computes the minium number of xi≠yi constraints necessary to ensure all the usual 27 ones (answer 21).
I think "my" question is harder, as it introduces a very different kind of constraints. Not sure it's worth spending too much time on it, though.

[blue]

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.

[blue]

Hi Denis !

These 27 checks can't be enough for all the possible grids (otherwise Sudoku would be an integer linear
programming problem with 81 unknowns and 27 linear constraints).

That's a curious comment.
Sudoku "is" an integer linear programming problem with 729 unknowns (one for each candidate) and 324 linear constraints.
For reasons similar to the ones in the previous post, the 324 constraints can be reduced to 81 + 9 * 21 = 270 constraints.

Best Regards,
Blue.

[denis_berthier]

Hi Denis !

These 27 checks can't be enough for all the possible grids (otherwise Sudoku would be an integer linear
programming problem with 81 unknowns and 27 linear constraints).

That's a curious comment.
Sudoku "is" an integer linear programming problem with 729 unknowns (one for each candidate) and 324 linear constraints.
For reasons similar to the ones in the previous post, the 324 constraints can be reduced to 81 + 9 * 21 = 270 constraints.

Hi Blue,
We aren't speaking of the same thing. How do you write Sudoku as an integer linear programming problem with 81 unknowns and 27 linear constraints (namely the 27 house sums)?

[eleven]

504 (xi ≠ yi) checks, is another upper bound.
...
[ 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 ]

Nice observations.

[Addded:]I don't think, that columns 78 need to be checked. Do i miss something ?

[blue]

[Addded:]I don't think, that columns 78 need to be checked. Do i miss something ?

Somehow, yes.

Code: Select all

+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | 1 2 . |
+-------+-------+-------+
| . . . | . . . | 3 4 . |  swap 3 & 4 in r4
| . . . | . . . | . . . |
| . . . | . . . | 2 1 . |  swap 2 & 1 in r6
+-------+-------+-------+
| . . . | . . . | 4 3 . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

[Leren]

Seeing as I'm not taking this too seriously I might as well make a complete fool of myself and have another go. As expected, I think blue has the right number of 504, but that applies to a grid that is completely correct, so all 504 xi≠yi checks "check out correctly. But what if the grid contained the minimum number of errors that retained the 27 house sums to 45 ?

Code: Select all

+-------+-------+-------+
| 5#7 6 | 8 2 1 | 3 4 9 |
| 8 1 2 | 9 3 4 | 5 6 7 |
| 9 3 4 | 5 7 6 | 1 8 2 |
+-------+-------+-------+
| 7 4 1 | 3 5 8 | 2 9 6 |
| 3 5 8 | 6 9 2 | 4 7 1 |
| 6 2 9 | 1 4 7 | 8 5 3 |
+-------+-------+-------+
| 4*7 3 |#7#1 5 | 9*1 8 |
| 1#8 5 | 2 6 9 | 7 3 4 |
|#2*8 7 | 4#8 3 | 6*2 5 |
+-------+-------+-------

I've repeated my second grid from my previous post and added two more bad checks that I missed. So, in this bad grid, there are six bad checks : r1c2=r7c2, r8c2=r9c2, r7c2=r7c4, r7c5=r7c8, r9c1=r9c8 & r9c2=r9c5.

So, if 6 bad checks is indeed the minimum number, can't we say that if you get, in the worst case scenario, to 499 good checks, the remaining 5 checks must ummm check out OK!

So, I'll suggest that 499 is a new upper bound, based on the proviso that 6 is the minimum number of grid errors that maintains the 27 * 45 sums requirement.

Leren

Code: Select all

+-------+-------+-------+
| 5#6#7 | 8 2 1 | 3 4 9 |
| 8 1 2 | 9 3 4 | 5 6 7 |
| 9#4#3 | 5 7 6 | 1 8 2 |
+-------+-------+-------+
| 7#4 1 | 3 5 8 | 2 9 6 |
| 3 5 8 | 6 9 2 | 4 7 1 |
| 6 2 9 | 1 4 7 | 8 5 3 |
+-------+-------+-------+
| 4#6#3 | 7 1 5 | 9 2 8 |
| 1 8 5 | 2 6 9 | 7 3 4 |
| 2 9#7 | 4 8 3 | 6 1 5 |
+-------+-------+-------

PS it was easy to produce the invalid grid above with just 4 checks that would fail, so I guess the upper bound must be increased to 501.

Leren

[eleven]

Somehow, yes.

Thanks. Yes, somehow i was blind for swaps in the same box. Probably because all the UR's and UA's need a second box.

@Leren: If in the last box you have

Code: Select all

 . 2 5
-------
 . . .
 . 2 5
 . 3 4

instead of

Code: Select all

 . 2 5
-------
 . . .
 . 5 2
 . 3 4

you would find the error with the last check 504 (compare r6c8 and r8c8) using blues' method above.

[blue]

@Leren: If in the last box you have (...)

Right idea ... nice
You need the right column sums in c8 & c9 too, though.
One small change, then:

Code: Select all

 . 2 5
-------
 . . .
 . 2 5
 . 4 1

instead of

Code: Select all

 . 2 5
-------
 . . .
 . 5 2
 . 1 4

[eleven]

Stand corrected. It's simply too hot here