The New Sudoku Players' Forum

[Leren]

Thanks RSJ,

What I think you are saying is that you could get nine different symbols in a house, but if one of them was different from what is in your list, the house might look OK by itself but you wouldn't get 111111111.

So your choice of symbols is a nice way of canonicalising them such that if a 10th symbol was in a checked house, you'd know about it. Looking good for my assertion so far.

I guess the next possible problem might be that a 10th symbol might appear in one of the 6 houses not checked. I'd have to go through the 21 house proof to see whether or not that can't happen.

I think I'll wait and see what some of the other smart guys say first.

Leren

[RSW]

Expressing it in a different way, if there are only nine positions available in a house and all of them are occupied, but there is an invalid pattern, then it means that one or more symbols are duplicates and therefore one or more symbols must be missing. The inclusive OR operation won't detect duplicates directly, but it will detect the missing symbols, because the bit position corresponding to the missing symbol will be zero in the final result. So an invalid pattern will always be detected.

I use bit patterns extensively in my solver program for locating various patterns. In fact, I'm currently updating my X-wing routine to generalize it into solving swordfish and jellyfish, and using bit patterns to simplify the detection of them.

[Leren]

Thanks RSW.

I'm quite happy that your method will confirm nine different symbols in a house that has been checked. But the other part of the minimisation assertion says that 6 houses don't have to be checked at all (after JPF).

So, if 21 houses have been checked, and all found to contain 9 different symbols from the same set of 9, is it impossible for any other of the 6 unchecked houses to contain either a duplicate symbol from the nine, or a 10th symbol.

I'd have to read carefully through the 21 house proof referred to in JPF's post but I'm being a bit lazy and waiting for someone else to confirm or deny it.

Leren

[RSW]

Okay, I see what you're saying.

It makes sense that the check on a certain number of houses could be skipped, but whether or not it's six, I can't think of any easy proof off the top of my head.

[Leren]

I just checked the 21 house proof in the link provided by JPF and it appears to use the digits 1 - 9, so I think the proof depends on you being given a set of 9 symbols to pick from, which I suppose would be normal for most electronic solvers.

But Hodoku offers a variant called Colorku, where the digits are replaced by small coloured circles. A solved cell is indicated by a large circle of the right colour.

Now suppose you printed out the grid and used coloured pencils to solve the puzzle, and you accidentally used the wrong shade of a colour in the solution, ie a 10th symbol.

Would someone picky like me say your solution was wrong ? Well, maybe, but maybe that's being unreasonable.

So, if you are given a set of 9 symbols that you must use, and use RSW's checking system, and JPF's 21 house proof has not been improved on, then the 189 inclusive OR operations thing seems to be holding up.

So far !

Leren

[StrmCkr]

a bit late for me to chime in but i shall anyway

considering Mini Row & Mini Cols as restraint subsets with in a row

you'd need 2 checks per row and can skip the entire third row/col. per band/stack

now the interesting part is you can completely ignore the entirety of the 3 stack

Code: Select all

 Bands
ABC | DEF | ...    <- first 2 mini row sectors prove the 3rd is true
DEF | ABC | ...   <- first 2 mini row sectors prove the 3rd is true
... | ... | ...     <- thus the  3rd row is also in full


Code: Select all

Stacks
---------------------------
AD. | ... | ...   <- first 2 mini Col sectors prove the 3rd is true
BE. | ... | ... <- first 2 mini Col sectors prove the 3rd is true
CF. | ... | ...  <- thus the  3rd Col is also in full
---------------------------
DA. | ... | ...
EB. | ... | ...
FC. | ... | ...
---------------------------
... | ... | ...
... | ... | ...
... | ... | ...

the fun part

Mini Row of box 1 + Mini Row of Box 1 also proves 3rd mini row of box 1 is true
+
mini Col of box 1 + Mini Col of box 1 also proves 3rd Col of box 1 is true.

