Team project: C or C++ Explainer-like rating program

Programs which generate, solve, and analyze Sudoku puzzles

Re: Team project: C or C++ Explainer-like rating program

Postby ronk » Sun Dec 26, 2010 1:30 pm

champagne wrote:
ronk wrote:That "filter" may be rather subtle. For example, I think at least one of the weak links must be in a mini-row or mini-column, which is not the case for your loops.

The filter is quite simple. The loop has "0 solution". This is seen thru a "parity check" in the process.

So Sudoku Explainer uses a "parity check?"

lksudoku wrote:I know the exact logic of that "filter", the question is whether this filter a bug and therefore a new SE version is required that does not have this filter, or, the SE clone needs to use the same filter

Does this mean you agree with champagne as to the existence of a "parity check?"

Moreover, why do you think this might be a bug? I see nothing to support that POV.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Team project: C or C++ Explainer-like rating program

Postby lksudoku » Sun Dec 26, 2010 1:36 pm

ronk wrote:
lksudoku wrote:I know the exact logic of that "filter", the question is whether this filter a bug and therefore a new SE version is required that does not have this filter, or, the SE clone needs to use the same filter

Does this mean you agree with champagne as to the existence of a "parity check?"

I found this "parity check" in the code
ronk wrote:Moreover, why do you think this might be a bug? I see nothing to support that POV.

I think this is a bug because even though the UL has no solution (as opposed to UL with multiple solutions) it is still a deadly pattern, and this pattern cannot exist in a valid puzzle, just like the multiple solutions UL, and therefore all the eliminations derived from a multiple solutions UL can be derived from a no solution UL
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Team project: C or C++ Explainer-like rating program

Postby champagne » Sun Dec 26, 2010 2:03 pm

lksudoku wrote:
ronk wrote:That "filter" may be rather subtle. For example, I think at least one of the weak links must be in a mini-row or mini-column, which is not the case for your loops.

I know the exact logic of that "filter", the question is whether this filter is a bug and therefore a new SE version is required that does not have this filter, or, the SE clone needs to use the same filter


let me tell it in another way.

The same logic applies whether the UL has "0" or "multiple" solutions. Why loops with "0" solutions are excluded (if all of them are excluded) is a kind of mystery.

We have anyway to accept I guess some changes in the new version (I have much more puzzles not matching if I take the original SE version and not ffixed8 in batch mode). That one is somehow anecdotal.

I keep my code as it is for the time being

champagne
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Team project: C or C++ Explainer-like rating program

Postby ronk » Sun Dec 26, 2010 2:40 pm

champagne wrote:The same logic applies whether the UL has "0" or "multiple" solutions. Why loops with "0" solutions are excluded (if all of them are excluded) is a kind of mystery.

No mystery. The existence of a one-to-one correspondence between unavoidable sets (in the puzzle setter's world) and uniqueness patterns (in the puzzle solver's world) is both reasonable and elegant.

I floated a similar trial balloon here for a BUG-Lite with zero solutions. RW and Steve R here didn't think much of the idea ... and I agree. I now think it would be much better for uniqueness patterns with no-solution to be referred to, e.g., as pseudo-ULs and pseudo-BUG-Lites.

Besides, a clone should clone, not redefine existing patterns.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Team project: C or C++ Explainer-like rating program

Postby champagne » Sun Dec 26, 2010 2:54 pm

ronk wrote:Besides, a clone should clone, not redefine existing patterns.


I already "un cloned" the crazy "K" rule (lksudoku found a bug in my attempt to duplicate it) , and I don't try to copy found bugs in SE, but may be somebody will be better than me in the "pure cloning". As far as I can see, Paul gave up as well in an attempt to build a pure clone.

champagne
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Team project: C or C++ Explainer-like rating program

Postby daj95376 » Sun Dec 26, 2010 6:21 pm

champagne wrote:
Code: Select all
 
..8.6..4.
34...5.2.
..2...9.5
.3..2....
1..3.8..7
....5..1.
4.3...6..
.8.6...54
.9..8.1..  locked here
 
