The New Sudoku Players' Forum

[ronk]

Nice loops! Your loops and finned X-Wing used less than half the number of steps I needed with forcing chains/nets.

Danny still seems to have the shortest solution so far.

What is the point of comparing a solution found manually to those found with computer programs?

[daj95376]

What is the point of comparing a solution found manually to those found with computer programs?

Comparing was not my intent on posting my puzzle and PM. My solver lists non-redundant chains found in a PM. It also performs all of them before continuing. In many PMs, the result is a cascade of Singles.

I then manually try to find a subset of the chains that will produce the same effect, but often find it difficult and frustrating. So, I posted an example and was hoping that someone would have some insight into how to select the important chains.

note: the {nnn} prepending my chain output is the number of eliminations if a chain was performed using basic techniques. Obviously, the importance of [r7c6]<>1 is not properly reflected in the {1} associated with it.

[eleven]

What is the point of comparing a solution found manually to those found with computer programs?

In general, manual solutions obviously will be longer than program solutions, unless you optimize them by means of a program (what i do sometimes, especially for harder puzzles). But despite of some lucky tries it is much better traceable, how one could find the same (manually).
So, hard to compare.

[hobiwan]

I then manually try to find a subset of the chains that will produce the same effect, but often find it difficult and frustrating. So, I posted an example and was hoping that someone would have some insight into how to select the important chains.

Before I started writing my own solver I played around with a few programs. It appeared to me that they just took the first solution they found, so I tried a different approach: My solver takes the step first that produces the most eliminations. It sounded like a good idea to me, but I can't find any real difference to other solutions (the length of the solutions seems to be pretty random).

Apart from attacking back doors one possibility I can think of is using steps first that lead to singles. Has anybody tried that already?

When looking for simpler solutions I often look at the last advanced step and try to reproduce the eliminations earlier in the solution path (often using a different technique). So trying to reproduce this behaviour is the other thing that comes in mind (but it would probably result in a significant amount of trial and error - and it could be just the same as looking for back doors which could be considered cheating).

[eleven]

A manual player doesn't know about backdoors. But - when stuck - she would never put any effort in trying to eliminate a number, which is present more than 2 times in the 3 units (exceptions might be alluring ALS's).
So "My solver takes the step first that produces the most eliminations" sounds good for me.
Another difference to programs for me is, that both on paper and with (graphical) programs combinations of strong links (with different numbers) are much harder to see than (longer) bivalue chains.

[daj95376]

Before I started writing my own solver I played around with a few programs. It appeared to me that they just took the first solution they found, so I tried a different approach: My solver takes the step first that produces the most eliminations. It sounded like a good idea to me, but I can't find any real difference to other solutions (the length of the solutions seems to be pretty random).

Sometimes, hobiwan's approach of selecting the most productive chain works great.

Code: Select all

 +-----------------------+
 | 9 5 6 | . . . | . 3 1 |
 | 7 3 . | . . . | . . 5 |
 | 2 . . | 6 . . | . 7 . |
 |-------+-------+-------|
 | . . 5 | 3 . . | . . 8 |
 | . . . | . . 8 | 3 6 . |
 | . . . | . 7 . | . . 9 |
 |-------+-------+-------|
 | . . . | . 1 . | . . . |
 | 5 . 7 | . 6 . | . 1 . |
 | 1 8 . | 7 . 3 | . . . |
 +-----------------------+


Code: Select all

 SSTS, UR [r79c38] => [r79c8]<>2 (not necessary), PM
 +--------------------------------------------------------------+
 |  9     5     6     |  24    248   7     |  28    3     1     |
 |  7     3     4     |  129   289   129   |  6     28    5     |
 |  2     1     8     |  6     3     5     |  9     7     4     |
 |--------------------+--------------------+--------------------|
 |  6     79    5     |  3     249   1249  |  147   24    8     |
 |  4     79    1     |  259   259   8     |  3     6     27    |
 |  8     2     3     |  14    7     6     |  145   45    9     |
 |--------------------+--------------------+--------------------|
 |  3     6     29    |  2458  1     24    |  457   4589  27    |
 |  5     4     7     |  289   6     29    |  28    1     3     |
 |  1     8     29    |  7     245   3     |  45    459   6     |
 +--------------------------------------------------------------+


Here the elimination [r2c6]<>9 jumps out from the chain list.

Code: Select all

