The New Sudoku Players' Forum

[Serg]

deleted

[StrmCkr]

deleted

[Serg]

Hi, StrmCkr!
Here is an example of proper solution grid (i.e. having sums of rows/columns/boxes equal to 45) to be checked:

126453789
456789123
786126456
231564897
564897231
897231564
312645978
645978312
978312645

Basically it is MC grid, where 4 cells only were changed (they are colored by red). This grid passes checks for r1, r2, r4, r5, r7, r8, c1, c2, c4, c5, c7, c8. But those checks don't garantee different digits in r1c3 and r2c3 cells (in your notation they are cell 2 and cell 11).

This is original MC grid:

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

Serg

[blue]

Hi 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...)]

I do have a list of 484 checks for an eqivalent scheme: "skip {c1,c4,c7,b1,b4,b7}"
I'm a little confused myself, about whether they're adequate.

I put some "output" lines in the code, to tell me what it had done in producing them.
The output isn't making sense ... part of it, anyway ... compared with what the code is supposed to be doing.
I may have a bug.

Before I look into it, though ... I need to work with my solver code a little, to try to speed it up for "2-clue" puzzles that aren't expected to have a solution. If that works out, I'll use it to try to find a problem with the 484 checks.

Cheers,
Blue.

[eleven]

If i understood blues' comments right, i could do the checks in the "missing box123, rows 369" case this way:
9 columns: 9*28 checks (we can drop one digit because of sum 45)
rows r4578: 4*28 checks
boxes 456789: 6*13 checks (3 minicols, 2 minirows have different digits, so 15 checks are redundant)
rows 12: 2*21 checks:
boxes 123 now must have different digits. Otherwise one would be missing, but then we would have it 3 times in the rest of each column and at least 2 times in another box of that stack.
This saves 7 of 28 checks.
So we have 13*28 + 6*13 + 2*21 = 484 checks.

[edit:] no, in the boxes only 8+13 of 36 checks are redundant. That gives 496 checks ...

So maybe this way:
cols 124578, rows 4578: 10*28
boxes 456789: 6*16
now for columns 369: 28-6 each, 3*22
rows12: 2*21

10*28 + 6*16 + 3*22 + 2*21 = 484

[Serg]

Hi, eleven!

So maybe this way:
cols 124578, rows 4578: 10*28
boxes 456789: 6*16
now for columns 369: 28-6 each, 3*22
rows12: 2*21

10*28 + 6*16 + 3*22 + 2*21 = 484

Well done! I think it's right solution. After checking columns 369 it turns out, that constraint "all-different digits" is true for B1, B2 and B3 boxes (see paper "Redundant Sudoku Rules"), and this helps in rows 12 calculation. Nice!

Serg

[eleven]

Thanks Serg (nice to read from you again),
i didn't read the paper (had no access), but i think that my simple deduction above is correct.

[Serg]

Hi, eleven!

i didn't read the paper (had no access), but i think that my simple deduction above is correct.

The paper can be accessed by Mladen's link, posted in this thread earlier (site arxiv.org): Redundant Sudoku Rules.
Lemma 4.1 from this paper says that if a band in Sudoku solution grid has 3 rows with all different digits each and 2 boxes with all different digits each, then 3rd box has all different digits too. No so difficult to prove though.

Serg

[eleven]

Thanks, this worked for me.

[StrmCkr]

thanks for the example serg.

my code has a simplification i was eliminating all cells in a box where Row= Row and Col=Col made for easier coding... back to the drawing board for that. and i was trying to justify it with my set checking engine which inst the same...
should be easy enough to add the 18 checks back in.

{still prefer my other method of using nodes and sets}

my other ideas is that a list of cell sets cannot repeat values in full for any sector
ie...
from the mc example
{2,18}, {11,18} = (67)

but that would be tabling probably not the same thing.
36 digit combinations listing 1+ for each of the 14 data points that match the set
then
any of the 36 points >=2 are false.
any of the 14 data points = zero indicates the 2 cells share the same 1 digit.

[blue]

Nice work, eleven !

After a lot of experimenting, I've update my earlier post about the possiblity of reducing things to 480 checks.
Currently it reads:

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.

The 14 cases that remain, are still a challenge for my (still) unsophisticated code.
All I know for sure, is that the thier earlier reductions to 480 (in theory), were all (definitely) invalid.

In case anyone wants to play with them, here's a list:

Code: Select all

skip {c1,c4,c7,b1,b4,b8}
skip {c1,c4,c7,b1,b5,b9}
skip {c1,c4,b2,b3,b4,b7}
skip {c1,c4,b2,b3,b5,b8}
skip {c1,c4,b2,b3,b5,b9}
skip {c1,c4,b2,b3,b6,b9}
skip {c1,c4,b2,b3,b6,b7}
skip {c1,c4,b2,b5,b6,b7}
skip {c1,b1,b2,b3,b4,b7}
skip {c1,b1,b2,b3,b4,b8}
skip {c1,b1,b2,b3,b5,b9}
skip {c1,b1,b2,b3,b6,b9}
skip {c1,b1,b2,b4,b6,b7}
skip {c1,b2,b3,b4,b6,b9}
skip {c1,b2,b3,b6,b7,b8}
skip {c1,b3,b4,b6,b7,b8}
skip {c1,b2,b3,b4,b7,b8}

Below is a pic showing the 39 configurations.
The particular forms (37 of them) were taken from the mathoverflow page that JPF linked to earlier.
(Two were missing)

