PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Interactive on-site game threads go here

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby 1to9only » Wed Jun 16, 2021 7:28 am

1to9only wrote:I've built a list of SE Ratings from puzzles submitted in the Patterns Game ONLY (up to 0420 inclusive)!!

I updated the lists a couple days ago, with a bit more details added to the 6.x,7.x and the multiple/dynamic/nested chains, e.g.
Code: Select all
10.2, Dynamic Forcing Chains (+), ED=9.0 + 1.2 (193-256 nodes) [Contradiction Forcing Chain]
10.2, Nested Forcing Chains (+ Forcing Chains), ED=9.5 + 0.7 (33-48 nodes) [Cell Forcing Chains]
10.2, Nested Forcing Chains (+ Forcing Chains), ED=9.5 + 0.7 (33-48 nodes) [Contradiction Forcing Chain]
10.2, Nested Forcing Chains (+ Forcing Chains), ED=9.5 + 0.7 (33-48 nodes) [Region Forcing Chains]
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby 1to9only » Tue Jun 22, 2021 8:32 am

I've created another list, ER List: https://github.com/1to9only/patterns-game/raw/main/001-460-erlist.txt

[To View: Click on link] [To Save: Right-click on link, and select 'Save linked content as...']
This ER List lists the most recent submitted puzzle that matches the ER rating, e.g.

Code: Select all
 4.5, Unique Rectangle type 1                       .5.9..7....3..2.8.....4.5.2.7.1..8.............4..8.1.6.1.7.....3.6..1....8..1.2. # 0459  54    4.5/4.5/2.8
 4.5, Unique Rectangle type 2                       1...2..3..3.4....5..2..61...2.7....85....96....3.6......9.7.4..7.......1.1.9...7. # 0455  62    4.5/4.5/3.4
 4.5, Unique Rectangle type 3 (w/Hidden Pair)       ..4..5....7..3..4.3..8....5..36....2.2....8..6....8.3.....5...4.9...1.5...79..2.. # 0460  68    4.5/4.5/3.4
 4.5, Unique Rectangle type 4                       ..1..2....3..4..5.5..6....2..61....7.8....1..1....7.8.....9...6.4...3.2...97..8.. # 0460  91    4.5/4.5/3.6

Edit 04/26: updated list and link.
Last edited by 1to9only on Tue Apr 26, 2022 10:01 am, edited 2 times in total.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

PGExplainer (2021.9.28)

Postby 1to9only » Tue Sep 28, 2021 9:45 am

I've modified PGExplainer (2021.9.28) here to rate sudokus with multiple solutions.
Rating sudokus with multiple solutions is about twice as fast as the SukakuExplainer I posted about here.

Options:
Code: Select all
-M      for sudokus with multiple solution

-N      use with -M, disable Nested Forcing Chains checks
-D      use with -M, disable Dynamic Forcing Chains checks (implies -N)


Example:
Code: Select all
java.exe -Xrs -Xmx1g -cp PGExplainer.jar sudoku.serate -M --input=puzzles.txt --output=output.txt

java.exe -Xrs -Xmx1g -cp PGExplainer.jar sudoku.serate -M -N --input=puzzles.txt --output=output.txt


For the Patterns Game, either of the released versions (2021.3.30 or 2021.9.28) can be used.
The speed differences are not noticeable (maybe a few milliseconds!).
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Postby Pat » Sat Oct 02, 2021 4:41 pm


    where it produces 2 different results,
    fixing this bug would be justified

1to9only wrote:The unknown bug in se rating ???
was posted by champagne in July 2010,
so the problem has been known for years!!

PGExplainer is just a slim-down version of SE, so the bug will still be there. I come across this problem every now and then!

Rating the puzzles on their own (PGExplainer):
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/10.0/10.0/9.4

Code: Select all
1.68......35.2..6.82...9...5.......4.6.....3...2...7.......1.49.5..3.17....9..3.5 ED/9.9/9.9/9.4


Rating the two puzzles together (PGExplainer):
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4
1.68......35.2..6.82...9...5.......4.6.....3...2...7.......1.49.5..3.17....9..3.5 ED/9.9/9.9/9.4


The bug was fixed by lksudoku a long time ago, and the fix is in SudokuMonster's SE when using newer techniques and ratings.

User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby 1to9only » Sat Oct 02, 2021 6:03 pm

Pat wrote:
1to9only wrote:The bug was fixed by lksudoku a long time ago, and the fix is in SudokuMonster's SE when using newer techniques and ratings.

