The New Sudoku Players' Forum

[Cenoman]

...6..5...6..9..7...3..7..64..5..8...1..4..2...8..9..41..2..9......3..4...9..5..7

Code: Select all

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

Original here
This puzzle is rated 9.4 by S.E. Nevertheless, I found nothing efficient to attack it.

PM after basics and a finned X-wing (5)r678c2, r67c8 (eliminating 5r7c3)

Code: Select all

 +-------------------------+-----------------------+------------------------+
 |  2789    24789   1247   |  6      128   12348   |  5      1389   12389   |
 |  258     6       1245   |  1348   9     12348   |  1234   7      1238    |
 |  289     2489    3      |  148    5     7       |  124    189    6       |
 +-------------------------+-----------------------+------------------------+
 |  4       2379    267    |  5      126   1236    |  8      1369   139     |
 |  3569    1       56     |  378    4     368     |  367    2      359     |
 |  2356    235     8      |  137    126   9       |  1367   1356   4       |
 +-------------------------+-----------------------+------------------------+
 |  1       3458    46     |  2      7     468     |  9      3568   358     |
 |  25678   2578    2567   |  9      3     168     |  126    4      1258    |
 |  2368    2348    9      |  148    168   5       |  1236   1368   7       |
 +-------------------------+-----------------------+------------------------+


From here, I am stuck...

[SpAce]

I don't have the skills or the tools required to find anything, but I'm following with interest.

With basic settings Hodoku required a brute force move to crack this, and after some tweaking it needed a minimum of 15 Forcing Nets (+ 3 Forcing Chains + 11 simpler steps) on its own. By manually selecting the steps I got it down to 11 Forcing Nets (+ 6 simpler steps). So... looks pretty tough, unless someone can find a cool move to downgrade it.

[champagne]

Nothing special out of my solver(s), just a long sequence of boring dynamic chains.
Waiting for something original from one of our experts

My first dynamic chain shows that 2r2c1 comes quickly to a contradiction

[eleven]

A good candidate for a "sudoku for masochists" collection.
What you can find with big effort (and no fun), doesn't help you. What would help you, you can't find.
If you are interested in those ones, have a look at the patterns game. I guess that 8 of 10 ER 9+ puzzles have this property.

[Cenoman]

Thank you all three of you !

Thank you SpAce for running Hodoku.
Thank you champagne for running your solver(s)
Thank you eleven for running eleven's methods.

Actually, my own solver (full tagging method ) found similar results to what you say (including r2c1<>2 from a triple kraken) I had to turn on recursive kraken derivation and got a long sequence of kraken nets. I didn't trust these results.
I was just hoping to have missed some trick.
The shape of the puzzle suggest that it might have been extracted from the patterns game...

A good candidate for a "sudoku for masochists" collection.
[...] If you are interested in those ones, have a look at the patterns game. I guess that 8 of 10 ER 9+ puzzles have this property.

I suppose that these ER 9+ puzzles of the "sudoku for masochists" collection are what have been called the "grey zone" (between hard and hardest ?). I have seen some threads about that.

Eventually, players on Andrew's site have been right to use T&E to solve it.
My own conclusions are:
1) experts are not masochist (this is rather good news...)
2) I should trust more my solver (it is masochist enough to solve that and this is also good news...)

Thanks !

[SpAce]

I suppose that these ER 9+ puzzles of the "sudoku for masochists" collection are what have been called the "grey zone" (between hard and hardest ?). I have seen some threads about that.

Eventually, players on Andrew's site have been right to use T&E to solve it.

This leads back to the question I asked last time when you posted an "unsolvable". What would be the best strategy when you've run out of normal tactics and your life depends on solving the puzzle? Obviously some form of T&E must be used then, but how do you employ that efficiently and effectively in manual solving? As far as I know, those kinds of strategies and tactics aren't really covered anywhere (here at least) because no respectable solver admits to using them (here at least). That's a very limited view, I think, because it leaves most of the grey+ zone puzzles unsolvable by hand -- even for top experts knowing all the exotic techniques, if eleven's estimates are correct.

