Comments on Sudoku Explainer and Sudoku Assistant

Programs which generate, solve, and analyze Sudoku puzzles

Comments on Sudoku Explainer and Sudoku Assistant

Postby Glyn » Thu Aug 07, 2008 9:22 pm

I have started a new topic for this.

999_Springs wrote:Intrigued by the failure of Bob Hanson's solver to remove a single candidate and the fact that SE needs 12 sub-chains in some enormous first step, I ask these questions:
1. How far does Bob Hanson's ++depth actually go?
2. Do all puzzles of this sort of difficulty stump Bob Hanson's solver, or just this one?
3. Why choose r1c7#3 in Mauricio's puzzle? Is this the simplest elimination? (I can hardly believe this is.)


1) I don't know the answer here. You could test puzzles of increasing ER, determine the last to succeed and examine Sudoku Assistant's solving path to see if that gives a clue.
2) Other puzzles of this complexity will fox Bob Hanson's solver eg Easter Monster.
3) Of the 17 eliminations of ER 11.2 r1c7<>3 is the simplest.
In this cycle of the program SE finds 76 conclusions up to ER 11.6. The last Cell Forcing Chain having a mind numbing 116 dynamic nested chains supporting the 4 primary chains.
Applying all these conclusions simultaneously maintains symmetry, leaving a few singles to mop up. There are fluctuations in the logical sequences leading to symmetrical eliminations and hence different ERs and orders of priority.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby Draco » Fri Aug 08, 2008 4:06 am

I've been following some of the discussions on SE ratings on and off; while I do not grok all of its advanced techniques, I do understand forcing chains / nets to some degree. I fed this puzzle my solver generated to SE
Code: Select all
.2......8...4.2.......5..438.....31..7..2..8..19.....564..8.......6.5...3......7.

14579 2     134567 | 1379  13679 13679 | 15679   569  8   
1579  35689 135678 | 4     13679 2     | 15679   569  1679
179   689   1678   | 1789  5     16789 | 12679   4    3   
-------------------+-------------------+-------------------
8     56    2456   | 579   4679  4679  | 3       1    24679
45    7     3456   | 1359  2     13469 | 469     8    469 
24    1     9      | 378   3467  34678 | 2467    26   5   
-------------------+-------------------+-------------------
6     4     1257   | 12379 8     1379  | 1259    2359 129 
1279  89    1278   | 6     13479 5     | 12489   239  1249
3     589   1258   | 129   149   149   | 1245689 7    12469

SE reports:

Difficulty rating: 7.3
This Sudoku can be solved using the following logical methods:
56 x Hidden Single
2 x Direct Hidden Pair
1 x Pointing
1 x Turbot Fish
6 x Forcing Chain

Taking the puzzle thru the Turbot Fish step (same as SSTS until stuck) leaves you with:
Code: Select all
14579 2   14567 | 1379  13679 13679 | 15679  569  8   
1579  3   8     | 4     1679  2     | 15679  569  1679
179   69  167   | 1789  5     16789 | 2      4    3   
----------------+-------------------+------------------
8     56  2456  | 579   479   479   | 3      1    2479
45    7   3     | 159   2     1469  | 469    8    469 
24    1   9     | 378   3467  34678 | 467    26   5   
----------------+-------------------+------------------
6     4   1257  | 12379 8     1379  | 159    2359 129 
1279  89  127   | 6     13479 5     | 1489   239  149 
3     589 125   | 129   149   149   | 145689 7    12469

One fairly simple chain cracks the puzzle to singles:

r3c2=6 r4c3=6 +
r3c2=9 [r1c1<>9 r2c1<>9 r3c1<>9] r8c1=9 r6c1=2 => r4c3<>2

There are several chains/nets possible from the SSTS stop-point; finding this one required some searching/testing to score it against other candidate "next moves."

