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 lksudoku » Wed Oct 20, 2010 12:06 am

PIsaacson wrote:Run the same puzzle in SE and step until you hit the 7.3 bi-directional cycle (xy-cycle loop). Count the number of links - it's 12!!! I found several shorter/simpler standard discontinuous nice-loops (xy-cycle chain) length 10 which keeps my score to 7.1. Now, I'll admit that I'm having problems with the chain length score adjustments, but the length of a chain is pretty easy to count. Just another example of the SE anomalies that I'm tracking down...

Well I already described a bug that SE tries the techniques in the same order and when a technique is found it stops searching for the next technique move, which causes errors if a later technique has lower rating (when the rating range overlaps)

I suppose that xy-cycle loop technique is an earlier technique than the xy-cycle chain and thus if there is a xy-cycle loop, no matter how long it is, it will always be suggested, even if there is a xy-cycle chain which is much simpler with lower rating
lksudoku
 
Posts: 90
Joined: 06 October 2010

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

Postby champagne » Wed Oct 20, 2010 6:26 am

JasonLion wrote:My personal interest is in optimization. Optimization doesn't normally respect the existing structure of the code. You run a profiler, find problem areas, and do whatever is needed to make that code faster; regardless of what section(s) of the code that involves. In many cases this ends up involving significant restructuring of the code.


Believe me, the code I have has nothing to do with the existing code in SE. This is part of the expected better performance.

Regarding the sequence in the program, to match SE results, you have no way out than checking step by step to extract moves having the same rating, starting with the lowest rating.

This does not give the same sequence as in SE, but each level of resistance appears in each solution.

That logic should resist in nearly all cases; the main reason is that SE has been proven to rate nearly all morphs in the same way (few exceptions).

A small problem could come out of order in which UR/UL are taken.

It seems however from here above discussions that it's not so easy to stick to SE handling of lenght in chains.

I am expecting high improvements in performance, but it is to early to give any ratio; May be when I'll reach ER 9;

And for sure, the code I'll produce will still has room for improvements.


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

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

Postby champagne » Fri Oct 22, 2010 8:55 am

One reason among others why it will be difficult to match at 100% SE results.
here is the puzzle

....2......74.69...8.....3.2.......1.3.9.5.4...8...6...5..1..9...2...4......9....

and both my "clone" and SE reach that position

Code: Select all
A     B    C     |D     E  F   |G   H   I   
14569 1469 14569 |38    2  38  |57  67  467 
3     2    7     |4     5  6   |9   1   8   
456   8    456   |1     7  9   |25  3   246 
--------------------------------------------
2     69   569   |678   4  78  |3   58  1   
167   3    16    |9     68 5   |278 4   27   
457   47   8     |2     3  1   |6   57  9   
--------------------------------------------
4678  5    346   |3678  1  2   |78  9   367 
19    19   2     |35678 68 378 |4   678 3567
678   67   36    |35678 9  4   |1   2   3567


both see the UR

r8c1 19
r8c2 19
r1c1 14569
r1c2 1469

the lowest rating here is , unless I missed something, the hidden locked set in row 1 or box1 (4.6 if I am right).

instead, SE produce a "UR type 3 with a naked quad" in row 1, rated 4.8

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

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

Postby PIsaacson » Fri Oct 22, 2010 10:07 am

Champagne,

