The New Sudoku Players' Forum

[Leren]

Sorry for my stupidity but I'm just not following this. Can you draw out whole the modified grid for that last case ?

Leren

[blue]

Here's one example:

Code: Select all

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

Where the last 21 checks are in c8, and set to happen in this order ... say:

r4c8≠r1c8, r4c8≠r2c8, r4c8≠r3c8
r5c8≠r1c8, r5c8≠r2c8, r5c8≠r3c8
r6c8≠r1c8, r6c8≠r2c8, r6c8≠r3c8
r7c8≠r1c8, r7c8≠r2c8, r7c8≠r3c8, r7c8≠r4c8, r7c8≠r5c8, r7c8≠r6c8
r8c8≠r1c8, r8c8≠r2c8, r8c8≠r3c8, r8c8≠r4c8, r8c8≠r5c8, r8c8≠r6c8

I suppose it should be asked: is there a better (but still "fixed") order for those checks, that makes it impossible using band & row swaps and an optional c8/9 swap ... to put the puzzle above, into a form where only the last check would fail ?

[Leren]

Hi blue,

As I expected, your example contains 4 cases of bad checks, which I think is the minimum.

It's obvious that if you start with a valid Sudoku grid and change just 1 digit then to re-balance the 45 rule in it's row, column and box, you have to make at least a second digit change in the first digit's row, column and box. So, naively, it sounds like the minimum number of bad checks would be 6. However you and I have both come up with clever tricks to reduce the number of bad checks to 4. I can't see any juggling of the puzzle that will make these bad checks go away. In your case you have an excess of one in digits 1, 2, 4 and 5 and no amount of puzzle juggling (without further digit changes) will make those 4 excesses go away, so there should be at least 4 bad checks in a juggled puzzle.

I think your 504 methodology would work in a valid Sudoku grid and show no bad checks, and you could stop there and proclaim the grid as a valid Sudoku grid without actually having seen it. However, in a minimally bad grid, which, for the moment, we will assume has an excess in 4 digits, and four potentially bad checks, then if we follow your 504 methodology, we must pick up one of those four bad checks at some stage. In the best (or is that worst ?) case this would be at check number 501, since the other 3 would also be bad. Of course you could follow some other less efficient methodology, and pick up your first bad check at 504, but we are looking for a minimum here.

Of course you would probably pick up the bad check at some earlier stage in your 504 methodology, but suppose you altered the order of your checks, such that you don't encounter a bad check until the 501 th ? What's the probability of that ? Well, I think it's the same probability that you have a bag full of 504 marbles, 500 white and 4 black and you look for the probability that the first 500 marbles that you pick up are all white. While I've been writing this post I looked up a probability calculator and I think I've got it correctly keyed in, and the answer it gives is 0.0000000003764187751562973001951318041370279887076144149729547664717379781007130159822375448152242404 approximately

So, to answer Denis's question, I think the minimum number of checks is 501, although I would have to say that this would be more correctly described as an extremely unlikely maximal minimum [ I just love oxymorons].

Leren

PS As usual, I now think you might be almost right. Carefully thinking about your post I see you have managed to carry out 20 Column 8 checks OK, although there is a typo in your post in the last line (tests 345 should be r8). The last pair check fails, and this implies at least one other pair check must fail in the column, at least one of r123457c8 = r9c8. It's obvious that you can do something similar in Column 9, with the first 20 checks being OK there, and the 21st failing.

But suppose you have carried out the 20 OK checks in both columns before the 21st check in either column. That would, I think, be 502 checks successfully completed. Whichever row you pick, the 503 rd check must fail, strangely enough, implying that not only the 504 th check must also fail, but that there are at least two other checks that would fail in the puzzle but needn't be included in your 504 protocol.

What about the probability of this happening by chance ? It looks like we have a bag of 504 marbles, only 2 being black, and you pick the first 502 as white.

The calculator says 0.0000078891728991132569661396699170059011013285367162106724730979204140237937454637255830098772444696 for this one.

