Sudoku Explainer Fixes

Programs which generate, solve, and analyze Sudoku puzzles

Re: Sudoku Explainer Fixes

Postby daj95376 » Fri Jan 07, 2011 11:00 pm

Thanks L.K. for your latest version of serate.

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

I hope this is an acceptable place to post this comparison between SE 1.2.1.3 (first entry) and FIXED13 1.2.8.0 in batch mode (second entry).

There is a difference in the %p ratings in the first two examples.

What I find more interesting is the difference in %r ratings in the second and third examples.

Code: Select all
1....6..9..42..3...8..7..5.4......3...2...4...9......8.4..2..7...5..91..6..3....2 ED=9.4/9.4/9.2
1....6..9..42..3...8..7..5.4......3...2...4...9......8.4..2..7...5..91..6..3....2 ED=9.4/9.3/9.2

Code: Select all
1....6..9..63..2...7..8..3.3......2...9...8...4......5.9..3..7...5..41..6..2....4 ED=8.9/8.9/8.3
1....6..9..63..2...7..8..3.3......2...9...8...4......5.9..3..7...5..41..6..2....4 ED=8.8/8.8/8.3

Code: Select all
1....6..9..87..5...9..3..2.6......7...2...4...4......3.3..2..4...5..31..9..8....2 ED=8.4/7.1/7.1
1....6..9..87..5...9..3..2.6......7...2...4...4......3.3..2..4...5..31..9..8....2 ED=8.3/7.1/7.1

Regards, Danny
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer Fixes

Postby ronk » Fri Jan 07, 2011 11:19 pm

daj95376 wrote:What I find more interesting is the difference in %r ratings in the second and third examples.

Looks like a problem with serate. The v1.2.8.0 GUI agrees with your posted %r for v1.2.1.3.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sudoku Explainer Fixes

Postby daj95376 » Sat Jan 08, 2011 12:11 am

ronk wrote:
daj95376 wrote:What I find more interesting is the difference in %r ratings in the second and third examples.

Looks like a problem with serate. The v1.2.8.0 GUI agrees with your posted %r for v1.2.1.3.

I don't believe that lksudoku did anything to the GUI. For sure, I strongly doubt if it runs in batch mode.

That leaves: which version of serate has problems?

Both versions of serate encounter the lower valued ER rating first, but serate 1.2.1.3 selects a higher ER rating later. In batch mode, serate 1.2.8.0 doesn't encounter the higher ER rating later.

Regards, Danny
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer Fixes

Postby ronk » Sat Jan 08, 2011 12:44 am

daj95376 wrote:Both versions of serate encounter the lower valued ER rating first, but serate 1.2.1.3 selects a higher ER rating later. In batch mode, serate 1.2.8.0 doesn't encounter the higher ER rating later.

Aha, I didn't notice you were using the 'batch mode' for v1.2.8.0. Using non-batch mode (by definition) for the older version ... and batch mode mode for the newer opens the door to a number of possibilities. I don't wish to go there.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sudoku Explainer Fixes

Postby lksudoku » Sat Jan 08, 2011 10:32 am

daj95376 wrote:There is a difference in the %p ratings in the first two examples.

The reason for the difference in the %p rating is due to batch processing and the way SE finds dynamic forcing chains

If you run without batch mode the rating is the same

What happens in batch mode is that at a certain batch, SE finds several dynamic forcing chains based on the same puzzle state.
In step mode, SE finds the same moves due to forcing chains, but because it is not in batch mode, it finds them one after the other. When applying one of the batch moves before the next, the puzzle state changes

When SE finds dynamic forcing chains, it tries different paths; having a puzzle with less candidates (due to applying the step dynamic forcing chain) causes more possible chains moves to be searched while finding the chains; when searching using the new possible move, you get a longer chain

SE only searches for chains until there is contradiction thus finding the longer chain and never finding the shorter chain

In other words, step mode causes a different chain to be found for the same move because of more search options, and the first found chain is returned regardless of its length

daj95376 wrote:That leaves: which version of serate has problems?

The answer is that both versions have the same problem, however in batch mode, the lower rating chain will be found
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Sudoku Explainer Fixes

Postby daj95376 » Sat Jan 08, 2011 7:21 pm

lksudoku wrote:SE only searches for chains until there is contradiction thus finding the longer chain and never finding the shorter chain

Code: Select all
 8.8 Dynamic ( 9-12 nodes) CRCD Forcing Chains
 8.9 Dynamic (13-16 nodes) CRCD Forcing Chains
 9.0 Dynamic (17-24 nodes) CRCD Forcing Chains
 9.1 Dynamic (25-36 nodes) CRCD Forcing Chains
 9.2 Dynamic (37-48 nodes) CRCD Forcing Chains

If I follow LK's explanation, then the difference between an 8.8 rating and a 9.2 rating is simply the number of nodes in the first chain with a contradiction in a depth-first search of chains. This makes it possible for a puzzle and its row MinLex equivalent to have different ratings in the range 8.8-9.2. Hmmm! Too bad the number of nodes isn't a constraint in the DFS.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer Fixes