Starting with the PM, my bsf (best so far) code finds a slightly lower scoring UR type 3 with a triple instead of a quad, but I don't see any hidden locked set either manually or with the code. If it was coded for it, there's a nice skyscraper with digit 8 in cols 5/7 - another example of a technique that should probably be included with a modern scorer (I've got it available, but don't know what it should score as...):
Code: Select all
000020000327456918080179030200040301030905040008231609050012090002000400000094120 puzzle 1 starting
 14569     1469      14569    |38        2         38       |57        67        467     
 3         2         7        |4         5         6        |9         1         8       
 456       8         456      |1         7         9        |25        3         246     
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 2         69        569      |678       4         78       |3         58        1       
 167       3         16       |9         68        5        |278       4         27       
 457       47        8        |2         3         1        |6         57        9       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 4678      5         346      |3678      1         2        |78        9         367     
 19        19        2        |35678     68        378      |4         678       3567     
 678       67        36       |35678     9         4        |1         2         3567     

  1)  4.7 r1c3 <> 4 unique rectangle type 3 1/9 r1c12 r8c12 + ls[3] r3c1 r3c3.<456>
  2)  4.7 r1c3 <> 5 unique rectangle type 3 1/9 r1c12 r8c12 + ls[3] r3c1 r3c3.<456>
  3)  4.7 r1c3 <> 6 unique rectangle type 3 1/9 r1c12 r8c12 + ls[3] r3c1 r3c3.<456>
  4)  4.2 r1c2 <> 9 xy-wing at r5c3.<16> 1) r1c3.<19> 2) r4c2.<69>
  5)  4.2 r4c3 <> 9 xy-wing at r5c3.<16> 1) r1c3.<19> 2) r4c2.<69>
  6)  1.2 r4c2 <= 9 hidden single in b4
  7)  1.2 r8c1 <= 9 hidden single in b7
  8)  1.2 r1c3 <= 9 hidden single in b1
  9)  1.2 r8c2 <= 1 hidden single in b7
 10)  1.2 r1c1 <= 1 hidden single in b1
 11)  1.2 r5c3 <= 1 hidden single in b4
 12)  1.5 r1c7 <= 5 hidden single in r1
 13)  2.0 r3c7 <= 2    direct hidden pair r57c7.<78>
 14)  2.0 r5c9 <= 2    direct hidden pair r57c7.<78>
 15)  4.2 r6c8 <> 7 xy-wing at r1c2.<46> 1) r1c8.<67> 2) r6c2.<47>
 16)  1.2 r5c7 <= 7 hidden single in b6
 17)  1.0 r7c7 <= 8 full house in c7
 18)  1.2 r4c8 <= 8 hidden single in b6
 19)  1.0 r6c8 <= 5 full house in b6
 20)  1.2 r4c3 <= 5 hidden single in b4
 21)  1.2 r3c1 <= 5 hidden single in b1
 22)  1.2 r5c1 <= 6 hidden single in b4
 23)  1.0 r5c5 <= 8 full house in r5
 24)  1.0 r8c5 <= 6 full house in c5
 25)  1.2 r4c4 <= 6 hidden single in b5
 26)  1.0 r4c6 <= 7 full house in r4
 27)  1.2 r9c1 <= 8 hidden single in b7
 28)  1.5 r1c8 <= 6 hidden single in c8
 29)  1.0 r8c8 <= 7 full house in c8
 30)  1.2 r3c3 <= 6 hidden single in b1
 31)  1.0 r1c2 <= 4 full house in b1
 32)  1.0 r3c9 <= 4 full house in r3
 33)  1.0 r1c9 <= 7 full house in b3
 34)  1.2 r6c1 <= 4 hidden single in b4
 35)  1.0 r7c1 <= 7 full house in c1
 36)  1.0 r6c2 <= 7 full house in b4
 37)  1.0 r9c2 <= 6 full house in c2
 38)  1.2 r7c3 <= 4 hidden single in b7
 39)  1.0 r9c3 <= 3 full house in c3
 40)  1.2 r9c4 <= 7 hidden single in b8
 41)  1.0 r9c9 <= 5 full house in r9
 42)  1.2 r8c4 <= 5 hidden single in b8
 43)  1.2 r8c6 <= 8 hidden single in b8
 44)  1.0 r1c6 <= 3 full house in c6
 45)  1.0 r1c4 <= 8 full house in r1
 46)  1.0 r7c4 <= 3 full house in c4
 47)  1.0 r7c9 <= 6 full house in r7
 48)  1.0 r8c9 <= 3 full house in r8