A  B  C  |D  E   F   |G  H  I 
79 5  8  |2  6   379 |37 4  1 
3  4  79 |1  79  5   |8  2  6 
6  1  2  |8  37  4   |9  37 5 
------------------------------
79 3  4  |79 2   1   |5  6  8 
1  6  5  |3  4   8   |2  9  7 
8  2  79 |79 5   6   |4  1  3 
------------------------------
4  7  3  |5  1   2   |6  8  9 
2  8  1  |6  379 379 |37 5  4 
5  9  6  |4  8   37  |1  37 2 


Where my “clone” process that loop

r1c7 r8c7 r8c5 r3c5 r3c8 r9c8 r9c6 r1c6 r1c7

It's interesting that your loop contains the <37> remote pair w/o resolving it first. I suppose that's because SE doesn't resolve the remote pair first, either.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Team project: C or C++ Explainer-like rating program

Postby champagne » Sun Dec 26, 2010 7:15 pm

daj95376 wrote:It's interesting that your loop contains the <37> remote pair w/o resolving it first. I suppose that's because SE doesn't resolve the remote pair first, either.


No surprise, although I am not 100% sure that you have such a chain in any case.
lksudoku could give a better definition of the "parity check" process, but it's likely not so far from "colouring such chains".

The chain would be rated 6.7 against 4.7 for the loop. This is another reason to keep that loop in the UL logic.

champagne
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Team project: C or C++ Explainer-like rating program

Postby ronk » Sun Dec 26, 2010 8:01 pm

champagne wrote:The chain would be rated 6.7 against 4.7 for the loop. This is another reason to keep that loop in the UL logic.

As you well know, that loop is not in Explainer's UL logic. Moreover, PIsaacson [edit: code, as improved by lksudoku,] was apparently able to clone Explainer's UL and BUG techniques without exception.
Last edited by ronk on Sun Dec 26, 2010 11:02 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Team project: C or C++ Explainer-like rating program

Postby lksudoku » Sun Dec 26, 2010 8:43 pm

[EDIT]This post referred to a statement that no longer exists
Last edited by lksudoku on Sun Dec 26, 2010 11:52 pm, edited 4 times in total.
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Team project: C or C++ Explainer-like rating program

Postby PIsaacson » Sun Dec 26, 2010 8:45 pm

SE included a UR loop validation check which in C++ looks like:

Code: Select all
bool ur_loop_valid (int level)
{
   bool found = true;

   int sects[2] = {0, 0};

   for (int n = 0; n <= level; n++)
   {
      int nx = ur_loop_stack[n].ur_key.lh_index;
      int rx = nx / 9;
      int cx = nx % 9;
      int bx = rc2b[rx][cx];

      int lx = n & 1;

      int mask = (1 << rx) | (1 << (cx + 9)) | (1 << (bx + 18));

      if (sects[lx] & mask)
         return (false);

      sects[lx] |= mask;
   }

   return (sects[0] == sects[1]);
}

Sorry for the lack of comments, but basically it retraces the loop and computes the row/col/box for each cell of the loop and accumulates these values separately for the even/odd links in the chain. Using Champagne's first UR loop:

Code: Select all
r1c7 r8c7 r8c5 r3c5 f3c8 f9c8 f9c6 r1c6

r1c7   1/7/3    r8c7  8/7/9
r8c5   8/5/8    r3c5  3/5/2
r3c8   3/8/3    r9c8  9/8/9
r9c6   9/6/8    r1c6  1/6/2

Since the boxes used on the even (left) side do not match the boxes on the odd (right) side, the ur_valid (sects[0] == sects[1]) test will fail. The other way to fail is if the sectors are re-used/traversed, which is checked by the if (sects[lx] & mask) test.

I'm guessing that this is the "parity check" or "filter" that everyone is referencing. I was trying to mimic SE exactly when I wrote the UR loop code, so I think I stuck it in without attempting to determine it's fundamental correctness or "goodness" factor.

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: Team project: C or C++ Explainer-like rating program

Postby daj95376 » Sun Dec 26, 2010 10:35 pm

PIsaacson wrote:SE included a UR loop validation check which in C++ looks like:

Code: Select all
      if (sects[lx] & mask)
         return (false);

Code: Select all
r1c7 r8c7 r8c5 r3c5 r3c8 r9c8 r9c6 r1c6

r1c7   1/7/3    r8c7  8/7/9
r8c5   8/5/8    r3c5  3/5/2
r3c8   3/8/3    r9c8  9/8/9
r9c6   9/6/8    r1c6  1/6/2


