Minimum number of checks

Everything about Sudoku that doesn't fit in one of the other sections

Re: Minimum number of checks

Postby Serg » Sun Jul 14, 2019 9:07 am

deleted
Last edited by Serg on Sat Jul 20, 2019 8:35 pm, edited 1 time in total.
Serg
2018 Supporter
 
Posts: 651
Joined: 01 June 2010
Location: Russia

Re: Minimum number of checks

Postby StrmCkr » Sun Jul 14, 2019 11:38 am

deleted
Last edited by StrmCkr on Mon Jul 15, 2019 11:04 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 979
Joined: 05 September 2006

Re: Minimum number of checks

Postby Serg » Sun Jul 14, 2019 1:21 pm

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
Serg
2018 Supporter
 
Posts: 651
Joined: 01 June 2010
Location: Russia

Re: Minimum number of checks (504 -> 480)

Postby blue » Sun Jul 14, 2019 2:27 pm

Hi Serg,

Serg wrote:[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.
blue
 
Posts: 837
Joined: 11 March 2013

Re: Minimum number of checks

Postby eleven » Mon Jul 15, 2019 9:33 am

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
eleven
 
Posts: 2075
Joined: 10 February 2008

Re: Minimum number of checks

Postby Serg » Mon Jul 15, 2019 3:18 pm

Hi, eleven!
eleven wrote: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
Serg
2018 Supporter
 
Posts: 651
Joined: 01 June 2010
Location: Russia

Re: Minimum number of checks

Postby eleven » Mon Jul 15, 2019 7:44 pm

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.
eleven
 
Posts: 2075
Joined: 10 February 2008

Re: Minimum number of checks

Postby Serg » Mon Jul 15, 2019 9:19 pm

Hi, eleven!
eleven wrote: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
Serg
2018 Supporter
 
Posts: 651
Joined: 01 June 2010
Location: Russia

Re: Minimum number of checks

Postby eleven » Mon Jul 15, 2019 9:52 pm

Thanks, this worked for me.
eleven
 
Posts: 2075
Joined: 10 February 2008

Re: Minimum number of checks

Postby StrmCkr » Mon Jul 15, 2019 10:01 pm

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.
Last edited by StrmCkr on Tue Jul 16, 2019 9:10 am, edited 2 times in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 979
Joined: 05 September 2006

Re: Minimum number of checks

Postby blue » Tue Jul 16, 2019 2:56 am

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:
blue wrote: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
39-configurations.png (40.06 KiB) Viewed 98 times
blue
 
Posts: 837
Joined: 11 March 2013

Re: Minimum number of checks

Postby eleven » Tue Jul 16, 2019 5:00 pm

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
 
Posts: 2075
Joined: 10 February 2008

Re: Minimum number of checks

Postby eleven » Thu Jul 18, 2019 10:26 pm

blue wrote: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
Last edited by eleven on Sat Jul 20, 2019 10:55 pm, edited 1 time in total.
eleven
 
Posts: 2075
Joined: 10 February 2008

Re: Minimum number of checks

Postby blue » Fri Jul 19, 2019 6:45 pm

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
blue
 
Posts: 837
Joined: 11 March 2013

Re: Minimum number of checks

Postby eleven » Fri Jul 19, 2019 7:51 pm

Hi blue,

i couldn't really decipher your method either.
I would read, that boxes 3678 are checked, but they are skipped.
eleven
 
Posts: 2075
Joined: 10 February 2008

PreviousNext

Return to General