I've now checked SudokuMonster's SE source code and lksudoku's fix has not been applied, so I've edited that post to:
The bug was fixed by lksudoku a long time ago, and the fix is NOT in SudokuMonster's SE when using newer techniques and ratings.

g.r.emlin still uses SE 1.2.1.3 to rate submissions, so fixing PGExplainer will not make the problem go away.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby Pat » Sat Oct 02, 2021 6:16 pm

it certainly would save us the hedache
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby 1to9only » Sat Oct 02, 2021 6:35 pm

When I have some time, I may create a fixed version and run it through some recent games results, some have high rated puzzles.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby JPF » Sat Oct 02, 2021 9:36 pm

Is there a way to make g.r.emlin use a modified version of SExplainer or PGExplainer without this bug?

JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby 1to9only » Sun Oct 03, 2021 9:05 am

JPF wrote:Is there a way to make g.r.emlin use a modified version of SExplainer or PGExplainer without this bug?JPF

I think Jason (Site-Admin) will be the one to make the update. PGExplainer can be renamed to SudokuExplainer, but some script changes are required (SE's diuf.sudoku.test.serate to PGE's sudoku.serate). Or I can build a version of PGExplainer (with diuf.sudoku.test.serate) that can be a direct replacement. When rating Multiple Forcing Chains, PGE is about (rough estimate) 4 times faster than SE.

I've done some testing of lksudoku's fix on several vintages of SE: Testing with JPF's ED=10.0 submission, repeated 10 times, with a few seconds gap between each test.