in other words the unmarked cell can only be 1 digit for the box when no digits are copied/duplicated.
--------
which is equal to 45 - [ mini Row + Mini row ] + [ mini Col + Mini Col ] - [ ( Mini row * Min Col )+ (mini Row * Mini Col) ] = last number missing. ie set of [ 1-> 9 digit only]

--------------------------------------------------------------------

which means the only Real boxes we have to check are Boxes 3,6,7,8,9
once boxes 3,6,7,8 are confirmed the only valid positing of the digits can be only arranged one way in box 9

[6 {Rows} + 6{Cols} + 5{Boxes} * 9 {digits } ] + 81{Cells} = 270 pseudo constraints.

once boxes 3,6,7,8 are confirmed the only valid positing of the digits can be only arranged one way in box 9

[6 {Rows} + 6{Cols} + 4{Boxes} * 9 {digits } ] + 81{Cells} = 225 pseudo constraints.

Code: Select all

+--------------+--------------+-----------+
| 12   12   1  | 12   12   1  | 23  23  3 |
| 12   12   1  | 12   12   1  | 23  23  3 |
| 2    2    .  | 2    2    .  | 23  23  3 |
+--------------+--------------+-----------+
| 12   12   1  | 12   12   1  | 23  23  3 |
| 12   12   1  | 12   12   1  | 23  23  3 |
| 2    2    .  | 2    2    .  | 23  23  3 |
+--------------+--------------+-----------+
| 123  123  13 | 123  123  13 | 2   2   . |
| 123  123  13 | 123  123  13 | 2   2   . |
| 23   23   3  | 23   23   .  | .   .   . |
+--------------+--------------+-----------+
1 = Row
2= Col
3= box


--------------------------------------------- tricks for mini row summations: ---------------------------------------------------------------------

Code: Select all

 {shortened list}
 3 # used       sum total
9   8   7      24
9   8   6      23
9   8   5      22
9   8   4      21
9   8   3      20
9   8   2      19
9   8   1      18
8   7   6      21
8   7   5      20
8   7   4      19
8   7   3      18
8   7   2      17
8   7   1      16
7   6   5      18
7   6   4      17
7   6   3      16
7   6   2      15
7   6   1      14
6   5   4      15
6   5   3      14
6   5   2      13
6   5   1      12
5   4   3      12
5   4   2      11
5   4   1      10
4   3   2      9
4   3   1      8
3   2   1      6

first rule:
2 mini sectors are using Set-wise Multiplication to prove they do not carry identical numbers,

2nd Rule : that a mini sector must be valid set's sum total can only be found on this list else they are invalid.

rule 3: 45 - ( A + B) = C : were C must also fall in the chart above.