It seems to me that SE's "parity check" fails once champagne's chain reached cell r3c8 and [b3] is reused. However, since r8c5 contains the only non-37 candidate(s) in the chain/loop through r3c8, we can deduce r8c5<>37. Right?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Team project: C or C++ Explainer-like rating program

Postby PIsaacson » Mon Dec 27, 2010 1:55 am

Code: Select all
 *--------------------------------------------------*
 | 79   5    8    | 2    6   h379  |a37   4    1    |
 | 3    4    79   | 1    79   5    | 8    2    6    |
 | 6    1    2    | 8   d37   4    | 9   e37   5    |
 |----------------+----------------+----------------|
 | 79   3    4    | 79   2    1    | 5    6    8    |
 | 1    6    5    | 3    4    8    | 2    9    7    |
 | 8    2    79   | 79   5    6    | 4    1    3    |
 |----------------+----------------+----------------|
 | 4    7    3    | 5    1    2    | 6    8    9    |
 | 2    8    1    | 6   c379  379  |b37   5    4    |
 | 5    9    6    | 4    8   g37   | 1   f37   2    |
 *--------------------------------------------------*

Danny,

I've inserted the PM and both (c) r8c5 and (h) r1c6 contain <379>. So, I'm assuming it's some sort of UR loop type 2 and either r1c6 is a 9 or r8c5 is which eliminates candidate 9 from the peers of r1c6 and r8c5: r2c5 <> 9 and r8c6 <> 9. Is there an alternative pattern interpretation of these cells that leads to your immediate r8c5 <> 37???

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: Team project: C or C++ Explainer-like rating program

Postby daj95376 » Mon Dec 27, 2010 3:38 am

Code: Select all
 *--------------------------------------------------*
 | 79   5    8    | 2    6   h379  |a37   4    1    |
 | 3    4    79   | 1    79   5    | 8    2    6    |
 | 6    1    2    | 8   d37   4    | 9   e37   5    |
 |----------------+----------------+----------------|
 | 79   3    4    | 79   2    1    | 5    6    8    |
 | 1    6    5    | 3    4    8    | 2    9    7    |
 | 8    2    79   | 79   5    6    | 4    1    3    |
 |----------------+----------------+----------------|
 | 4    7    3    | 5    1    2    | 6    8    9    |
 | 2    8    1    | 6   c379  379  |b37   5    4    |
 | 5    9    6    | 4    8   g37   | 1   f37   2    |
 *--------------------------------------------------*

d-e-a-b is a Remote Pair in a 2-String Kite pattern => c:r8c5<>37=9
d-e-f-g is a Remote Pair in a Skyscraper    pattern => ch:r8c5,r1c6<>37=9

Adding "c" to the first chain or "c"|"h" to the second chain creates a chain that fails the SE test but allows a conclusion to be reached because only the added cell would contain non-37 candidates. IOW, SE has the potential to detect (some) Remote Pairs in the UR loop logic when an odd-numbered cell is added to the chain ... but it doesn't.

[Edit: reworded based on ronk's comments below.]
Last edited by daj95376 on Mon Dec 27, 2010 5:47 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Team project: C or C++ Explainer-like rating program

Postby ronk » Mon Dec 27, 2010 5:24 am

daj95376 wrote:SE has the potential to detect (some) Remote Pairs in the UR loop logic, but I'm under the impression that it doesn't. Right/Wrong?

UL loop logic is a continuous loop of even length and remote pairs is a discontinuous loop of odd length, so I'm unsure what you mean by "Remote Pairs in the UR loop logic." In any case, remote pairs is not in the Sudoku Explainer Technique Set ("SETS"). Remote pairs with four cells would be detected as turbot fish with (I think) difficulty rating 6.6.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Team project: C or C++ Explainer-like rating program

Postby daj95376 » Mon Dec 27, 2010 6:05 am

ronk wrote:UL loop logic is a continuous loop of even length ...

Okay, it's possible/probable that pairs of cells are added to the UL loop instead of adding individual cells and performing a parity check after each cell is added. Too bad because the routine listed by Paul doesn't care if "n" is even or odd when it detects a failure! BTW: it is interesting that "level" has to be odd for the loop to check an even number of cells.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

PreviousNext

Return to Software