So maybe the extremely unlikely maximal minimum checks number is 503, one less than 504 even though the minimum number of "errors" in a false grid is, I think, 4, in 2 rows or columns.

How's that sound ? Leren

[blue]

Hi Leren,

... there is a typo in your post in the last line (tests 345 should be r8).

Fixed. Thanks.

But suppose you have carried out the 20 OK checks in both columns before the 21st check in either column. That would, I think, be 502 checks successfully completed. Whichever row you pick, the 503 rd check must fail, strangely enough, implying that not only the 504 th check must also fail, but that there are at least two other checks that would fail in the puzzle but needn't be included in your 504 protocol.

There are no checks in column 9. Once boxes 3,6,9 and columns 7,8 have been checked, columm 9 is guaranteed to be OK.
Eleven's idea (with my "touch up") has things set up so that 3 of the 4 errors are among the checks that were removed in getting down to the 504 count.

I suppose it should be asked: is there a better (but still "fixed") order for those checks, that makes it impossible using band & row swaps and an optional c8/9 swap ... to put the puzzle above, into a form where only the last check would fail ?

The answer to that, turns out to be "no".
The example grid, could have been better though.

If I had thought about it more, I would have had the errors in c8, distributed like they are in c9 -- with only one box containing two *'s.
Then it wouldn't be necessary to swap c8/c9 to get something for an order where the last check is between a cell in r123c8, and one in one in r456c8.

Cheers,
Blue.

[Leren]

Hi blue

Amazing, even though the minimum number of errors in a "corrupted' grid is, I'm reasonably sure, 4, your protocol, effectively eliminates the need to find 3 of them.

So our number is 504, and the probability of requiring all 504 checks a minimally corrupted grid is about 0.001984. Awesome analysis, as I expected.

Leren

[Leren]

I guess that's about it for this topic.

Thanks to denis for coming up with this very interesting and entertaining question, blue, for his very clear thinking solution and eleven for his input.

Leren

[denis_berthier]

I guess that's about it for this topic.
Thanks to denis for coming up with this very interesting and entertaining question, blue, for his very clear thinking solution and eleven for his input.
Leren

It's great you all found a solution so fast. Actually, I didn't think it would be possible to compute it. Finally, it's not more difficult than the other problem dealt with in the paper mentioned by Dobrichev.
As I mentioned, the original question is not genuinely from me. Someone on a forum stated that "Simply sum each row, column and box. If every number is 45, the solution is 100% certain to be correct". I was sure this couldn't be enough but I had no idea how many more xi≠yi checks would be required. Quite a lot, finally.

Still not sure this is very interesting, but it suggests a complementary, very open question:
Let's call K-Sudoku the puzzle with the usual Sudoku constraints plus the 27 house sum constraints (K because they are Kakuro-like constraints). Of course, the latter ones are logical consequences of the first and they don't add anything to the problem. But suppose now that, by some (very unrealistic) magic, they can be used at any time during solving and they are (computationally/mentally) free of any cost. Can that change drastically the difficulty of a puzzle (wrt any measure of difficulty: SER...)?

[RSW]

Leren points out in the second post that the 9 digits are really just unordered symbols, normally with no other meaning except that each one is unique. Using the coincidental mathematical properties of the symbols to aid in testing for a solution is certainly a valid option. However, we could create other properties for the symbols as well. And these properties could be more suitable for confirming valid solution grids. For example if we associate a bit pattern property to each symbol, we could perform bitwise operations along rows, columns and boxes, which are just as fast as addition, and could provide superior results. The bit patterns I'm thinking of are as follows:

Code: Select all

Symbol  Bit Pattern
------  -----------
  1      000000001
  2      000000010
  3      000000100
  4      000001000
  5      000010000
  6      000100000
  7      001000000
  8      010000000
  9      100000000


If we have a valid grid, then if we OR (inclusive OR) the bit patterns of each symbol in a house, then the result should always be 111111111. A parallel wordwise OR operation is just as fast as addition. However, we now only have to do 27 tests to validate the solution.

[Mathimagics]