notes: some numbers summations total over lap however every single one of those that do involves 1 over lapping digit with the exception of "12" { thus rule 1 invalidates a lot of errors, rule 2 insures sum totals can only fall on the chart with out overlapping digits. and rule three insures all three are the sum of 45.

with some cleaver code you can check 2 rows, 2 cols and 2 box at the same time.

to cover all the rows/cols/box you'd need ~
3 checks each with 3 math checks per min part. => 3 * (6*2*3) = 108 checks.... {when physically looking at the operations needed}

but it is done in 3 steps for the whole grid and all digits.

the list of 3 digits and their sum can be further reduced if you'd like:
to a list of 3 sets of 3 digits that properly form a sum of 45 with out overlapping digits.

which is:

84 choices for the first spot,
20 for the 2nd
1 for the third.

Additional notes
2 rows 4 mini rows OF 2 BOXES cannot contain any identical missing digits else THE THIRD box has duplicate numbers

Code: Select all

Row 1 min row (a+ b) - [1..9]
*
row 2 mini row (a+b) - [1..9]

= [empty]

Code: Select all

123 | 786 | .9.
456 | 123  |.9.
... | ... | ...   <-  box 3 must have the digit  9 placed twice

And the opposite side of that:

They cannot share more then 3 digits else 3 cells contain more then 3 placements ie Row 3 mini row C = more then 3 digits.

Code: Select all

Row 1 min row (a+ b) - [1..9]
*
row 2 mini row (a+b) - [1..9]

<=[3 digits shared]

Code: Select all

123 | 786 | ...
456 | 123  |...
... | ... | 1236   <- must equal 4 digits

the box mini rows of two intersecting rows cannot share missing digits else the box row 3 = duplicates

Row 1 mini Row a + Row 2 mini row A - [1..9]

*
Row 1 mini Row b + Row 2 mini row B - [ 1..9]

= [ empty]

Code: Select all

123 | 678 | ...
456 | 123  |...
.9. | .9. | ...   <- must equal 9 digit twice

[Leren]

StrmCkr wrote : a bit late for me to chime in but i shall anyway

It's never too late to have fun. You might like to compare your method with the one JPF refered to here. They use 4 boxes, all but one row/column and all cells in those 21 houses.

Leren

[StrmCkr]

the flip side of this question is also interesting to pursue for grid generation as a quick validation checking.

if a row/col/box is missing N cells then it must have N digits listed as pencil-marks

this notion catches 2 types of errors
1) digits eliminated by box line reduction { less digits then cells needed to fill}
2) more digits unsolved then cells needed to fill { duplicated numbers in a space}

- a point to note:
a completed row/col/box cannot have digits not solved which is the 2nd error

which is more inline to what my error check/validation check performs
{ i can update this so it actually only searches the 21 minimal checks instead of all 27 }
a point to note is using set-wise data space I can do all 9 digits at once.

by my code below
4 steps and 27 sectors each verification step with 1 set-wise operations {after updating the code with noted improvements}
= 108 checks

when using 21 sectors this = 4 * 21 = 84

if i am correct from previous post you can also reduce the count from 6+6+9 = 21 down to (6+6+4) = 16
when using 16 sectors this = 4 * 16 = 64 total checks as a max

other notes on the code below:
free pascal lacks a Card(set) function compared to turbo-pascal so i have to use an improvise counting methods to compare

need to update this code to reflect some changes by using better data spaces
- a list of unsolved Digits of a sector
- a list of solved digits for a sector
- a count of unsolved cells for a sector

My error check: Show

Code: Select all

{CHECKS THE GRID FOR INVALID STATES}
procedure errorcheck;
var
XN,N,YN,count,s,f:INTEGER;
count2:RCBnums;
Begin
UNIQUE:= TRUE;

  {redundant checks as they are found below}
{FOR XN:= 0 TO 80 Do
 BEGIN

 //no cell and pm can be empty
 IF (s[XN] = [])  AND (nm[XN] =0 )
  THEN
    UNiQUE:= FALSE;

 //no peer cell of xn, can have the same solved digit
 FOR N IN S[XN] Do
 FOR YN IN PEER[XN] DO
   IF N IN S[YN]
     THEN
       UNIQUE:= FALSE;
END;  }

For xn:= 0 to 26 do
begin

if (nsector[xn] <>  [1..9]-ssector[xn] )  { and (nsector[xn] <> [])} {shows mutiple digits pms are missing in full}
 then
  unique:=false;

if (Nsector[xn] <> []) and (nsector[xn] = [1..9] - ssector[xn]) then
 begin
 Count:= 0;
 count2:=[];

{no sector can have less digits then unsolved cells
no sector can have more digits then unsolved cells}
   for n in Nsector[xn] do
     begin
      inc(count);
      count2:= Rnsector[xn,n] + count2;
      end;
     if popcnt(dword((count2))) <> count
      then
      unique:= false;

 if (count > 2)  then
case (count) of
3: begin s:=9; F:= 128; end;
4: begin s:=9; F:= 254; end;
5: begin s:=9; F:= 380; end;
6: begin s:=9; F:= 464; end;
7: begin s:=9; F:= 500; end;
8: begin s:=9; F:= 509; end;
9: begin s:=9; F:= 510; end;
end; {case count}

     { no subset can have less cells then the subset digit count}