{  1}  2r2c6  4r1c4  1r6c4  1r2c6                             [chain__9] <> 2 [r2c6]
{  1}  2r4c6  2r5c9  7r4c7  1r4c6                             [chain__9] <> 2 [r4c6]
{  6} -4r4c8  2r4c8  2r7c9  4r7c6                             [RemPairs] <> 4 [r4c6],[r7c8]
{  6}  2r7c3  2r8c7  8r7c8  9r7c3                             [chain__9] <> 2 [r7c3]
{  1} -2r7c9  2r5c9  4r4c8  4r6c4  2r1c4                      [chain__5] <> 2 [r7c4]
{  1}  2r5c4  2r4c8  8r2c8  8r7c4  5r5c4                      [chain__9] <> 2 [r5c4]
{  1}  2r1c5  2r2c8  4r4c8  4r6c4  4r1c5                      [chain__9] <> 2 [r1c5]
{  1}  9r5c4  9r2c5  8r2c8  8r7c4  5r5c4                      [chain__9] <> 9 [r5c4]
{  4} -4r4c8  2r4c8  8r2c8  8r7c4  5r9c5  4r9c7               [chain__5] <> 4 [r4c7],[r6c7],
                                                                              [r7c8],[r9c8]
{ 51}  9r2c6  2r8c6  2r1c7  4r1c4  1r6c4  1r2c6               [chain__9] <> 9 [r2c6]
{  3} -4r7c6  4r4c6  2r4c8  8r2c8  8r7c4  5r9c5  4r9c7        [chain__5] <> 4 [r7c78],[r9c5]
{  1}  4r7c4  1r6c4  1r2c6  1r4c7  7r5c9  2r4c8  8r2c8  8r7c4 [chain__9] <> 4 [r7c4]
{  1}  5r9c8  4r6c8  1r6c4  1r4c7  7r5c9  2r7c9  2r9c3  9r9c8 [chain__9] <> 5 [r9c8]
____________________________________________________________________________________________


However, in my previous example, finding the most productive chain doesn't seem to help. It took two chains to eliminate two candidates in '1' to really make headway. Basically, for a candidate, eliminate it in N-1 cells in a unit where it appears N times. In my current set of 99 puzzles, I encounter this scenario several times.

An Example: http://forum.enjoysudoku.com/viewtopic.php?p=58349#p58349

[hobiwan]

Another difference to programs for me is, that both on paper and with (graphical) programs combinations of strong links (with different numbers) are much harder to see than (longer) bivalue chains.

My solver will only look for general chains when no XY-Chain is present. In fact for daj95376's grid my solver uses 4 XY-Chains, 1 W-Wing and 1 Finned X-Wing.

[hobiwan]

I'll try to follow the "look for singles" idea. Below are daj95376's chains (I put numbers to them to make it easier):

Code: Select all

 1: <> 8 [r7c4]
 2: <> 3 [r1c8],[r9c7]   => r9c8=3
 3: <> 6 [r1c56],[r2c7]  => r2c6=6, r7c5=6
 4: <> 9 [r7c4]
 5: <> 9 [r4c7]
 6: <> 9 [r7c5]
 7: <> 7 [r9c8]
 8: <> 9 [r1c9]
 9: <> 1 [r12c6],[r7c4]  => r2c6=6
10: <> 6 [r1c5],[r7c6]   => r7c5=6
11: <> 1 [r9c8]
12: <> 8 [r7c5]
13: <> 1 [r7c6]
14: <> 9 [r8c5]
15: <> 9 [r7c1]
16: <> 6 [r1c7]
17: <> 8 [r8c5]

Now I write down all chains (or combinations of chains), that lead to singles:

Code: Select all

 2:     r9c8=3
 3:     r2c6=6, r7c5=6
 9:     r2c6=6
10:     r7c5=6
 9+13:  r9c6=1
 3+16:  r1c9=6
 1+4+9: r7c4=7
 14+17: r8c5=5
 7+11:  r9c8=3

Let's do some tabling (propagating only singles):

Code: Select all

Original tables for eliminations:

r1c9=6 => r2c6=6, r7c5=6
r2c6=6 => r7c5=6
r7c4=7 => r9c6=1, r1c6=7
r7c5=6 => r8c5=5, r7c1=5
r8c5=5 => r7c1=5
r9c6=1 => r2c6=6
r9c8=3

Tabling results:

 r7c4=7 => r9c6=1, r1c6=7, r2c6=6, r7c5=6, r8c5=5, r7c1=5
 r1c9=6 => r2c6=6, r7c5=6, r8c5=5, r7c1=5
(r9c6=1 => r2c6=6, r7c5=6, r8c5=5, r7c1=5)
(r2c6=6 => r7c5=6, r8c5=5, r7c1=5)
(r7c5=6 => r8c5=5, r7c1=5)
(r8c5=5 => r7c1=5)
 r9c8=3

Now take the entry with the most dependent singles:
Chains 1+4+9 lead to 1 W-Wing (not singles, but close enough).