....2....327456918.8.179.3.2...4.3.1.3.9.5.4...82316.9.5..12.9...2...4......9412. 1 4.7 4.7 4.7 0.5239ms

With skyscraper enabled and arbitrarily set to score 2.9 (highly ranked singles technique) the new final output would look like:
Code: Select all
000020000327456918080179030200040301030905040008231609050012090002000400000094120 puzzle 1 starting
 14569     1469      14569    |38        2         38       |57        67        467     
 3         2         7        |4         5         6        |9         1         8       
 456       8         456      |1         7         9        |25        3         246     
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 2         69        569      |678       4         78       |3         58        1       
 167       3         16       |9         68        5        |278       4         27       
 457       47        8        |2         3         1        |6         57        9       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 4678      5         346      |3678      1         2        |78        9         367     
 19        19        2        |35678     68        378      |4         678       3567     
 678       67        36       |35678     9         4        |1         2         3567     

  1)  2.9 r7c4 <> 8 skyscraper in r58c5 and r57c7
  2)  2.9 r8c8 <> 8 skyscraper in r58c5 and r57c7
  3)  1.2 r7c7 <= 8 hidden single in b9
  4)  1.2 r4c8 <= 8 hidden single in b6
  5)  1.2 r9c1 <= 8 hidden single in b7
  6)  1.2 r5c5 <= 8 hidden single in b5
  7)  1.2 r6c8 <= 5 hidden single in b6
  8)  1.0 r8c5 <= 6 full house in c5
  9)  1.2 r4c3 <= 5 hidden single in b4
 10)  1.2 r4c2 <= 9 hidden single in b4
 11)  1.2 r4c4 <= 6 hidden single in b5
 12)  1.2 r4c6 <= 7 hidden single in b5
 13)  1.2 r8c1 <= 9 hidden single in b7
 14)  1.2 r1c3 <= 9 hidden single in b1
 15)  1.2 r8c2 <= 1 hidden single in b7
 16)  1.2 r1c1 <= 1 hidden single in b1
 17)  1.2 r3c1 <= 5 hidden single in b1
 18)  1.2 r1c7 <= 5 hidden single in b3
 19)  1.2 r5c3 <= 1 hidden single in b4
 20)  1.2 r5c1 <= 6 hidden single in b4
 21)  1.5 r5c7 <= 7 hidden single in c7
 22)  1.5 r1c8 <= 6 hidden single in c8
 23)  1.5 r8c8 <= 7 hidden single in c8
 24)  1.5 r1c9 <= 7 hidden single in c9
 25)  1.0 r5c9 <= 2 full house in r5
 26)  1.0 r3c7 <= 2 full house in c7
 27)  1.0 r3c9 <= 4 full house in b3
 28)  1.0 r3c3 <= 6 full house in r3
 29)  1.0 r1c2 <= 4 full house in b1
 30)  1.2 r6c1 <= 4 hidden single in b4
 31)  1.2 r6c2 <= 7 hidden single in b4
 32)  1.2 r7c3 <= 4 hidden single in b7
 33)  1.2 r9c2 <= 6 hidden single in b7
 34)  1.2 r7c1 <= 7 hidden single in b7
 35)  1.2 r9c4 <= 7 hidden single in b8
 36)  1.2 r7c9 <= 6 hidden single in b9
 37)  1.0 r9c3 <= 3 full house in c3
 38)  1.0 r7c4 <= 3 full house in r7
 39)  1.0 r9c9 <= 5 full house in r9
 40)  1.0 r8c9 <= 3 full house in c9
 41)  1.2 r1c6 <= 3 hidden single in b2
 42)  1.2 r1c4 <= 8 hidden single in b2
 43)  1.2 r8c4 <= 5 hidden single in b8
 44)  1.2 r8c6 <= 8 hidden single in b8