if  (count > 2)   then
for yn:= s to f do
  if comboset[yn] * Nsector[xn] = comboset[yn]
    then
    begin
     Count:= 0;
      count2:=[];

   for n in Nsector[xn] * comboset[yn] do
     begin
      inc(count);
      count2:= Rnsector[xn,n] + count2;
      end;
     if popcnt(dword((count2))) < count
      then
        unique:= false;
    end;
 end;

end;

END;

--- basically the same idea as RWS - instead im using set-wise representation of bit-sets.
{ multiplication functions vs addition thus mine will run inherently slower comparatively due to cpu order of operations}

[eleven]

I just checked the 21 house proof in the link provided by JPF and it appears to use the digits 1 - 9, so I think the proof depends on you being given a set of 9 symbols to pick from, which I suppose would be normal for most electronic solvers.

Don't understand your doubts.
If you have a grid with 81 different symbols, it would pass each check for 9 different symbols in all houses.
So if you make 2 checks, you have to verify in any case, that you found the same symbols there.
In the proof all columns are checked. So you must have exactly 9 symbols in the grid.

[Leren]

Hi eleven. I haven't had much time to think about this topic for a few days, but JPF's link definitely assumes only 9 symbols are allowed. They say, inter alia :

... Suppose the columns c1,c2,c3 and the subsquares s1,s4 are correct (i.e. contain exactly the numbers 1 to 9). Then it's easy to see that s7 is correct as well. ...

So, they assume only 9 symbols (digits 1 - 9) are allowed. I haven't looked through StrmCkr's posts to see what he does yet.

RSW also assumes nine symbols eg he has a bit set 001000000 for the "third" symbol, but thinking a little about it, when he inclusive OR's the bit patterns, the meaning of the "three" bitset is that it's not only "three", but it's not any of the other symbols as well. That sounds like 9 implicit checks for each bit pattern, so I don't think you can compare my numbers with those obtained in the original problem, which used strictly elementary xi≠yi checks.

Leren

[StrmCkr]

Jps and rws

6 rows (solving 2 per band solves the third in a band)
6 cols (solving 2 per stack solves the third in a stack)
9 boxes

With a mask that sums all 9 digits
21 checks with 9 + operations each. =189 operations to verify a grid.

[Leren]

StrmCkr wrote : With a mask that sums all 9 digits 21 checks with 9 + operations each. =189 operations to verify a grid.