Point of this being that SE seems to select chains based not on how much they simplify the puzzle but on other criteria (length of chain for instance, or perhaps avoiding "indirect" forcing such as the 9's in the second chain):?:

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby Glyn » Fri Aug 08, 2008 7:51 am

Draco the elimination that you gave is found by SE with ER 8.4 as:
Code: Select all
(2=4)r6c1-(4=5)r5c1-(5)r12c3=(5-4)r1c3=(4)r4c3                    (r4c3<>2 SE 8.4)

Doesn't look too bad, it's there before the Turbot and still leaves singles.

As SE doesn't look a move ahead it can't select the attractive elimination of a bilocation candidate.
Here's the SE route always applying the next 'simplest' move
Code: Select all
(2)r4c9=(2)r4c3-(2)r6c1=(2)r8c1                                   (r8c9<>2 ER 6.6)
(4=2)r6c1-(2)r6c8=(2-7)r4c9=(7)r6c7                               (r6c7<>4 ER 7.1)
(7)r2c9=(7)r4c9-(7=6)r6c7-(6)r9c7=(6)r9c9                         (r2c9<>6 ER 7.1)
(6)r9c9=(6-8)r9c7=(8-5)r9c2=(5-6)r4c2=(6-2)r4c3=(2)r4c9           (r9c9<>2 ER 7.3)
(6)r9c9=(6-8)r9c7=(8-5)r9c2=(5-6)r4c2=(6-2)r4c3=(2)r4c9-(2=6)r6c8 (r5c9<>6 ER 7.3)
Hidden single r9c9=6
(5)r4c4=(5-1)r5c4=(1-6)r5c6=(6)r5c7-(6=2)r6c8-(2)r6c1=(2)r4c3     (r4c3<>5 ER 7.3)
(4=2)r6c1-(2=6)r6c8-(6)r5c7=(6-1)r5c6=(1-5)r5c4=(5)r5c1           (r5c1<>4 ER 7.3)


Some of the ER7.3 chains are longer than the ER8.6 move which is penalized for using a region.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby daj95376 » Fri Aug 08, 2008 11:26 am

Code: Select all
 .2......8...4.2.......5..438.....31..7..2..8..19.....564..8.......6.5...3......7.

 Singles

 +--------------------------------------------------------------------------------+
 |  14579   2       14567   |  1379    13679   13679   |  15679   569     8       |
 |  1579    3       8       |  4       1679    2       |  15679   569     1679    |
 |  179     69      167     |  1789    5       16789   |  2       4       3       |
 |--------------------------+--------------------------+--------------------------|
 |  8       56      2456    |  579     4679    4679    |  3       1       24679   |
 |  45      7       3       |  159     2       1469    |  469     8       469     |
 |  24      1       9       |  378     3467    34678   |  467     26      5       |
 |--------------------------+--------------------------+--------------------------|
 |  6       4       1257    |  12379   8       1379    |  159     2359    129     |
 |  1279    89      127     |  6       13479   5       |  1489    239     1249    |
 |  3       589     125     |  129     149     149     |  145689  7       12469   |
 +--------------------------------------------------------------------------------+
 # 145 eliminations remain

 4-[r5c1]-5-[r12c1]=5=[r1c3]=4=[r1c1]  =>  [r6c1]<>4

 Singles
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby 999_Springs » Sun Aug 10, 2008 12:15 pm

How is SE's performance on this puzzle?
Code: Select all
7.8|...|3..
...|2.1|...
5..|...|...
---+---+---
.4.|...|.26
3..|.8.|...
...|1..|.9.
---+---+---
.9.|6..|..4
...|.7.|5..
...|...|...


Sudoku Assistant takes the puzzle 6 times through "Hypothesis and Disproof" and some of these result in VERY long chains.

I solved this puzzle by hand 2 and a half years ago. It remains the hardest I have ever solved by hand. I still have the solving path. It requires 2 short-ish chains with subsets, a (useless?) swordfish and a turbot, together with loads of subsets and locked candidates. Much shorter than Sudoku Assistant.
Basic techniques get here:
Code: Select all
     7      126        8 |  459   4569    4569 |    3   1456   1259
   469       36     3469 |    2  34569       1 | 4679  45678   5789
     5     1236   123469 |   78   3469      78 |12469    146    129
------------------------------------------------------------------------------
   189        4     1579 | 3579     59    3579 |  178      2      6
     3     1267    12679 |  479      8   24679 |  147   1457    157
   268    25678     2567 |    1   2456   24567 |  478      9      3
------------------------------------------------------------------------------
   128        9    12357 |    6    125    2358 |  127   1378      4
 12468    12368    12346 | 3489      7   23489 |    5   1368   1289
 12468  1235678  1234567 |34589  12459  234589 |12679  13678  12789
Then:

r5c2-7(-r5c4)-r5c789=7=hidden pair r46c7-7-r2c7=7=hidden pair r2c89=5=r2c5-5-r4c5-9-r5c4-4-r5c7-1-r5c8, no value for r5c9
hidden pair in c2
r8c2=8
3 is locked in c3b7
r2c7-7(-r7c7)-naked triple r456c7-1-r7c7-2(-r7c5)-r7c1-1(-r4c1)-r7c5-5-r4c5-9(-r5c4)-r4c1-8-r4c7-1-r5c7-4-r5c4-7, no place for 7 in b6
hidden pair in r2
r2c5=5
r4c5=9
r3c5=3
r2c2=3
4,6,9 are locked in r1b2
naked pair in r7
r7c7=7
hidden pair in r5
1,4,8 locked in c7b6, 5,7 locked in r5b6
r5c4=4
r1c4=9
r8c4=3
r5c7=1
r4c7=8
r4c1=1
r6c7=4
r5c3=9
r2c1=9
r2c7=6
r2c3=4
r4c6=3
r6c1=8
r7c1=2
r7c5=1
r3c8=4
naked pairs in b5, b8, b7, r8
r8c1=4
r9c1=6
r8c3=1
r8c8=6
naked pairs in r6, b9
swordfish in 2s in c357
turbot fish in 5s r69c2, r49c4 => r4c3, r6c6 <> 5
singles

(I'm not entirely sure about chain notation.)
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby 999_Springs » Tue Aug 12, 2008 3:36 pm

I have just noticed that Bob Hanson put this up on his website:
Code: Select all
1..|...|.89
...|..9|..2
...|...|45.
---+---+---
..7|6..|...
.3.|.4.|...
9..|..2|..5
---+---+---
..4|.7.|...
5..|..8|.1.
.6.|3..|...

which it can't solve.

What are the rating and techniques needed by SE to solve this?
Last edited by 999_Springs on Tue Aug 12, 2008 1:34 pm, edited 1 time in total.
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby gsf » Tue Aug 12, 2008 4:52 pm

999_Springs wrote:I have just noticed that Bob Hanson put this up on his website:
Code: Select all
1..|...|.89
...|..9|..2
...|...|45.
---+---+---
..7|6..|...
.3.|.4.|...
9..|..2|..5
---+---+---
..4|.7.|...
5..|..8|.1.
.6.|3..|...

which it can't solve.

this is the Easter Monster
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby 999_Springs » Tue Aug 12, 2008 5:30 pm

Thank you to all those who PMed me about how to get SE to work on my computer. I installed a newer version of Java half an hour ago and now it works.

Oh dear.
SE is even worse than Bob Hanson's solver at this puzzle:
999_Springs wrote:
Code: Select all
7.8|...|3..
...|2.1|...
5..|...|...
---+---+---
.4.|...|.26
3..|.8.|...
...|1..|.9.
---+---+---
.9.|6..|..4
...|.7.|5..
...|...|...


It did ALL THIS.
SE wrote:Analysis results
Difficulty rating: 9.5
This Sudoku can be solved using the following logical methods:
61 x Hidden Single
1 x Direct Hidden Pair
1 x Direct Hidden Triplet
11 x Pointing
1 x Claiming
2 x Hidden Pair
1 x Forcing Chain
1 x Nishio Forcing Chains
2 x Cell Forcing Chains
5 x Region Forcing Chains
1 x Dynamic Double Forcing Chains
11 x Dynamic Region Forcing Chains
1 x Dynamic Cell Forcing Chains
15 x Dynamic Contradiction Forcing Chains
1 x Dynamic Region Forcing Chains (+)
1 x Dynamic Double Forcing Chains (+)

39 forcing chains, almost all of which eliminated completely pointless candidates which did nothing. I don't understand why SE does all this.
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Pat » Wed Aug 13, 2008 5:01 am

999_Springs wrote:39 forcing chains, almost all of which eliminated completely pointless candidates which did nothing. I don't understand why SE does all this.


at each step, it finds what it considers the simplest move --
thus including all the red herrings along the way.
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby 999_Springs » Fri Aug 15, 2008 2:01 pm

999_Springs wrote:
Code: Select all
7.8|...|3..
...|2.1|...
5..|...|...
---+---+---
.4.|...|.26
3..|.8.|...
...|1..|.9.
---+---+---
.9.|6..|..4
...|.7.|5..
...|...|...


Looking at SE's hints at each step I see that my first chain elimination was SE's 16th choice elimination and my second chain elimination was SE's 18th choice elimination through a longer route.
So did I just get EXTREMELY lucky with the chains I picked? ... Or are human solvers generally better at picking chains than SE...?
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby RW » Fri Aug 15, 2008 6:47 pm

999_Springs wrote:Looking at SE's hints at each step I see that my first chain elimination was SE's 16th choice elimination and my second chain elimination was SE's 18th choice elimination through a longer route.
So did I just get EXTREMELY lucky with the chains I picked? ... Or are human solvers generally better at picking chains than SE...?

SE rates puzzles by the hardest move neccessary (hardest according to it's own measure of course). The only way to do this is to always pick the "easiest" move. This is how SE picks it's moves and this will almost never lead to the shortest solution. For the hardest puzzles, a human picking candidates to eliminate will probably survive with a lot fewer chains, but the chains will be longer than SE's chains.

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby 999_Springs » Thu Aug 21, 2008 2:02 pm

What exactly are Sudoku Assistant's "strong chains"? For months I thought that they were bidirectional cycles (well, they certainly do look like bidirectional cycles) except the directions are in pink and yellow instead of SE's orange and green.

But then I accidentally came across this:
Code: Select all
.13|4.7|825
..4|8.2|631
28.|1.3|947
---+---+---
...|.24|318
342|918|756
8.1|.36|294
---+---+---
429|671|583
.38|245|1.9
1..|389|4.2

Sticking this into SE and clicking on the "Get next hint" button a few times yields 3 bidirectional cycle eliminations. Sticking it into Sudoku Assistant, I discovered that it needs weak links to solve (I'm not sure what these are, either). So what are these mysterious "strong chains"?
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Draco » Thu Sep 18, 2008 10:46 pm

999_Springs wrote:...
Code: Select all
.13|4.7|825
..4|8.2|631
28.|1.3|947
---+---+---
...|.24|318
342|918|756
8.1|.36|294
---+---+---
429|671|583
.38|245|1.9
1..|389|4.2


Sticking this into SE and clicking on the "Get next hint" button a few times yields 3 bidirectional cycle eliminations. Sticking it into Sudoku Assistant, I discovered that it needs weak links to solve (I'm not sure what these are, either). So what are these mysterious "strong chains"?


While you asked this several weeks ago, I only just read the post. I am unsure what either SE or SA is doing (actually, unaware is more like it), but there is a single chain that (I beleive) uses only strong links and cracks the puzzle to singles:
Code: Select all
.134.7825..48.263128.1.3947....243183429187568.1.36294429671583.382451.91..3894.2

69   1    3   | 4  69 7 | 8 2  5
579  579  4   | 8  59 2 | 6 3  1
2    8    56  | 1  56 3 | 9 4  7
--------------+---------+-------
5679 5679 567 | 57 2  4 | 3 1  8
3    4    2   | 9  1  8 | 7 5  6
8    57   1   | 57 3  6 | 2 9  4
--------------+---------+-------
4    2    9   | 6  7  1 | 5 8  3
67   3    8   | 2  4  5 | 1 67 9
1    567  567 | 3  8  9 | 4 67 2

r4c1=9 r1c1=6 + r4c2=9 r9c2=6 ==> r8c1<>6


My solver does something that, as other comments earlier in this thread explained, SE does not do: it looks at all the chains/nets it can find based on bi-values and picks the one that does the most to simplify the puzzle. Simplify is somewhat subjective and based both on my understanding of the SSTS solving order (at some point in time:) ) and my own opinions about which chains/nets are "best." Sometimes it yields fairly nice results.

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008


Return to Software