Cheers,
Blue.

39-configurations.png (40.06 KiB) Viewed 1054 times

[eleven]

I made 5 more tries with the following (skipped) box patterns:

Code: Select all

 * 2 3     1 * *    * * *    * * 3    1 * *
 * 5 6     * 5 6    * 5 6    * 5 *    * 5 6
 7 * 9     * 8 9    * 8 9    * 8 9    * * 9


These are the counts i got:
skip {c1,c4,c7,b1,b4,b8} 486
skip {c1,c4,b2,b3,b4,b7} 486
skip {c1,b1,b2,b3,b4,b7} 484
skip {c1,b1,b2,b4,b6,b7} 488
skip {c1,b2,b3,b4,b7,b8} 498


I only used these properties (as given by blue), simply because i did not find other redundancies:
- If a house has 8 different digits, from the sum 45 also the 9th is distinct
- If in a band 3 boxes and 2 rows have all 9 digits, then also the 3rd row.
- If in a band 3 rows and 2 boxes have all 9 digits, then also the 3rd box.

Checks needed then:
28 for a house
-3 with a distinct minirow (column)
-6 with 2
-7 line with 3
-12 box with 2 distinct minirows and 2 minicolumns

My strategy was quite simple:
Start with (at least 2) pairs of rows and columns, where the most (non skipped) boxes can be validated with 16 checks.
Then in that order:
1. Add a 3rd line (not skipped) in bands/stacks with 2 full boxes and 2 full lines (which makes the 3rd box checked)
2. If a non skipped box is left, add (up to) 2 rows and columns and check it (if there are more boxes, take the cheapest)
3. Complete a band/stack with 2 verified boxes with (the cheapest) 2 or 3 lines

Hidden Text: Show

----------------
skip {c1,c4,c7,b1,b4,b8}

Code: Select all

 * 2 3
 * 5 6
 7 * 9


r124578c4578 10*28, b23569 5*16
r36 2*22 (->b14): rows 1-6, boxes 1-6 checked

c23 2*22, b7 16

r9 22 (->b8)
Note: box 8 (skipped) could be verified with 16 checks (and prove c4 and r9),
but i can't see a redundancy in the 22 row checks.

10*28+5*22+6*16 = 486

----

4 boxes:
skip {c1,c4,b2,b3,b4,b7}

Code: Select all

1 * *
 * 5 6
 * 8 9


r4578,c5678 8*28, b5689 4*16
r69 2*22 (-> b47): rows 4-9, boxes 4-9 checked
c7 22 (->b3)

(a)
c23 2*22
r12 2*25, b1 16
r3 22 (->b2)

8*28+2*25+6*22+5*16=486

(b)
c123 3*22 (->b1)
r123 3*22 (->b2)

8*28+9*22+4*16 = 486

---
5 boxes
skip {c1,b1,b2,b3,b4,b7}

Code: Select all

 * * *
 * 5 6
 * 8 9

r4578c4578 8*28, b5689 4*16
r69 2*22 (->b47)
c69 2*22 (->b23)
r123 3*22 (b1)
c23 2*21

8*28+7*22+2*21+4*16 = 484

----
skip {c1,b1,b2,b4,b6,b7}

Code: Select all

 * * 3
 * 5 *
 * 8 9

r4578c4578 8*28, b589 3*16
c6 22 (->b2)
r9 22 (->b7)
r12 2*22, b3 16
c9 22 (->b6)
r36 2*22 (-> b14)
c23 2*21

8*28 + 7*22 + 2*23 + 4*16 = 488

---
skip {c1,b2,b3,b4,b7,b8}
1 * *
* 5 6
* * 9

r4578c4578 8*28, b569 3*16
c9 22 (->b3)
r6 22 (->b4)

r12c23 4*25, b1 16

r3 22 (->b2)
c6 22 (->b8)
r9 22 (->b7)

8*28 + 4*25 + 5*22 + 4*16 = 498

[eleven]

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.

That's strange. While for pattern 14 in your list i get 480 with my greedy method, i can't see something better than 492 for number 18.
What am i missing ?

Hidden Text: Show

r1 c1 b2347

Code: Select all

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

r4578 c4578 8*28 b5689 4*16
r69 2*22 (b47)
c69 2*22 (b23)
r23, c23 4*22, b1 16

8*28 + 8*22 + 5*16 = 480

---------------------------------------
r6 c6 b2347

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 !!

[Edit:] Corrected typos, thanks to Serg

[blue]

Hi eleven,

I couldn't really decipher your method, or how your counts were derived
This is what worked for me:

#18 : skip {r1,c1,b3,b6,b7,b8}


b12459 : skip checks against the cell in the (1,1) position
r23789 : skip checks against the c1 cell
c23789 : skip checks against the r1 cell
r56 : skip checks against the c7 cell
c56 : skip checks against the r7 cell
b38 : skip checks in mini-rows
b67 : skip checks in mini-columns
(xi-yi) counts:

R/c cross-box -- # of tested rows & columns times 21, always
2*8*21= 336
Boxes, cross-r&c -- # of tested boxes times 14, always
5*14 = 70
Same mini-r/c, by box -- # varies by box
b1: 6
b2,4,5,9: 4*14
b3,7,6,8: 4*3
16*21 + 5*14 + (6+4*14+4*3) = 480

[eleven]

Hi blue,

i couldn't really decipher your method either.
I would read, that boxes 3678 are checked, but they are skipped.