The New Sudoku Players' Forum

[blue]

Hi eleven,

The boxes are skipped, but rows and columns containing thier mini-rows and mini-columns, aren't.
It's just a way to group mini-rows and mini-columns together.
"By box", helps you remember that checks against the (1,1) position and the containing mini-rows/columns, are skipped.

I'm working on a follow-up post, with another picture and a "legend" for deciphering the markups.
Very soon ...

Blue.

[blue]

I think I have figured out the the smallest number of checks for each of the configurations, now.
It's 480 for all of the configurations with both a skipped row, and a skipped column.
It's 484 for the rest.

I attached a picture below, showing the details.

Following the description for the 18's configuration in the post (now 2) above, should help with deciphering what the markings mean.

Legend:

Thin horizontal lines in band (blue), indicate a cells to skip checks against in columns.
Thin vertical lines in band (green), indicate cells to skip checks against in rows.
Thick lines in boxes (red), indicate mini-rows and mini-columns where each check is skipped.
Vertical lines mean skip checks in mini-columns, horizontal lines mean skip checks in mini-rows.
The only thing that isn't shown, is a mark in the (1,1) position of tested boxes.
In isomorphic variations of the configuarions, they should map to positions in skipped rows and skipped columns.

The configurations where the count can only be reduced to 484, all share a common feature: a skipped box, with marks for both column and row positions to skip checks against. Having them all together in the box, means 4 skipped "mini-xxx" checks for a box, coincide with 4 skipped "xxx" checks ... where "xxx" is row or column. Shifting the thin horizontal line out of the box (when it's possible), always results in situation where recursive application of the 3 rules that eleven mentioned, doesn't "close things up" properly.

480-484.png (39.8 KiB) Viewed 949 times

[Serg]

Hi, eleven!

Code: Select all

     |
   1 * *
-- * 5 6 ---
   * 8 9
     |

r4578 c4578 8*28 b5689 4*16
r9c9 2*22 (b3,b7)

r12, c12 4*25, b1 16
r3, c3 2*22

8*28 + 4*25 + 4*22 + 5*16 = 492 !!

I checked this example and got 492 checks too. (I also found 2 typos, colored by red.) I'll try to understand Blue's checking sequence.

Serg

[Serg]

Hi, Blue!
I don't understand your method

Serg

[Edited. I removed my silly questions.]

[eleven]

Thanks Serg,

for reading my method so carefully.

Thanks blue,

from your graphic i could see the redundant checks of my method.
The point is, that i do it house by house, i.e. i start with a house and count all comparisons needed to prove, that it has all digits, then the next one and so on. This turned out to count redundant checks in those cases.

For nr 18 it looked like that (in the constellation shown in your graphic):

skipped r1, c1, b3678

Code: Select all

  |
--1 2 *--
  4 5 *
  * * 9
  |

- verify rows 2345 and columns 2345 with 28 checks each.
- now the 4 boxes 1245 all must have 2 distinct minirows an columns, and can be verified with 16 checks
- with the 4 boxes all minirows must be distinct, and we can verify r6 and c6 with 22 checks
- now in band and stack 2 two boxes and 3 lines are verified, so also b6 and b8

- now we verify r78 and c78, need only 25 checks each because the minirows of b68 must be distinct
- then box 9 needs 16 checks
- at the end we verify r9 and c9, because of the 2 verified boxes we need 22 checks each
- with the 3 columns c789 and 2 boxes 69 b3 is verified, with r789 and b89 b7.

So we had 8*28 + 4*16 + 2*22 + 4*25 + 16 + 2*22 = 492 checks.

BUT:
With the verification of b3 and b7 also all minirows/columns must be distinct, especially r23c789 and r789c23, which we have checked in the first step.
So we can leave them out and substract 4*3=12 from the overall count, getting the desired 480.

[blue]

Hi Serg & Eleven,

BUT:
With the verification of b3 and b7 also all minirows/columns must be distinct, especially r23c789 and r789c23, which we have checked in the first step.
So we can leave them out and substract 4*3=12 from the overall count, getting the desired 480.

Right !

Here's a sequence that works out nicely:

Code: Select all

b2459      4*28
r456       3*(28-2*3)   subtracting mini-row checks in b45
c456       3*(28-2*3)   subtracting mini-col checks in b25
b68        provably valid, now (3r-2b, 3c-2b rules)
r789       3*(28-2*3)   subtracting mini-row checks in b89
c789       3*(28-2*3)   subtracting mini-col checks in b69
b37        provably valid, now (3r-2b, 3c-2b rules)
r23,c23    2*(28-2*3)   subtracting mini-r/c checks in b23
r23,c23    2*(28-2*3)   subtracting mini-r/c checks in b47
b1         1*(28-4*3)   subtracting mini-r/c checks in r23/c23
r1,c1      provably valid, now (3b-2r, 3b-2c rules)

4*28+
3*(28-2*3)+
3*(28-2*3)+
3*(28-2*3)+
3*(28-2*3)+
2*(28-2*3)+
2*(28-2*3)+
1*(28-4*3)= 480

----

The way I showed the counts for case 18, earlier, was related to these observations:

Forgetting about the "sums = 45" thing for the moment ...

• Tested rows have 27 check between cells in distinct boxes, and 9 checks for cells in a common mini-row.
• Tested columns have 27 check between cells in distinct boxes, and 9 checks for cells in a common mini-column.
• Boxes have 18 checks between cells in distinct rows and distinct columns, 9 checks for in a common mini-row, and 9 checks for cells in a common mini-column.
• On the first look, checks in mini-rows/mini-columns can only be skipped when both the box and row/column are skipped.

We can use those numbers to add up the total number of checks, assuming every house is tested:

• R/c: 18*27 checks between cells in distinct boxes.
• Boxes: 9*18 checks between cells in distinct rows and columns.
• Mini-r/c: 54*3 checks between cells in the same mini-row/mini-column.
  (This can be viewed as 9 boxes containing 3 minirows and 3 minicolmns each ... with 9*(3+3) = 54).
• Total: 18*27+9*18+54*3 = 810

More later ... things to do ...

One thing to mention:

Above, I wrote: "On the first look, checks in mini-rows/mini-columns can only be skipped when both the box and row/column are skipped".
When we factor in skipped houses and do the sums above, with (only) that idea in mind ... the totals vary from 648 to 690, depending on which houses are skipped.

A closer look, though, reveals that in every skipped box, we can skip either 3 mini-rows, or 3 mini-columns.
In my last picture, those are shown as thick red lines in the skipped boxes, showing the direction of the mini-xxx's that can be skipped.
If we factor that into the sums, too, they come out at 648 for each configuration of skipped houses.

[Serg]

Hi, Blue!
I am very amazed! I expected you demonstrated some "backdoor" tricks to get 480 checks for configuration number 18. But you published very straightforward solution without any "tricks". Very impressive!

Code: Select all

b2459      4*28
r456       3*(28-2*3)   subtracting mini-row checks in b45
c456       3*(28-2*3)   subtracting mini-col checks in b25
b68        provably valid, now (3r-2b, 3c-2b rules)
r789       3*(28-2*3)   subtracting mini-row checks in b89
c789       3*(28-2*3)   subtracting mini-col checks in b69
b37        provably valid, now (3r-2b, 3c-2b rules)
r23,c23    2*(28-2*3)   subtracting mini-r/c checks in b23
r23,c23    2*(28-2*3)   subtracting mini-r/c checks in b47
b1         1*(28-4*3)   subtracting mini-r/c checks in r23/c23
r1,c1      provably valid, now (3b-2r, 3b-2c rules)

4*28+
3*(28-2*3)+
3*(28-2*3)+
3*(28-2*3)+
3*(28-2*3)+
2*(28-2*3)+
2*(28-2*3)+
1*(28-4*3)= 480

Frankly speaking, I don't see yet the way to get such solutions from your graphic diagram, but I hope I'll catch the method in some time.
Very impressive work!

Serg

[eleven]

... I don't see yet the way to get such solutions from your graphic diagram ...,

I guess, that's not hard then. Just try to avoid checks which are skipped in the graphic. E.g. the last one (for which i needed 498 checks):

Code: Select all

   |
   1 * *
   * 5 6
   * * 9
   |

b1569 4*28
c789 3*22 -> b3
r456 3*22 -> b4
r123 3*22 -> b2
c456 3*22 -> b8
r789 3*22 -> b7
c23 2*21

4*28+15*22+2*21=484

[StrmCkr]

nice work blue,

"common mini-row" is the point i like the most it was the foundation for my first post on minimizing checks

using the mini-rows for Rows/boxes and mini-cols for cols/boxes

as

graphical nodes

which are used for the "xi ≠ yi" {vs each cell individually}

the biggest difference for me was/is using sets and containers for Setwise operations

meaning the 3 cells in the mini- row/col is a set of digits found in the cells and the cells are the container.

to solve the first row:
mini Row digits of first box * mini Row digits 2nd box
[0,1,2] * [3,4,5] = [] =>> means that for this statement to be true. set[0,1,2] cant contain anything from set[3,4,5]
or simplified

[0,1,2] <> [3,4,5] =>> Checks non-equality of two sets {meaning it returns true if either set has digits from the other.
the 2nd check
for the row is [1..9] - ( [0,1,2] + [3,4,5]) = [6.7.8]
{ [set of all digits ]- [mini Row digits of first box + mini Row digits 2nd box] = mini Row digits 3rd box}

or cycle to fit the "xi ≠ yi" requirements
[0,1,2] <> [6,7,8]
[3,4,5] <> [6,7,8]

{solves the first row}

...... Thoughts...........?