Postby lksudoku » Sat Jan 08, 2011 8:41 pm

daj95376 wrote:
lksudoku wrote:SE only searches for chains until there is contradiction thus finding the longer chain and never finding the shorter chain

Code: Select all
 8.8 Dynamic ( 9-12 nodes) CRCD Forcing Chains
 8.9 Dynamic (13-16 nodes) CRCD Forcing Chains
 9.0 Dynamic (17-24 nodes) CRCD Forcing Chains
 9.1 Dynamic (25-36 nodes) CRCD Forcing Chains
 9.2 Dynamic (37-48 nodes) CRCD Forcing Chains

If I follow LK's explanation, then the difference between an 8.8 rating and a 9.2 rating is simply the number of nodes in the first chain with a contradiction in a depth-first search of chains. This makes it possible for a puzzle and its row MinLex equivalent to have different ratings in the range 8.8-9.2. Hmmm! Too bad the number of nodes isn't a constraint in the DFS.

That is not entirely correct, but close to it

A rating of a hint is the sum of hint type and a logarithmic function depending on the chain length

9.2 could be a 8.5+f(length) or 9+f(shorter length)

The way in which the first chain of contradiction is searched is not using a depth-first search
However, it is also not exactly a breadth-first search, so from what I see in the code, the length difference can be at most 1 between the shortest chain and the chain found by the algorithm, thus the rating difference cannot exceed 0.1

If you take for instance your second example puzzle
Code: Select all
1....6..9..63..2...7..8..3.3......2...9...8...4......5.9..3..7...5..41..6..2....4

And preform 5 moves that leave it in the following state:
Code: Select all
1    | 2358  | 2348  |  457    | 2457   |  6     |  457 | 458  |  9
----------------------------------------------------------------------
4589 | 58    |  6    |  3      | 14579  | 1579   | 2    | 1458 | 178
----------------------------------------------------------------------
459  |  7    |  24   |  1459   |  8     | 1259   | 456  | 3    | 16
----------------------------------------------------------------------
3    |  1568 | 178   | 1456789 | 145679 | 15789  | 4679 | 2    | 167
----------------------------------------------------------------------
257  | 1256  | 9     | 14567   | 124567 | 1357   | 8    | 146  | 1367
----------------------------------------------------------------------
278  | 4     | 1278  | 16789   | 12679  | 123789 |  379 | 169  | 5
----------------------------------------------------------------------
48   |  9    | 1248  | 1568    |  3     |  158   |  56  |  7   |  268
----------------------------------------------------------------------
278  |  238  | 5     | 6789    | 679    | 4      | 1    | 689  | 2368
----------------------------------------------------------------------
6    | 138   |  1378 |  2      |  1579  |  15789 |  359 | 589  |  4

It is possible to remove 2 from C1 with chains of rating 8.8 and in the a later step remove 4 from C1 with chains of rating 8.9
Or it is possible to remove 4 from C1 with chains of rating 8.8 in the current step

So removing candidates cause SE to find longer chains
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Sudoku Explainer Fixes

Postby ronk » Sat Jan 08, 2011 11:44 pm

lksudoku wrote:It is possible to remove 2 from C1 with chains of rating 8.8 and in the a later step remove 4 from C1 with chains of rating 8.9
Or it is possible to remove 4 from C1 with chains of rating 8.8 in the current step

So removing candidates cause SE to find longer chains

That looks like a bug to me. Explainer's step moves are r1c3<>2 (8.8), r1c2<>5 (8.5) and then r1c3<>4 (8.9). The r1c3<>4 (8.8) move is still available after the r1c2<>5 move. Explainer should be finding that lower rated move.

____Image

(hp38)r1c23 = (8) r1c8 - (8)r2c9 = (hp28)r78c9 - (3)r8c9 = (3)r8c2 - (3)r1c2 = (3)r1c3 ==> r1c3=38

[edit: r1c3=38 was r1c1=38; thanks to daj95376]
Last edited by ronk on Sun Jan 09, 2011 9:14 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sudoku Explainer Fixes

Postby daj95376 » Sun Jan 09, 2011 8:28 am

LK wrote:A rating of a hint is the sum of hint type and a logarithmic function depending on the chain length

9.2 could be a 8.5+f(length) or 9+f(shorter length)

The way in which the first chain of contradiction is searched is not using a depth-first search
However, it is also not exactly a breadth-first search, so from what I see in the code, the length difference can be at most 1 between the shortest chain and the chain found by the algorithm, thus the rating difference cannot exceed 0.1

ronk wrote:That looks like a bug to me. Explainer's step moves are r1c3<>2 (8.8), r1c2<>5 (8.5) and then r1c3<>4 (8.9). The r1c3<>4 (8.8) move is still available after the r1c2<>5 move. Explainer should be finding that lower rated move.

Putting these two statements together, it seems that the (8.9) chain for r1c3<>4 is being found before the (8.8) chain in the later step. If so, then we have yet another argument for converting all puzzles to row MinLex before rating them.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer Fixes

Postby ronk » Sun Jan 09, 2011 9:51 am

