The New Sudoku Players' Forum

[pjb]

Solutions to hard puzzles, eg easter monster, that I've seen are often obscure and useful only to that puzzle. What I'm proposing is a general method that can be used to solve any puzzle. The method can be applied to single digits, units, or patterns, and the latter is most powerful. The method relies on testing each possible pattern for a digit to see if it leads to a contradiction.

I first encountered the concept of eliminating by contradiction when I studied discontinuous nice loops, a seemilgly well accepted technique. I then realized that solvers such as SE relied heavily on contradiction when getting into the 9.5+ range. However, there is no logical reason why one should be confined to testing single digits for contradictions - why not test a unit or pattern? The methodology for identifying contradictions is fully explained at my online solver (see below)

For a chosen digit, all patterns are generated, and one pattern at a time, the 9 members of the pattern are postulated to be true. A forcing net is then generated, and if a contradiction results then that pattern is removed from the total. After all patterns have been tested, the remainder are transformed into a 9x9 grid and compared to the actual Sudoku. If there is a cell that all remaining patterns include, then that cell can have the value of the chosen digit. If there are cell(s) which none of the remaining patterns pass through, then the digit can be removed from these cell(s).

The Killer Method
If the above is not enough (as is the case in the very hardest puzzles) some something extra is needed. If one generates an array of all instances of a digit occurring twice in a unit (ie pairs), then one can make one of the pair true, then a pattern to be true, and see if there is a contradiction. If there is, then can make the other of the pair true, and the same pattern true, and if there is again a contradiction, then the pattern must be false and can be eliminated. This is because one of the pair has to be true, so the contradiction must be due to the pattern. This process can be enabled for triples and even quads. (in very hard puzzles there aren’t many pairs, so triples are initially needed). The progress of this method is fully outputted into a text box so the logic can be examined.

This new method, along with the similar one for single digits and units can be tested on my new online javascript solver at http://www.philsfolly.net.au

[eleven]

Hi,

can you try this puzzle please (from hardest thread)?

Code: Select all

1.......9.5.1...3...8..34...1.5.......9..8..2....6..7.3....4..8..2.......8..7..6.

I dont know, how to use your solver for it, get "script not responding" or other strange things.

If i understood your method, it is new, but not recommendable for human players.
In general, you can start with any set of assumptions, where one of them must be true, and look what happens. A contradiction shows the assumption is false, a common output for all must be true. E.g. when you try all combinations of candidates in 3 cells of a unit (for all triple cells in all units), you can solve all or at least almost all puzzles.
The problem is just, that such deductions become so complex for hard puzzles, that no one wants to read it.

[tarek]

Hi pjb,

Over the past 6+ years there had been several solvers attempting solving these hardest puzzles (& rate them) using several models one of them being elimination by contradiction.

I can't draw exact similarities or differences but whast you describe is close IIRC to what Arto Inkala describes in his Universal solver. You would also probably find "Ravel's minimum step" travelling closely.

Most of these will be either documented or have links in both threads (old & new) that deal with "Hardest Sudokus" on this forum.

Tarek

[pjb]

Hi,

can you try this puzzle please (from hardest thread)?

Code: Select all

1.......9.5.1...3...8..34...1.5.......9..8..2....6..7.3....4..8..2.......8..7..6.

I dont know, how to use your solver for it, get "script not responding" or other strange things.

If i understood your method, it is new, but not recommendable for human players.
In general, you can start with any set of assumptions, where one of them must be true, and look what happens. A contradiction shows the assumption is false, a common output for all must be true. E.g. when you try all combinations of candidates in 3 cells of a unit (for all triple cells in all units), you can solve all or at least almost all puzzles.
The problem is just, that such deductions become so complex for hard puzzles, that no one wants to read it.

1. Thank you for revealing a problem - When I copied and pasted the above string I found it had 83 characters so wouldn't import. I've now inserted code to trap this problem. Having reduced it to 81, It solved in 25 minutes using the patterns method, only needing to use 1 through 7.

2. Are the nested chains used for hard puzzles in Sudoku Explainer recommendable for human players? I certainly struggled trying to make sense of it. I'd love you to show me a method that solves the hardest puzzle that is 'recommendable' for human players.

3. Compared to other methods I've seen that solve these kinds of puzzles, the deductions are at least equally complex or more so.

[tarek]

I found the original threads by Arto Inkala which happen to be seperate from the "Hardest sudokus" thread.

2 similar threads: one here and the other on the Programmers forum.

http://forum.enjoysudoku.com/airoot-universal-solving-technique-t4870.html

http://www.setbb.com/sudoku/viewtopic.php?p=6831&mforum=sudoku#6831

It was effictive in filtering out one the hardest sudokus at that time which got media attention.

tarek

[eleven]

Having reduced it to 81, It solved in 25 minutes using the patterns method, only needing to use 1 through 7.

Thanks for the information. It resists champagne's main methods and my 6-unit tries, but doesnt seem to be extremely hard for (though complex) contradiction moves.

2. Are the nested chains used for hard puzzles in Sudoku Explainer recommendable for human players?

Explainer's not. But e.g. ttt has found very nice solutions for extremely hard puzzles. And dont forget the SK loop.

3. Compared to other methods I've seen that solve these kinds of puzzles, the deductions are at least equally complex or more so.

Generally i agree, but there are at least exceptions. In fact i think, that you could name any puzzle, and it would be possible to give a readable solution for it. Of course with the help of computer tools, but no known program could do it automatically.

[pjb]

I found the original threads by Arto Inkala which happen to be seperate from the "Hardest sudokus" thread.

2 similar threads: one here and the other on the Programmers forum.

http://forum.enjoysudoku.com/airoot-universal-solving-technique-t4870.html

http://www.setbb.com/sudoku/viewtopic.php?p=6831&mforum=sudoku#6831

It was effictive in filtering out one the hardest sudokus at that time which got media attention.

tarek

Thank you for that
It may be similar but you have to admit it's hard to figue out precisely what AIroot method involves. What I offer here is fully explained, and if that is not enough feel free to get the js files and look at my JavaScript. However, my code isn't pretty so apologies in advance.

Pjb

[tarek]

Thank you for that
It may be similar but you have to admit it's hard to figue out precisely what AIroot method involves. What I offer here is fully explained, and if that is not enough feel free to get the js files and look at my JavaScript. However, my code isn't pretty so apologies in advance.

You described it well, and you also made the solver available for use and evaluation. Well done

My interest and possibly others is in your solver's potential as a "Hard Puzzle" rating program. I mentioned Artoi's threads to interest you in that.

From my experience with JavaScript: it is toooo slow so you can understand the problem when you attempt to filter out the hardest puzzle out of a 1,000,000

The Multiple solution conflict is also interesting as a future addition.

Tarek