Unmodified versions of SE (i.e. no lksudoku's fix):
Code: Select all
                                        unmodified
                                        3 secs  5 secs  10 secs

SE      304,777         ED=10.0         x10     x10     x10
        original        ED=9.9                  0

SE(1)   281,366         ED=10.0                 0
        private         ED=9.9                  x10

SKE     2021.9.28       ED=10.0         x6      x7
                        ED=9.9          x4      x3

PGE     56,712          ED=10.0         x4      x6
        released        ED=9.9          x6      x4

Modified versions of SE (i.e. with lksudoku's fix):
Code: Select all
                                        modified (lksudoku's fix)
                                        3 secs  5 secs  10 secs

SE(1)   282,185         ED=10.0                 x10
        private         ED=9.9                  0

SKE     2021.10.3       ED=10.0                 x10
                        ED=9.9                  0

PGE     80,566          ED=10.0                 x10
        private         ED=9.9                  0

(1) private build (Java-6u45) of SE 1.2.1.3, with no debugging info. Other builds are Java-8, usually a recent release at the time of the build.
SKE is my current (development) version of SukakuExplainer.

I have no explanation for the results of the unmodified SE and SE(1), maybe it's a Java issue (HashMap implementation, as noted by lksudoku), all tests were run using Java-8 (java version "1.8.0_301").

For some technical stuff, I dumped the list of (available) Forcing Chains for the 2 steps leading to the ED=10.0 or ED=9.9 rating - it may be insightful to someone, but I myself will not follow this up as lksudoku's fix appears to have resolved the problem.

ED=10.0 case:
Code: Select all
+----------------------+----------------------+----------------------+
| 1      479    8      | 5      479    349    | 2367   2469   2467   |
| 479    3      2      | 1789   6      1489   | 78     5      1478   |
| 6      5      47     | 1378   14789  2      | 378    89     148    |
+----------------------+----------------------+----------------------+
| 8      147    34567  | 2367   12457  1346   | 2567   246    9      |
| 457    2      14567  | 16789  145789 14689  | 5678   3      4678   |
| 357    47     9      | 23678  24578  34568  | 1      2468   2678   |
+----------------------+----------------------+----------------------+
| 2459   489    45     | 2689   2589   7      | 268    1      3      |
| 259    6      15     | 1289   3      1589   | 4      7      28     |
| 237    178    37     | 4      128    168    | 9      268    5      |
+----------------------+----------------------+----------------------+

Contradiction Forcing Chain (w/68 nodes): R4C3.4 on ==> R1C9.2 both on & off: r4c3<>4
Contradiction Forcing Chain (w/98 nodes): R5C6.6 on ==> R6C4.2 both on & off: r5c6<>6
Contradiction Forcing Chain (w/98 nodes): R6C6.3 on ==> R7C4.6 both on & off: r6c6<>3
Contradiction Forcing Chain (w/103 nodes): R5C5.5 on ==> R5C9.7 both on & off: r5c5<>5
Contradiction Forcing Chain (w/104 nodes): R4C3.7 on ==> R1C8.4 both on & off: r4c3<>7
Contradiction Forcing Chain (w/124 nodes): R8C6.1 on ==> R9C8.8 both on & off: r8c6<>1
Contradiction Forcing Chain (w/127 nodes): R6C1.7 on ==> R4C6.4 both on & off: r6c1<>7
Contradiction Forcing Chain (w/134 nodes): R4C5.1 on ==> R9C8.8 both on & off: r4c5<>1
Contradiction Forcing Chain (w/150 nodes): R1C6.9 on ==> R7C7.2 both on & off: r1c6<>9
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 9.9, Contradiction Forcing Chain (w/68 nodes): R4C3.4 on ==> R1C9.2 both on & off: r4c3<>4

Contradiction Forcing Chain (w/98 nodes): R5C6.6 on ==> R6C4.2 both on & off: r5c6<>6
Contradiction Forcing Chain (w/98 nodes): R6C6.3 on ==> R7C4.6 both on & off: r6c6<>3
Contradiction Forcing Chain (w/102 nodes): R5C5.5 on ==> R5C9.7 both on & off: r5c5<>5
Contradiction Forcing Chain (w/104 nodes): R4C3.7 on ==> R1C8.4 both on & off: r4c3<>7
Contradiction Forcing Chain (w/124 nodes): R8C6.1 on ==> R9C8.8 both on & off: r8c6<>1
Contradiction Forcing Chain (w/127 nodes): R6C1.7 on ==> R4C6.4 both on & off: r6c1<>7
Contradiction Forcing Chain (w/134 nodes): R4C5.1 on ==> R9C8.8 both on & off: r4c5<>1
Contradiction Forcing Chain (w/150 nodes): R1C6.9 on ==> R7C7.2 both on & off: r1c6<>9
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 10.0, Contradiction Forcing Chain (w/98 nodes): R5C6.6 on ==> R6C4.2 both on & off: r5c6<>6

ED=9.9 case:
Code: Select all
pencilmarks as above.

Contradiction Forcing Chain (w/68 nodes): R4C3.4 on ==> R1C9.2 both on & off: r4c3<>4
Contradiction Forcing Chain (w/95 nodes): R5C6.6 on ==> R8C4.2 both on & off: r5c6<>6 <- this is different
Contradiction Forcing Chain (w/98 nodes): R6C6.3 on ==> R7C4.6 both on & off: r6c6<>3
Contradiction Forcing Chain (w/103 nodes): R5C5.5 on ==> R5C9.7 both on & off: r5c5<>5
Contradiction Forcing Chain (w/104 nodes): R4C3.7 on ==> R1C8.4 both on & off: r4c3<>7
Contradiction Forcing Chain (w/124 nodes): R8C6.1 on ==> R9C8.8 both on & off: r8c6<>1
Contradiction Forcing Chain (w/127 nodes): R6C1.7 on ==> R4C6.4 both on & off: r6c1<>7
Contradiction Forcing Chain (w/134 nodes): R4C5.1 on ==> R9C8.8 both on & off: r4c5<>1
Contradiction Forcing Chain (w/150 nodes): R1C6.9 on ==> R7C7.2 both on & off: r1c6<>9
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 9.9, Contradiction Forcing Chain (w/68 nodes): R4C3.4 on ==> R1C9.2 both on & off: r4c3<>4

Contradiction Forcing Chain (w/95 nodes): R5C6.6 on ==> R8C4.2 both on & off: r5c6<>6
Contradiction Forcing Chain (w/98 nodes): R6C6.3 on ==> R7C4.6 both on & off: r6c6<>3
Contradiction Forcing Chain (w/102 nodes): R5C5.5 on ==> R5C9.7 both on & off: r5c5<>5
Contradiction Forcing Chain (w/104 nodes): R4C3.7 on ==> R1C8.4 both on & off: r4c3<>7
Contradiction Forcing Chain (w/124 nodes): R8C6.1 on ==> R9C8.8 both on & off: r8c6<>1
Contradiction Forcing Chain (w/127 nodes): R6C1.7 on ==> R4C6.4 both on & off: r6c1<>7
Contradiction Forcing Chain (w/134 nodes): R4C5.1 on ==> R9C8.8 both on & off: r4c5<>1
Contradiction Forcing Chain (w/150 nodes): R1C6.9 on ==> R7C7.2 both on & off: r1c6<>9
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 9.9, Contradiction Forcing Chain (w/95 nodes): R5C6.6 on ==> R8C4.2 both on & off: r5c6<>6

Edit: I've added pencilmarks grid.
The '<- this is different' highlighted line is sometimes not there (instead has the '(w/98 nodes)' line) in both ED=10.0 and ED=9.9 ratings. So this may be a 'red herring'.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby tarek » Sun Oct 03, 2021 1:38 pm

1to9only wrote:
Pat wrote:
1to9only wrote:The bug was fixed by lksudoku a long time ago, and the fix is in SudokuMonster's SE when using newer techniques and ratings.

I've now checked SudokuMonster's SE source code and lksudoku's fix has not been applied, so I've edited that post to:
The bug was fixed by lksudoku a long time ago, and the fix is NOT in SudokuMonster's SE when using newer techniques and ratings.

That specific fix was not implemented as Mladen (who analyzed the code) suggested that the fix would work for some examples but not others (and also may create new rating discrepancies) as it is to do with Hash tables. The fix therefore is unpredictable and based on his advice it was not implemented!!

There wasn't a proper fix suggested for this very specific program and Sukaku Explainer continues to deal with these examples as the original sudoku explainer did
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: PGExplainer - a Minimal SudokuExplainer, in 56,712 bytes

Postby 1to9only » Sun Oct 03, 2021 2:30 pm

Tarek, Thanks for the info. Looks like the bugs in SE will live on!!
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Postby Pat » Sun Oct 03, 2021 3:48 pm

lksudoku's fix appears to have resolved the problem.


no, i never studied the code;
yet i expect it to be a clean fix
and to create no new issue

any place that the bug allows different results —
the fix will force the one result obtained by
rating the puzzle alone

(and, no need to bother g.r.emlin)
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby Pat » Fri Oct 08, 2021 10:22 pm

tarek wrote:

The bug was fixed by lksudoku a long time ago



That specific fix was not implemented as Mladen (who analyzed the code) suggested that the fix would work for some examples but not others (and also may create new rating discrepancies) as it is to do with Hash tables. The fix therefore is unpredictable and based on his advice it was not implemented!!




Pat wrote:
no, i never studied the code;
yet i expect it to be a clean fix
and to create no new issue

any place that the bug allows different results —
the fix will force the one result obtained by
rating the puzzle alone


    champagne, where are you??
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

lksudoku fix revisited

Postby 1to9only » Fri Feb 25, 2022 1:30 pm

tarek wrote:
1to9only wrote:I've now checked SudokuMonster's SE source code and lksudoku's fix has not been applied, so I've edited that post to:
The bug was fixed by lksudoku a long time ago, and the fix is NOT in SudokuMonster's SE when using newer techniques and ratings.

That specific fix was not implemented as Mladen (who analyzed the code) suggested that the fix would work for some examples but not others (and also may create new rating discrepancies) as it is to do with Hash tables. The fix therefore is unpredictable and based on his advice it was not implemented!!

There wasn't a proper fix suggested for this very specific program and Sukaku Explainer continues to deal with these examples as the original sudoku explainer did

I revisited the lksudoku fix, after another SE mismatch in Patterns Game 453:
Code: Select all
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4

The lksudoku fix is only applied to the nested parts of chains in dynamic and multiple chains.
A version of lksudoku fix must also be applied to the final chain when determining the chain to be selected/applied.

Example 1to9only's SukakuExplainer (2022.1.4), with the same grid appearing multiple times in a file:
Code: Select all
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4 ED=10.3/10.3/3.4
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4 ED=10.3/10.3/3.4
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4 ED=10.2/10.2/3.4

Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=9.9/9.9/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=9.9/9.9/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=10.0/10.0/9.4

When testing a fix applied to BOTH nested and final chains, resulting in the same ratings:
Code: Select all
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4 ED=10.2/10.2/3.4
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4 ED=10.2/10.2/3.4
...6..4...3.....5...5.7...98..4.6.....2.9.......2.71..4....18...5......3..9....7. ED=10.2/10.2/3.4 ED=10.2/10.2/3.4

Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 ED/9.9/9.9/9.4 ED=10.0/10.0/9.4

I need to test this with a few other example grids.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Postby 1to9only » Wed Mar 23, 2022 2:02 pm

1to9only wrote:The lksudoku fix is only applied to the nested parts of chains in dynamic and multiple chains.
A version of lksudoku fix must also be applied to the final chain when determining the chain to be selected/applied.

I have fixed the lksudoku fix!!
I have a version of SE that now (consistently!) produces the same rating for all Patterns Game se-mismatches from game 84 onwards (95 of them!).
I'll be putting the fixed lksudoku fix in my various versions of SE.
The fixed code should not be used in the Patterns Game as that still uses the original (flawed !) SE.
PGExplainer will not have this fix!
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

PreviousNext

Return to Interactive games