....2....327456918.8.179.3.2...4.3.1.3.9.5.4...82316.9.5..12.9...2...4......9412. 1 2.9 2.9 2.9 0.1616ms

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

re: Uniqueness

Postby Pat » Fri Oct 22, 2010 10:27 am

the result of the Uniqueness
can surely be viewed many ways

e.g.
  • r1c12 not both in {1,9} -- therefore r1c3 must join with one of them as "hidden" duo {1,9} in r1
  • r1c12 not both in {1,9} -- therefore one of them joins with r1c789 as "naked" quartet ={4,5,6,7} in r1 (Nicolas Juillerat)
  • r1c12 must contain a {4,5,6} -- therefore one of them joins with r3c13 as "naked" trio ={4,5,6} in b1 (PIsaacson)
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re: re: Uniqueness

Postby champagne » Fri Oct 22, 2010 10:58 am

Pat wrote:the result of the Uniqueness
can surely be viewed many ways

e.g.
  • r1c12 not both in {1,9} -- therefore r1c3 must join with one of them as "hidden" duo {1,9} in r1
  • r1c12 not both in {1,9} -- therefore one of them joins with r1c789 as "naked" quartet ={4,5,6,7} in r1 (Nicolas Juillerat)
  • r1c12 must contain a {4,5,6} -- therefore one of them joins with r3c13 as "naked" trio ={4,5,6} in b1 (PIsaacson)



I use that post to answer to both.

My point is that SE normally rates the hidden locked set defined, using uniqueness, thru the cells r1c123 for the common digits of the UR (1;9) 4.6.

(to Paul, in that conditions, cells r1c13 of the UR are seen as one cell)

This should come before the naked quad rated 4.8

Most often, when there is a hidden set, a nacked set can also be found as here.

The question is "why SE did not find the "hidden locked set"

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

Re: re: Uniqueness

Postby ronk » Fri Oct 22, 2010 11:26 am

champagne wrote:My point is that SE normally rates the hidden locked set defined, using uniqueness ...

Normally? I don't believe SE even looks for a hidden set with a UR.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: re: Uniqueness

Postby champagne » Fri Oct 22, 2010 11:53 am

ronk wrote:
champagne wrote:My point is that SE normally rates the hidden locked set defined, using uniqueness ...

Normally? I don't believe SE even looks for a hidden set with a UR.


I did not,

I added that code just to comply to SE specifications

champagne

edit : you can find int he "comment pages" the skeleton to describe that situation with the title

Unique{0} type 3 (with Hidden{7})
champagne
2017 Supporter
 
Posts: 7466
Joined: 02 August 2007
Location: France Brittany

Re: re: Uniqueness

Postby ronk » Fri Oct 22, 2010 12:51 pm

champagne wrote:you can find int he "comment pages" the skeleton to describe that situation with the title

Unique{0} type 3 (with Hidden{7})

I'm not aware of a Sudoku Explainer "specification" ... and do you have a link to those "comment pages?"
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: re: Uniqueness

Postby champagne » Fri Oct 22, 2010 1:21 pm

ronk wrote:
champagne wrote:you can find int he "comment pages" the skeleton to describe that situation with the title

Unique{0} type 3 (with Hidden{7})

I'm not aware of a Sudoku Explainer "specification" ... and do you have a link to those "comment pages?"


I have not seen specificatons as such, but mixing a brief analysis of the code, html documents used by the program and analysis of examples, i more or less succeded up to now in guessing them.

If you downloaded the sources, you will find the "comments skeletons" as HTML documents spread in the source files.

The page related to "hidden locked sets in UR / UL" is in that directory


SudokuExplainer-sources\Sudoku\diuf\sudoku\solver\rules\unique

I entered the code when I found an example where it was utilized.

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

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

Postby lksudoku » Fri Oct 22, 2010 9:15 pm