To me it seems a bit weird point of view that solving methods should be limited to elegant ones only, if it means that only complying puzzles can be solved at all. As a martial arts analogy, it's kind of like practicing aikido etc which may look nice on demonstrations but depend on the opponent voluntarily falling down on cue. If you want to have an actual chance in a street fight or in the MMA cage, you need very different skills.

So, how should we defend ourselves if attacked by a non-cooperating opponent like this puzzle (not to even mention harder ones)? I think (hope) there must be some way to kick them in the groin, so to speak, to give our normal techniques a chance to work. How do you find those kinds of weak spots to attack, and how do you actually employ T&E? Bivalue and bilocation links are obvious first targets, but what if they're scarce and the few are just too well-armored? Do you then try to attack candidates that would produce new strong links? How would you limit your technique set in the trials to keep the process efficient? (The simpler the techniques, the more nested T&E required, I would presume.)

In this particular case, it seems that even a pretty naive T&E strategy would crack the puzzle relatively easily, even on pencil&paper, because the obvious targets aren't that well-armored (no nested T&E needed). It would take time, however, because the trial paths aren't trivial or short with my chosen technique set, but they'd be doable nevertheless. I guess some T&E variants only accept very simple techniques in the trial paths, but I chose the cut-off point at any patterns that I could probably find manually in a reasonable time (basically all AICs but not krakens). That choice would make testing individual branches much slower, but presumably there would be fewer branches to test and they'd yield better results if successful (i.e. a contradiction is found).

Here's what I'd do (or did, but with a software helper to run the trials with the mentioned technique set). The two bivalue cells are the most obvious targets, especially since they have a chance to solve each other, so I'd start with them. I actually started with the (56)r5c3 but it was quickly established that it would yield nothing without nesting. The (46)r7c3 worked, however. (Basic steps omitted below.)

1a) Try 4r7c3: 1 x AIC -> dead end.
1b) Try 6r7c3:

13 x AIC
1 x AIC-Loop
1 x Kite
1 x Grouped Skyscraper
1 x X-Wing
1 x WXYZ-Wing
2 x Hidden Rectangle
-> contradiction => -6 r7c3 => 4r7c3

This was the most demanding set of trial steps because of the sheer number of them, but none of them were individually hard.
2) Solve with 4r7c3.

1 x AIC
3a) Try 6r5c3: 1 x Hidden Rectangle -> dead end.
3b) Try 5r5c3:

1 x Grouped Kite
1 x ER
-> contradiction => -5 r5c3 => 6r5c3
4) Solve with 6r5c3:

1 x Hidden Rectangle.
5a) Try 3r5c6: -> solution (not really what we want in T&E)
5b) Try 8r5c6:

6 x AIC
1 x X-Wing
-> contradiction => -8 r5c6 => 3r5c6
6) Solve with 3r5c6:

2 x AIC
1 x XY-Chain
1 x X-Wing
1 x XY-Wing
-> stte

So, in this particular case that T&E strategy would have worked without nesting or a lot of frustrating dead-end trials. However, I bet it's usually not this "easy". Can anyone recommend a better T&E strategy for manual solving?

[RSW]

If you're going to use T&E then I don't see any particular problem in deciding how to go about it. Once you've exhausted all logical solution techniques, just pick a cell with the fewest candidates and then continue on under the assumption that you've made the correct choice (using the full set of logical techniques again) until one of the following happens:
1. Puzzle solved. You're done!
2. Reached a contradiction, so go back to the last cell that you guessed and try a different guess.
3. Reached another impasse without solving the puzzle. So, guess the value of another cell and continue.