I have no idea whether this approach works with all grids but it should produce better results than just taking the first chain or the chain with the most eliminations. On the down side it takes a lot of work (certainly puts an end to trying to mimick a human solver).

[Draco]

...
I have no idea whether this approach works with all grids but it should produce better results than just taking the first chain or the chain with the most eliminations. On the down side it takes a lot of work (certainly puts an end to trying to mimick a human solver).

Oddly enough, I've been working out the details for a feature that does this sort of searching. Right now my solver simply takes the first forcing chain or net it finds, starting its search for shorter chains and expanding the "allowed size" if none are found (search space is all b/b locations). I reach better solutions when I try to force specific values (no surprise there).

So I've laid out the high-level details for searching through all chains within certain length parameters and "scoring" them based on how close they get the puzzle to Singles or SSTS. The scoring method will be critical, but with some tuning I ought to be able to find shorter solution paths at the expense of CPU cycles.

One could start a rather lively debate on whether this is brute force vs. usning a computer to mimic the thinking of a human solver looking for likely candidates to force and then for chains or nets that achieve that end. I'll leave that to others who enjoy religious discussions .

Cheers...

- drac

[Draco]

What is the point of comparing a solution found manually to those found with computer programs?

Firstly, I had no idea that Steve's solution was manual vs. produced with a solver.

That said, to improve my solver, I look for techniques that other solvers (manual or computer) use to arrive at solutions, and try to reasonably encode them when I notice distinct advantages over the solutions produced by my solver. Or just if it looks like a fun problem to attack.

For instance, to date I am undecided as to whether or not it is worth encoding the logic for finding mutant/kraken fish, XYZ-wings, Nice Loops and/or less complex forcing chains (vs. the chains/nets my solver produces at present).

I have, from solutions others have presented (be they manual or solver-produced) been working on improvements on how chains/nets are selected. In this case, descriptions of manual techniques for chains based on b/b plots (as well as preliminary designs -- not yet slated for coding -- on simpler forcing chains based on b/b plots) have led me to a design and initial implementation of said improvements.

Finally, I like to acknowledge the solutions others post to my queries, regardless of how they arrived at them, because I appreciate the time and effort they put forth to find and post their solutions.

Cheers...

- drac

[Draco]

Apart from attacking back doors one possibility I can think of is using steps first that lead to singles. Has anybody tried that already?

When looking for simpler solutions I often look at the last advanced step and try to reproduce the eliminations earlier in the solution path (often using a different technique). So trying to reproduce this behaviour is the other thing that comes in mind (but it would probably result in a significant amount of trial and error - and it could be just the same as looking for back doors which could be considered cheating).

I've made some progress on my "smarter" chain evaluator. As Danny noted earlier, sometimes it is a noticable help (e.g. solves with 3 or 4 instead of 7 or 8 passes). Sometimes it is little or not help; always, it is slower (sometimes 10x) because it examines every chain/network based on cascading singles starting from b/b locations (instead of just taking the first one it finds).

The algorighm looks first for the chain/net that most reduces puzzle complexity (using my own fairly general and reasonably quick measure). Then it looks for the one that produces the most cancellations, then chains before nets, then shortest overall length (fewest nodes). The "chains before nets" code is stubbed out right now.

I have a second method in mind which is similar to your "starting from singles" idea; it mimics what I do when I manually select targets in squares for cancellation (often one member of a b/b pair since that is an easy and obvious path to generating singles). Not terribly complex to write now that I've coded up the "best chains" method but still... gotta' do some Real Work sometime .

I wonder what would happen (other than running REALLY slow) if I combined the "best chains" and "target at singletons" codepaths (other than running REALLY slow)?

Cheers...

- drac

[daj95376]

My next level of headache!

Do you remember this PM and these two chains as part of my listing. Well, it turns out that the first chain is just a subset of the second chain. Every assignment and elimination that (reasonably) follow from the first chain is also present in the effect of the second chain.

Code: Select all

 +-----------------------------------------------------------------------+
 |  2      4      5      |  178    368    1678   |  1369   139    169    |
 |  13     9      8      |  5      2      16     |  136    4      7      |
 |  6      7      13     |  19     39     4      |  5      8      2      |
 |-----------------------+-----------------------+-----------------------|
 |  37     5      39     |  68     1      89     |  679    2      4      |
 |  17     6      19     |  2      4      5      |  8      79     3      |
 |  4      8      2      |  69     7      3      |  169    5      169    |
 |-----------------------+-----------------------+-----------------------|
 |  589    3      4      |  1789   5689   16789  |  2      179    189    |
 |  589    1      7      |  3      589    2      |  4      6      89     |
 |  89     2      6      |  4      89     17     |  137    137    5      |
 +-----------------------------------------------------------------------+