champagne wrote:My point is that SE normally rates the hidden locked set defined, using uniqueness, thru the cells r1c123 for the common digits of the UR (1;9) 4.6

There is no hidden locked set in this case according to SE code, SE defined a UR type 4 (locked set) as follows (according to source code):

There is a region containing both ceiling cells of the UR with extra potentials (in this case r1c1, r1c2 and region either r1 or b1), such that the region does not contain any other cell with one of the UR floor two digits (1,9 in this case)

r1 contains 1 in r1c3 and 9 in r1c3
b1 contains 1 in r1c3 and 9 in r1c3

Therefore there is no UR type 4

Your definition of UR hidden locked set is not implemented by SE

A UR type 3 is either a UR with hidden or naked set, but the cells involves only the potentials that do not exist in the floor, it searches for hidden/naked sets with the common ceiling digits beside the floor digits (in this case with the digits 4,5,6)

EDIT: There is a naked set of degree 7 (2345678), but SE does not search for degree higher than 4, the equivalent hidden set of degree 2 is never found since it requires digits of the floor
lksudoku
 
Posts: 90
Joined: 06 October 2010

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

Postby champagne » Sat Oct 23, 2010 6:49 am

lksudoku wrote:
champagne wrote:My point is that SE normally rates the hidden locked set defined, using uniqueness, thru the cells r1c123 for the common digits of the UR (1;9) 4.6

There is no hidden locked set in this case according to SE code, SE defined a UR type 4 (locked set) as follows (according to source code):

There is a region containing both ceiling cells of the UR with extra potentials (in this case r1c1, r1c2 and region either r1 or b1), such that the region does not contain any other cell with one of the UR floor two digits (1,9 in this case)

r1 contains 1 in r1c3 and 9 in r1c3
b1 contains 1 in r1c3 and 9 in r1c3

Therefore there is no UR type 4

Your definition of UR hidden locked set is not implemented by SE

A UR type 3 is either a UR with hidden or naked set, but the cells involves only the potentials that do not exist in the floor, it searches for hidden/naked sets with the common ceiling digits beside the floor digits (in this case with the digits 4,5,6)

EDIT: There is a naked set of degree 7 (2345678), but SE does not search for degree higher than 4, the equivalent hidden set of degree 2 is never found since it requires digits of the floor



this is an interessing view of somebody appearing as being the best existing expert to-day in SE.

Let me ask questions to sure to catch 100% your post and make comments.

1) I understand that what you call the "floor digits" are the common digits of the UR pattern.

2) I have never seen an hidden set done out of the "non common" digits of the UR so far

3) If I added some code for the "hidden locked set pattern" it is because iI have seen (or I believed I saw) that in one example.
In fact what I am doing is to run the pattern game results as sample file and look in the windows version of SE to explain any non matched results.

I'll simply de activate my code to check again and I'll come back with confirmation of your statement or a counter example.

4) I have to apologize for my first reaction to your "de bugged" verion of Sudoku Explainer.

In case this project would fail, it would be good, at the right moment to switch to such a version
Within the scope of the project, trying in parallel to build a faster version of SE and to debug the existing one ould help to match results.

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

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

Postby champagne » Sat Oct 23, 2010 7:52 am

here an example of a "sophisticated" hidden triplet rated 4.6
That one is seen by my "clone", but not properly rated.

..1...2..
...3.2...
4...1...3
.6.7.8.5.
..4...9..
.8.6.4.2.
9...6...7
...8.7...
..5...1..

Code: Select all
A     B    C    |D   E    F   |G   H    I   
3568  359  1    |4   78   569 |2   6789 5689
568   59   678  |3   78   2   |4   1    5689
4     259  2678 |59  1    569 |568 6789 3   
--------------------------------------------
1     6    29   |7   29   8   |3   5    4   
2357  2357 4    |125 235  135 |9   68   68   
35    8    39   |6   359  4   |7   2    1   
--------------------------------------------
9     234  238  |125 6    135 |58  348  7   
236   1    236  |8   2345 7   |56  3469 2569
23678 2347 5    |29  234  39  |1   3468 268 