Someone on a forum stated that "Simply sum each row, column and box. If every number is 45, the solution is 100% certain to be correct". I was sure this couldn't be enough but I had no idea how many more xi≠yi checks would be required. Quite a lot, finally.

Compute the house sums as sum of d * 10^(9-d). If all houses sum to 123456789 the grid is valid.

[Leren]

Hi denis,

I think we have gone about as far as we can go with this topic and I must admit that the question you ask in your last post is difficult for me to understand - I personally can't see it leading anywhere.

However, .... for me this topic has, strictly speaking, never been about vanilla Sudoku at all, precisely because, in asking the x≠y questions, you admit the possibility that the grid is not a vanilla Sudoku grid.

So, suppose you define a KSudoku_N as being a Sudoku-like latin square puzzle, that has all the house sums equal to 45 and has N x≠y checks that will fail, out of the naive maximum possible of 810 (without double counting).

So a KSudoku_0 is just a vanilla Sudoku, and I think we can pass over that case, because it has been flogged to death over the last 25 years or so, and all the smart guys are at the top of their learning curves and in their comfort zones with that.

Now a corollary of the work we did in the thread was that the next N > 0 was 4, and we tricked up the examples so that a KSudoku_4 could also survive 503 x≠y checks.

But there are lots of other questions that might be asked about a KSudoku_4. How many absolutely different such grids are there ? How many essentially different grids are there ? Are there solving tricks that differ from vanilla Sudoku ?

I'm sure the list could go on ad infinitum ( or is that ad nauseum ? ). At least it would get the smart guys' brains whirring figuring out the answers to these sorts of questions or even thinking up the right questions to ask in the first place.

And you'll get the credit for dreaming up this variant - maybe you could even call it a DBudoku_N. Well, at least it's a thought.

Leren

[denis_berthier]

Someone on a forum stated that "Simply sum each row, column and box. If every number is 45, the solution is 100% certain to be correct". I was sure this couldn't be enough but I had no idea how many more xi≠yi checks would be required. Quite a lot, finally.

Compute the house sums as sum of d * 10^(9-d). If all houses sum to 123456789 the grid is valid.

Yep, that's a much better test than the mere sums.

[denis_berthier]

Hi denis,

I think we have gone about as far as we can go with this topic and I must admit that the question you ask in your last post is difficult for me to understand - I personally can't see it leading anywhere.
...
Leren

Hi Leren
Even I was not convinced of the interest of going further.

[JPF]

Just for fun:

1) Assuming that x1,x2,...,x9 are integers such that 1<=xi<=9, then:

(x1,x2,...,x9) is a permutation of (1,2,...9) iff:

(x1+10)(x2+10)...(x9+10) = 33522128640

2) and yes, checking 21 houses is enough, see here

JPF

[Leren]

OK, I'll take the bait on this one again. This really is a fun topic. Forget denis's original question for now.

What is the minimum number of checks of any sort required to verify that a grid is correct ? In this case you are not told that the "digits" sum to anything, or even that there are not more than 9 different "digits" in the grid.

Looking at RSW's post, and taking the sensible (IMHO) view that the "digits" are "really" just distinct symbols (a view that I've had for as long as I can remember) then to check that a house is correct you have to carry out 8 inclusive OR operations to verify that a house contains 9 different symbols. From JPF's post he says you only have to check 21 houses (I took a quick look at the link and it looks OK to me).

So, putting this together, it looks like the minimum number of inclusive OR operations is 21 * 9 = 189.

Anything wrong with that, or can anyone come up with a smaller number ? It's OK if the answer is yes, for me failure is always an option

The main thing I'm unsure about is whether it is possible to get a house result of 111111111 with any other set of symbols that what is in RSW's list.

Leren

<> Changed the 8 to 9 for 189 operations

[RSW]

The main thing I'm unsure about is whether it is possible to get a house result of 111111111 with any other set of symbols that what is in RSW's list.

Since each symbol has only a single 1 bit, and each one is different, there is no other way of getting 111111111 unless every symbol appears at least once. Since there are only nine available positions in each house, a value of 111111111 guarantees that each symbol is present exactly once, so it must be a valid house arrangement.