That's the same number I came up with. The question I have is how do we compare this result with that of the original problem? As far as I can see these 189 "operations" aren't "elementary" in the sense of the original problem. So, in terms of "elementary" operations maybe they should be multiplied by 9. Now that gives a larger number than the original problem, but in that case the space of grid errors was smaller, because the sum of the houses was to be kept at 45, so the number of errors in each faulty house had to be more than one (I think it's got to be even).

Leren

[RSW]

At the beginning of the discussion the operation was simply addition. Adding up the digits of a house requires 8 additions. From a human point of view, addition may be simpler to comprehend than inclusive OR, but for even the most basic computer processor, the inclusive OR operation is just as simple, if not simpler. Every CPU has an inclusive OR function as part of its hardware instruction set. Inclusive ORing all the symbols of a house requires 8 inclusive OR operations—the same as the number of additions in the addition test.

[StrmCkr]

At the beginning of the discussion the operation was simply addition. Adding up the digits of a house requires 8 additions. From a human point of view, addition may be simpler to comprehend than inclusive OR, but for even the most basic computer processor, the inclusive OR operation is just as simple, if not simpler. Every CPU has an inclusive OR function as part of its hardware instruction set. Inclusive ORing all the symbols of a house requires 8 inclusive OR operations—the same as the number of additions in the addition test.

21 steps that must be true else the test case is false each of the 21 with a "sum" of 9 spaces that must also be true else everything is false.

Hidden Text: Show

Code: Select all

row 1  OR(1,2,3,4,5,6,7,8,9)
  or
Row 2 or (1,2,3,4,5,6,7,8,9) 
 or
row 3  OR(1,2,3,4,5,6,7,8,9)
or
row 4  OR(1,2,3,4,5,6,7,8,9)
 or
row 5 OR(1,2,3,4,5,6,7,8,9)
 or
row 6 OR(1,2,3,4,5,6,7,8,9)
or
Col 1  OR(1,2,3,4,5,6,7,8,9)
  or
Col 2 or (1,2,3,4,5,6,7,8,9) 
 or
Col 3  OR(1,2,3,4,5,6,7,8,9)
or
Col 4  OR(1,2,3,4,5,6,7,8,9)
 or
col 5 OR(1,2,3,4,5,6,7,8,9)
 or
 col 6 OR(1,2,3,4,5,6,7,8,9)
or
box 1  OR(1,2,3,4,5,6,7,8,9)
  or
box 2 or (1,2,3,4,5,6,7,8,9) 
 or
box 3  OR(1,2,3,4,5,6,7,8,9)
or
box 4  OR(1,2,3,4,5,6,7,8,9)
 or
box 5 OR(1,2,3,4,5,6,7,8,9)
 or
box 6 OR(1,2,3,4,5,6,7,8,9)
or
box 7 OR(1,2,3,4,5,6,7,8,9)
 or
box 8 OR(1,2,3,4,5,6,7,8,9)
 or
box 9 OR(1,2,3,4,5,6,7,8,9)

in computer code that's 21 checks each with 1 "check"
if it read what you said corret.

i use set-wise data sets
similar logic except slightly different notation

Hidden Text: Show

+ Union of two sets
- Difference of two sets
* Intersection of two sets
= Checks equality of two sets
<> Checks non-equality of two sets
in Checks set membership of an element in a set
".. " operator precedence

more then bitsets

Hidden Text: Show

Code: Select all

Operator    Usage    Description
Bitwise AND    a & b    Returns a 1 in each bit position for which the corresponding bits of both operands are 1s.
Bitwise OR    a | b    Returns a 1 in each bit position for which the corresponding bits of either or both operands are 1s.
Bitwise XOR    a ^ b    Returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1s.
Bitwise NOT    ~ a    Inverts the bits of its operand.
Left shift    a << b    Shifts a in binary representation b (< 32) bits to the left, shifting in 0s from the right.
Sign-propagating right shift    a >> b    Shifts a in binary representation b (< 32) bits to the right, discarding bits shifted off.
Zero-fill right shift    a >>> b      Shifts a in binary representation b (< 32) bits to the right, discarding bits shifted off, and shifting in 0s from the left.

thus for this to show up

Code: Select all

 111 111 111

each "1" represent that for each of the "27" sectors the digit is true, and each "1" representing the digits [1-9 ]

[Leren]

Just doing a bit of elementary probability theory shows that picking a correct set of 9 characters 123456789 in any order from all the possible outcomes is 9^9 / 9! which is about 1067 = 2^10 approximately.

So the single "check" outcome 111 111 111 effectively contains about 10 bits of information. Other outcomes, such as 101 111 111 contain slightly less information, because they show that 2 is not in the set but don't distinguish between which of the other 8 digits is in the set twice. 000 000 000 is impossible because you are supposed to pick some digits. I suspect that when you look at all the possible "check" outcomes and average out their effective bit content, you will arrive at a figure of 9 bits per single "check".

Working out the effective bit content of an elementary check of type xi≠yi given that the sum of the digits in a house must balance to 45 is tricky - I would have to figure out exactly how many ways you can get any assortment of 9 digits 1 - 9 to sum to 45 and it's a bit late at night to do that. Nevertheless, I'm pretty sure it must be less than 1067 which would make the bit content of this type of elementary check much less than 10.

Leren