UR

r5c8 68
r5c9 68
r9c9 268
r9c8 3468



in row 9 digits 678 are only

in the UR cells
in cells r9c12

this form a "hidden triplet"
SE clears 23 r9c1 and 234 r9c2

Here after the comment block (I hope without typing error)

Unique rectangle type 3 (with Hidden triplet)
The cells H5;I5;I9;H9 form a Unique rectangle with the values 6 and 8.
There are exactly two ways of placing the values 6 and 8 in the cells of the Unique rectangle, forming two possible configurations.
In both configurations, each row, column or block touched by the Unique rectangle contains each of the two values 6 and 8 exactly once.
As a result, if one of these two configurations were part of the solution, it could then be replaced by the other one to get a second valid solution.

Because a valid sudoku cannot have more than one solution, none of the two configurations of the Unique rectangle can be valid.
This implies that either I9 or H9 contains one of the values 2,3 or 4.
It follows that either I9 or H9 forms a Hidden triplet with A9 and B9 on the values 6,7 and 8 in the row.

Other potential values can therefore be removed from A9 and B9

====================================

As far as priorities are concerned, SE gives the priority to the naked pair against the hidden locked set.
I have to investigate more to understand other priorities


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

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

Postby ronk » Sat Oct 23, 2010 8:21 am

champagne wrote:Here after the comment block (I hope without typing error)

Unique rectangle type 3 (with Hidden triplet)
The cells H5;I5;I9;H9 form a Unique rectangle with the values 6 and 8.
There are exactly two ways of placing the values 6 and 8 in the cells of the Unique rectangle, forming two possible configurations.
In both configurations, each row, column or block touched by the Unique rectangle contains each of the two values 6 and 8 exactly once.
As a result, if one of these two configurations were part of the solution, it could then be replaced by the other one to get a second valid solution.

Because a valid sudoku cannot have more than one solution, none of the two configurations of the Unique rectangle can be valid.
This implies that either I9 or H9 contains one of the values 2,3 or 4.
It follows that either I9 or H9 forms a Hidden triplet with A9 and B9 on the values 6,7 and 8 in the row.

Other potential values can therefore be removed from A9 and B9

Rather than typing, cut & paste is possible. Also, menu bar "Options" has a selection for the "R1C1 - R9C9 cell notation" used on this forum.

Sudoku Explainer wrote:The cells R5C8,R5C9,R9C9,R9C8 form a Unique Rectangle with the values 6 and 8. There are exactly two ways of placing the values 6 and 8 in the cells of the Unique Rectangle, forming two possible configurations. In both configurations, each row, column or block touched by the Unique Rectangle contains each of the two values 6 and 8 exactly once. As a result, if one of these two configurations were part of the solution, it could then be replaced by the other one to get a second valid solution.
Because a valid sudoku cannot have more than one solution, none of the two configurations of the Unique Rectangle can be valid. This implies that either R9C9 or R9C8 contains one of the values 2, 3 or 4. It follows that either R9C9 or R9C8 forms a Hidden Triplet with R9C1 and R9C2 on the values 6, 7 and 8 in the row.
Other potential values can therefore be removed from R9C1 and R9C2.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

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

Postby champagne » Sat Oct 23, 2010 8:28 am

ronk wrote:Rather than typing, cut & paste is possible. Also, menu bar "Options" has a selection for the "R1C1 - R9C9 cell notation" used on this forum.



I did try "copy" (no cut) but it did not work.

One remark about my "clone solution.

In my clone solution, cell r9c2 does not play any role.
The hidden locked set is well defined with the cell r9c1 and the digits 6;8.

The fact that digt 7 is a bivalue comes later.

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

PreviousNext

Return to Software