The New Sudoku Players' Forum

[daj95376]

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

[ronk]

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.

[daj95376]

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

[ronk]

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.

[lksudoku]

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

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

[daj95376]

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.

[lksudoku]

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

[ronk]

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.

____

(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]

[daj95376]

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

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.

[ronk]

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.

[lksudoku]

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

[daj95376]

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???

[lksudoku]

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)

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]

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

[Pat]

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?

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