daj95376 wrote:Putting these two statements together, it seems that the (8.9) chain for r1c3<>4 is being found before the (8.8) chain in the later step. If so, then we have yet another argument for converting all puzzles to row MinLex before rating them.

I don't think canonicalization ("c14n") would fix this particular issue.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sudoku Explainer Fixes

Postby lksudoku » Sun Jan 09, 2011 7:13 pm

ronk wrote:
daj95376 wrote:Putting these two statements together, it seems that the (8.9) chain for r1c3<>4 is being found before the (8.8) chain in the later step. If so, then we have yet another argument for converting all puzzles to row MinLex before rating them.

I don't think canonicalization ("c14n") would fix this particular issue.

Canonicalization will not solve the bug shown, it will still yield higher rating then possible in some cases, the solution should be to fix this bug, and if not fix it, at least run batch mode, which is less likely to have this bug appearing
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Sudoku Explainer Fixes

Postby daj95376 » Mon Jan 10, 2011 5:40 pm

lksudoku wrote:A rating of a hint is the sum of hint type and a logarithmic function depending on the chain length

9.2 could be a 8.5+f(length) or 9+f(shorter length)

The way in which the first chain of contradiction is searched is not using a depth-first search
However, it is also not exactly a breadth-first search, so from what I see in the code, the length difference can be at most 1 between the shortest chain and the chain found by the algorithm, thus the rating difference cannot exceed 0.1

If you take for instance your second example puzzle
Code: Select all
1....6..9..63..2...7..8..3.3......2...9...8...4......5.9..3..7...5..41..6..2....4

It is possible to remove 2 from C1 with chains of rating 8.8 and in the a later step remove 4 from C1 with chains of rating 8.9
Or it is possible to remove 4 from C1 with chains of rating 8.8 in the current step

So removing candidates cause SE to find longer chains

After stepping through the solution several times, I realize that a short (8.8) chain was found for r1c3<>4 at the same time a
short (8.8) chain was found and used for r1c3<>2. Later, a longer (8.9) chain was found for r1c3<>4 while the earlier chain was missed/ignored because it wasn't in the list of hints.

In any case, the list of hints contained 45 entries when both chains were selected. I'm assuming that the number of hints is fixed and, in this instance, filled before discovering the presence of the short (8.8) chain for r1c3<>4 in the later step.

If the search algorithm had been restricted to searching for (8.8) rated chains, then the list of hints wouldn't have run from 8.9 to 9.6 when r1c3<>4 was selected.

This raises the question: Does batch mode perform all hints, or just those matching the lowest rating???
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Sudoku Explainer Fixes

Postby lksudoku » Mon Jan 10, 2011 6:43 pm

daj95376 wrote:After stepping through the solution several times, I realize that a short (8.8) chain was found for r1c3<>4 at the same time a
short (8.8) chain was found and used for r1c3<>2. Later, a longer (8.9) chain was found for r1c3<>4 while the earlier chain was missed/ignored because it wasn't in the list of hints.

The earlier chain was missed due to a bug causing SE to find a longer chain for the same move (only one chain is found for a move)

daj95376 wrote:This raises the question: Does batch mode perform all hints, or just those matching the lowest rating???

batch mode performs all hints matching the loswest rating only

You can view the log (-l) to see which hints were applied
lksudoku
 
Posts: 90
Joined: 06 October 2010

Re: Sudoku Explainer Fixes

Postby lksudoku » Mon Apr 25, 2011 8:29 pm

Another fix/enhancement to Sudoku Explainer and serate

n.
Improved the way SE searches for chains so that it can find shorter chains than before in some cases thus reducing the rating of some puzzles, this fix also solves some of the cases where relabeling clues changed the rating

The following puzzles are examples that can be solved with shorter chains in this version
Code: Select all
..12......3...45..6......7.2..1...8.....2.....9......3.5......9..76...1......34.7
1..2..3......1..4...5..6..78.....2...3..9..8...4.....12..8..7...1..5......3..4..6
..1..23...4..5..6.7.......8...5.......5.4.9.......8...8.......7.6..9..4...31..2..

The following puzzles are an example for relabeling rating change bug fix
Code: Select all
5.....2...9.3.....8.6.....17..2......8..9......4..1.6..7.5..3....2.8..4.4....27.9
5.....2...1.3.....8.6.....97..2......8..1......4..9.6..7.5..3....2.8..4.4....27.1


Numbered this version as 1.2.9.0, can be downloaded from this page
lksudoku
 
Posts: 90
Joined: 06 October 2010

Postby Pat » Thu Apr 28, 2011 9:04 am

lksudoku wrote:
Numbered this version as 1.2.9.0,

can be downloaded from
    sites.google.com/site/sefixshare/files/FIXED14SudokuExplainer.jar?attredirects=0&d=1

and how about the source-code?
    elsewhere, lksudoku (2011.Mar.28) wrote:
    The sources for the latest version can be found in
      sites.google.com/site/sefixshare/files/SEFix13MainSrc.zip?attredirects=0&d=1
    They can be built using jdk,
    by running the mymake.bat batch file
User avatar
Pat
 
Posts: 3449
Joined: 18 July 2005

PreviousNext

Return to Software