That's essentially the strategy of my solver, and here is the verbose listing of its solution of #324:
(Trial & Error steps are preceded with '##")

Solver Output: Show

* Cell r3c5 is the only valid location in column 5 for digit 5
- Removing candidate 5 from r3c1 r3c2
* Cell r8c4 is the only valid location in row 8 for digit 9
* Cell r7c5 is the only valid location in block 8 for digit 7
- Removing candidate 7 from r7c2 r7c3 r4c5 r6c5
Box/Line: In row 4, the only valid positions for digit 7 are r4c2 r4c3
- Removing candidate 7 from block 4 r5c1 r5c3 r6c1 r6c2
## All Logic Strategies exhausted at top level. Starting new branch level 1.
## Choosing cell having fewest candidates: r5c3: [5,6]
## Level 1, trying r5c3=5: Leads to contradiction. Backtracking...
## Level 1, trying r5c3=6: Leads to solution.
* Cell r5c3=6 by trial & error
Sparse Subset: In row 5, the digits 3 7 8 must go in cells r5c4 r5c6 r5c7 (unspecified order)
These digits can then be eliminated from the other cells in row 5
- Removing candidate(s) 3 from cell r5c1
- Removing candidate(s) 3 from cell r5c9
## All Logic Strategies exhausted at level 1. Starting new branch level 2.
## Choosing cell having fewest candidates: r5c6: [3,8]
## Level 2, trying r5c6=3: Leads to solution.
* Cell r5c6=3 by trial & error
* Cell r5c7=7 by simple elimination.
* Cell r5c4=8 by simple elimination.
* Cell r2c4 is the only valid location in column 4 for digit 3
- Removing candidate 3 from r2c7 r2c9
* Cell r6c4 is the only valid location in row 6 for digit 7
X-wing: In columns 1 & 7, digit 3 must go in row 6 or 9
Therefore candidate 3 can be removed from all other cells in rows 6 & 9
Removing candidate 3 from r6c2 r9c2 r6c8 r9c8
## All Logic Strategies exhausted at level 2. Starting new branch level 3.
## Choosing cell having fewest candidates: r5c1: [5,9]
## Level 3, trying r5c1=5: Leads to contradiction. Backtracking...
## Level 3, trying r5c1=9: Leads to solution.
* Cell r5c1=9 by trial & error
* Cell r5c9=5 by simple elimination.
* Cell r7c8 is the only valid location in column 8 for digit 5
- Removing candidate 5 from r7c2 r7c3
* Cell r7c3 now has only one possible value: 4
- Removing candidate 4 from r7c2 r7c6 r1c3 r2c3 r9c2
* Cell r7c6 is the only valid location in row 7 for digit 6
- Removing candidate 6 from r4c6 r8c6 r9c5
* Cell r9c4 is the only valid location in row 9 for digit 4
- Removing candidate 4 from r3c4
* Cell r3c4 now has only one possible value: 1
- Removing candidate 1 from r3c7 r3c8 r1c5 r1c6 r2c6
Sparse Subset: In column 2, the digits 2 3 5 7 8 must go in cells r4c2 r6c2 r7c2 r8c2 r9c2 (unspecified order)
These digits can then be eliminated from the other cells in column 2
- Removing candidate(s) 2 7 8 from cell r1c2
- Removing candidate(s) 2 8 from cell r3c2
In column 2, the only valid positions for digit 8 are r7c2 r8c2 r9c2
- Removing candidate 8 from block 7 r8c1 r9c1
## All Logic Strategies exhausted at level 3. Starting new branch level 4.
## Choosing cell having fewest candidates: r9c5: [1,8]
## Level 4, trying r9c5=1: Leads to solution.
* Cell r9c5=1 by trial & error
* Cell r8c6=8 by simple elimination.
* Cell r4c6 is the only valid location in column 6 for digit 1
- Removing candidate 1 from r4c8 r4c9
* Cell r1c5 is the only valid location in column 5 for digit 8
- Removing candidate 8 from r1c1 r1c8 r1c9
## All Logic Strategies exhausted at level 4. Starting new branch level 5.
## Choosing cell having fewest candidates: r1c1: [2,7]
## Level 5, trying r1c1=2: Leads to contradiction. Backtracking...
## Level 5, trying r1c1=7: Leads to solution.
* Cell r1c1=7 by trial & error
## All Logic Strategies exhausted at level 5. Starting new branch level 6.
## Choosing cell having fewest candidates: r1c2: [4,9]
## Level 6, trying r1c2=4: Leads to contradiction. Backtracking...
## Level 6, trying r1c2=9: Leads to solution.
* Cell r1c2=9 by trial & error
* Cell r3c2=4 by simple elimination.
* Cell r3c7=2 by simple elimination.
* Cell r3c1=8 by simple elimination.
* Cell r3c8=9 by simple elimination.
* Cell r8c9 is the only valid location in column 9 for digit 2
- Removing candidate 2 from r8c1 r8c2 r8c3
* Cell r1c6 is the only valid location in row 1 for digit 4
- Removing candidate 4 from r2c6
* Cell r2c6 now has only one possible value: 2
- Removing candidate 2 from r2c1 r2c3
* Cell r2c7 is the only valid location in row 2 for digit 4
* Cell r9c8 is the only valid location in column 8 for digit 8
- Removing candidate 8 from r9c2 r7c9
* Cell r9c2 now has only one possible value: 2
- Removing candidate 2 from r9c1 r4c2 r6c2
* Cell r6c2 now has only one possible value: 5
- Removing candidate 5 from r6c1 r8c2
* Cell r8c2 now has only one possible value: 7
- Removing candidate 7 from r8c3 r4c2
* Cell r8c3 now has only one possible value: 5
- Removing candidate 5 from r8c1 r2c3
* Cell r8c1 now has only one possible value: 6
- Removing candidate 6 from r8c7 r9c1
* Cell r8c7 now has only one possible value: 1
- Removing candidate 1 from r6c7
* Cell r9c1 now has only one possible value: 3
- Removing candidate 3 from r9c7 r6c1 r7c2
* Cell r9c7 now has only one possible value: 6
- Removing candidate 6 from r6c7
* Cell r6c7 now has only one possible value: 3
- Removing candidate 3 from r4c8 r4c9
* Cell r4c8 now has only one possible value: 6
- Removing candidate 6 from r4c5 r6c8
* Cell r4c5 now has only one possible value: 2
- Removing candidate 2 from r4c3 r6c5
* Cell r4c3 now has only one possible value: 7
* Cell r6c5 now has only one possible value: 6
* Cell r6c8 now has only one possible value: 1
- Removing candidate 1 from r1c8
* Cell r1c8 now has only one possible value: 3
- Removing candidate 3 from r1c9
* Cell r1c9 now has only one possible value: 1
- Removing candidate 1 from r1c3 r2c9
* Cell r1c3 now has only one possible value: 2
* Cell r2c9 now has only one possible value: 8
- Removing candidate 8 from r2c1
* Cell r2c1 now has only one possible value: 5
* Cell r4c9 now has only one possible value: 9
* Cell r6c1 now has only one possible value: 2
* Cell r7c2 now has only one possible value: 8
* Cell r2c3 now has only one possible value: 1
* Cell r4c2 now has only one possible value: 3
* Cell r7c9 now has only one possible value: 3

Summary (Combining Trial & Error with Logic Strategies):

792 684 531
561 392 478
843 157 296

437 521 869
916 843 725
258 769 314

184 276 953
675 938 142
329 415 687

Final Cell Values by Solve Order:

Initial (Clue) Values:
r1c4=6, r1c7=5, r2c2=6, r2c5=9, r2c8=7, r3c3=3, r3c6=7, r3c9=6, r4c1=4, r4c4=5, r4c7=8, r5c2=1, r5c5=4, r5c8=2, r6c3=8, r6c6=9, r6c9=4, r7c1=1, r7c4=2, r7c7=9, r8c5=3, r8c8=4, r9c3=9, r9c6=5, r9c9=7
Solved:
r3c5=5, r8c4=9, r7c5=7, *r5c3=6, *r5c6=3, r5c7=7, r5c4=8, r2c4=3, r6c4=7, *r5c1=9, r5c9=5, r7c8=5, r7c3=4, r7c6=6, r9c4=4, r3c4=1, *r9c5=1, r8c6=8, r4c6=1, r1c5=8, *r1c1=7, *r1c2=9, r3c2=4, r3c7=2, r3c1=8, r3c8=9, r8c9=2, r1c6=4, r2c6=2, r2c7=4, r9c8=8, r9c2=2, r6c2=5, r8c2=7, r8c3=5, r8c1=6, r8c7=1, r9c1=3, r9c7=6, r6c7=3, r4c8=6, r4c5=2, r4c3=7, r6c5=6, r6c8=1, r1c8=3, r1c9=1, r1c3=2, r2c9=8, r2c1=5, r4c9=9, r6c1=2, r7c2=8, r2c3=1, r4c2=3, r7c9=3
* Asterisk indicates trial & error assignment used when all logic strategies have been exhausted.

Deepest recursion: 8
Total steps including dead branches: 2047
Total patterns searched including dead branches: 67
Total patterns found including dead branches: 8078
Total patterns found resulting in candidate elimination including dead branches: 171
Unlimited depth search Backdoor values: r5c3=6 r5c6=3 r5c1=9 r9c5=1 r1c1=7 r1c2=9

Total solution time: 495.20 milliseconds

[champagne]

If you're going to use T&E then I don't see any particular problem in deciding how to go about it. Once you've exhausted all logical solution techniques, just pick a cell with the fewest candidates and then continue on under the assumption that you've made the correct choice (using the full set of logical techniques again) until one of the following happens:
1. Puzzle solved. You're done!
2. Reached a contradiction, so go back to the last cell that you guessed and try a different guess.
3. Reached another impasse without solving the puzzle. So, guess the value of another cell and continue.

This is the task of any brute force solver, except that if you don't know if it is a sudoku, you can not stop before the second valid solution.
And having tested many ways to choose the next guess, I can say that the result (total number of guesses) can vary in a wide range. I have in mind a puzzle rating around 11.8 solved with 3 guesses reversely, being unlucky, you can make many guesses to solve an easy puzzle (depending on the rule applied after a guess).

[eleven]

Can anyone recommend a better T&E strategy for manual solving?

I don't think, that a manual solver would solve such puzzles more than once in the life. So this is a theoretical question.

I recently mentioned an alternative to trying a bivalue/bilocation candidate:
Choose a unit with few possible outcomes and try them one after the other.

Here you would take column 5 with 8 possibilities to place the 4 digits.
This way you have more tries, but normally you will get easier to a contradiction (or the solution), because you have set 4 numbers, not only one. This is the output of a solver for the different settings, the hardest techniques used are als-xz and a 6 cell binary loop.

1268 pair, x-wing, swordfish
1628 2 pairs, 2 x-wings, y-wing, 2 short chains (less 6 links)
2168 pair, x-wing
2618 pair, x-wing, 2 als-xz, 3 short chains (< 4 links)
8126 pair x-wing swordfish, short chain (5 links)
8216 swordfish, chain 4 links
8261 solution with 2 pairs, 2 triples, skyscraper, swordfish, 4 short chains < 6 links
8621 skyscraper, 3 short chains < 5 links, loop 6 cells

[champagne]

Can anyone recommend a better T&E strategy for manual solving?

I recently mentioned an alternative to trying a bivalue/bilocation candidate:
Choose a unit with few possible outcomes and try them one after the other.

As an outcome of my current work on the search of 17 clues, I experienced another way (in fact to produce Unavoidable sets, but I intend to test it beginning of 2019 in the brute force).

Take all possible solutions of one digit (use in priority digits with less remaining candidates)
then apply it (dynamically) to the next digit having the smallest count of candidates.

This is a very efficient way to produce UAs limited to 2 bands through the preferred process of mladen Dobrichev (solve n digits out of 9 and find all valid solutions). With an appropriate coding, this could be faster than the faster known brute force.

note : off topic, but in line with eleven's last post

[RSW]

This is the task of any brute force solver, except that if you don't know if it is a sudoku, you can not stop before the second valid solution.
And having tested many ways to choose the next guess, I can say that the result (total number of guesses) can vary in a wide range. I have in mind a puzzle rating around 11.8 solved with 3 guesses reversely, being unlucky, you can make many guesses to solve an easy puzzle (depending on the rule applied after a guess).

Not necessarily. It depends on how it's programmed. My solver will stop as soon as it finds one valid solution. I've also tested it on puzzles that have more than one solution. I can adjust the program logic so that it picks different guesses when it reaches an impasse. This may lead to different solutions if the puzzle has more than one, but in any case the solver will stop as soon as it finds one solution.

The trial & error mehod is of course non-deterministic in its solving time, because it depends on how many wrong guesses it makes before making the right ones. I've tested my solver on all of the archived Weekly Unsolvables. The fastest time is for #319 at 157 milliseconds, and the slowest is for #293 at 4.3 seconds. The average time for all of the archived unsolvables is 1.3 seconds.

Another thing that my solver does is search for the minimal backdoor cells. None of the archived Weekly Unsolvables require more than two to downgrade it to a simple logical solution.

[eleven]

My solver will stop as soon as it finds one valid solution.

It does not:

## Choosing cell having fewest candidates: r5c1: [5,9]
## Level 3, trying r5c1=5: Leads to contradiction. Backtracking...
## Level 3, trying r5c1=9: Leads to solution.
...

The only reason i see not to stop here is, that you want to show, that it is the only solution. (btw you can be sure, that i would stop here, if i had solved it manually that way.)
I am wondering how it can solve multi solution puzzles then. Maybe you count the solutions of a try ?

[RSW]

I don't understand what you're saying. r5c1=5 is not a valid solution. It leads to a contradiction. So, it then tries the other candidate r5c1=9. It just so happens that it was the last candidate in this case that led to solution.

However, If you consider the choices at level 2:

## All Logic Strategies exhausted at level 1. Starting new branch level 2.
## Choosing cell having fewest candidates: r5c6: [3,8]
## Level 2, trying r5c6=3: Leads to solution.
* Cell r5c6=3 by trial & error

You see that the first candidate selection r5c6=3 led to a solution, so it never bothered to try r5c6=8.

[eleven]

Ok, i misread your output.
So, why did you not stop, when you found, that there is a solution setting r5c6=3 ? Ah, i see you just spell it out in your trace (there is a solution), and then set r5c6 to 3 and list, how it is found. A bit strange.

[champagne]

The trial & error mehod is of course non-deterministic in its solving time, because it depends on how many wrong guesses it makes before making the right ones. I've tested my solver on all of the archived Weekly Unsolvables. The fastest time is for #319 at 157 milliseconds, and the slowest is for #293 at 4.3 seconds. The average time for all of the archived unsolvables is 1.3 seconds.
Another thing that my solver does is search for the minimal backdoor cells. None of the archived Weekly Unsolvables require more than two to downgrade it to a simple logical solution.

I was not at all discussing timings.
The brute force used to filter valid puzzles is in another dimension.

The version in use in my programs checks 22500 puzzles per second for the file of potential hardest (2 048 000 puzzles)
and 245000 puzzles per second for the file of 17 clues puzzles (49157 puzzles)

But this is without the search of back doors