{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6         [chain__5] <> 6 [r1c56],[r2c7]
{ 15} -1r3c4  1r3c3  1r5c1  7r4c1  7r9c7  1r9c6  [chain__5] <> 1 [r12c6],[r7c4]
_______________________________________________________________________________


I ran across this gem of information after tracking down why my solver would drop chains when I enabled a section of new code.

Code: Select all

 effect of   <> 6 [r1c56],[r2c7]
 *-----------------------------------------------------------*
 | 2     4     5     | 178   38    178   | 1369  139   169   |
 | 13    9     8     | 5     2     6     | 13    4     7     |
 | 6     7     13    | 19    39    4     | 5     8     2     |
 |-------------------+-------------------+-------------------|
 | 37    5     39    | 68    1     89    | 679   2     4     |
 | 17    6     19    | 2     4     5     | 8     79    3     |
 | 4     8     2     | 69    7     3     | 169   5     169   |
 |-------------------+-------------------+-------------------|
 | 5     3     4     | 1789  6     1789  | 2     179   189   |
 | 89    1     7     | 3     5     2     | 4     6     89    |
 | 89    2     6     | 4     89    17    | 137   137   5     |
 *-----------------------------------------------------------*


Code: Select all

 effect of   <> 1 [r12c6],[r7c4]
 *-----------------------------------------------------------*
 | 2     4     5     | 178   38    *78   | 1369  139   169   |
 | 13    9     8     | 5     2     6     | 13    4     7     |
 | 6     7     13    | 19    39    4     | 5     8     2     |
 |-------------------+-------------------+-------------------|
 | 37    5     39    | 68    1     89    | 679   2     4     |
 | 17    6     19    | 2     4     5     | 8     79    3     |
 | 4     8     2     | 69    7     3     | 169   5     169   |
 |-------------------+-------------------+-------------------|
 | 5     3     4     | *789  6     1789  | 2     179   189   |
 | 89    1     7     | 3     5     2     | 4     6     89    |
 | 89    2     6     | 4     89    17    | 137   137   5     |
 *-----------------------------------------------------------*


[Draco]

Here's one that my solver rates as pretty hard, SE gives a 7.3 and both need several forcing chains (16 if I recall SE's list correctly, 20 for my solver if I let it go after short chains first, which I tend to do) to solve.

Any one able to bring some brevity to this situation, please chime in! ...

Code: Select all

.......91..48.1....6...534....4...89....5....29...6....872...3....6.75..62.......

378   357  235  | 37   23467 234  | 2678  9    1   
379   37   4    | 8    23679 1    | 267   2567 2567
1789  6    1289 | 79   279   5    | 3     4    278
----------------+-----------------+----------------
137   1357 1356 | 4    237   23   | 1267  8    9   
13478 1347 1368 | 1379 5     2389 | 1267  1267 2367
2     9    138  | 137  378   6    | 147   157  3457
----------------+-----------------+----------------
5     8    7    | 2    149   49   | 1469  3    46 
1349  134  139  | 6    1389  7    | 5     12   28 
6     2    139  | 5    13489 3489 | 14789 17   478


As I mentioned in my reply to hobiwan earlier in this thread, I've been working on a chain search algorithm that would produce better forcing or contradictions chains/nets. What I've got is slow and, in limited testing, always at least as well or better than my old method. It can also be MUCH slower. In the case of the puzzle above, it reduced the # of chains needed from 16 or so to 2!

----- First Chain ------
r1c1=8 r3c9=8 r8c9=2 r8c5=8
r1c1=8 r9c7=8 r7c7=9
r9c7=8 [r9c6<>8] r5c6=8
------ Second Chain ------
r1c7=8 r1c5=6 r1c6=4 r7c6=9
------ Cancellations ------
r5c6<>9, r7c5<>9, r8c5<>9
------ Chain Ends ------

STSS then

------ First Chain ------
r3c3=1 r9c3=3 r6c3=8 r5c6=8
r3c3=1 r8c3=9
r3c3=1 r1c3=2 r1c6=4
r9c3=3 [r8c1<>3 r8c2<>3 r8c3<>3] r8c5=3
r6c3=8 [r6c5<>8] + r8c5=3 [r6c5<>3] = r6c5=7
r8c5=3 [r4c5<>3] + r6c5=7 [r4c5<>7] = r4c5=2
[r1c6<>2 + r5c6<>2] = r4c6=2
------ Cancellations ------
r3c3<>1

STSS will solve. More work to do on this new search code, but it is looking very promising!

Cheers...

- drac