Finally A Way To Solve All Sudoku Puzzles!!

Post the puzzle or solving technique that's causing you trouble and someone will help

Postby merallas » Wed Nov 15, 2006 1:20 am

udosuk wrote:Merallas, check out this thread, if your program could solve the bulk of those puzzles I'd say it's very close to being complete...:)


Hello Udosuk,

Thanks for the link to difficult sudokus. However, my program could not be impressed after solving several puzzles. The most complicated one the program has met up to now is this one from http://diuf.unifr.ch/people/juillera/Sudoku/InterestingSudokus.html (first one in "Beyond Forcing Chains")

708000300
000201000
500000000
040000026
300080000
000100090
090600004
000070500
000000000

I am wondering what the opinion is of the specialist about this sudoku.

regards,
Merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby QBasicMac » Wed Nov 15, 2006 1:45 am

merallas wrote:I am wondering what the opinion is ... about this sudoku.


Not worse than the other one. Level 8 T&E.

Mac

Code: Select all
728  946  315
934  251  678
516  738  249

147  593  826
369  482  157
852  167  493

293  615  784
481  379  562
675  824  931
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby udosuk » Wed Nov 15, 2006 2:16 am

Merallas, these 10 puzzles are considered the hardest for now:
Code: Select all
..1..2....3..4..5.6..7..8....6.....7.1.....3.9.....6....7..1..8.4..3..2....5..9..
.6.9....35....4.2.....8.4..8......5...3...7...9......1..1.5.....7.3....99....2.4.
..1..2....3..4..5.6..7..8....6.....7.1.....2.9.....5....3..1..6.4..5..3....8..9..
1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..
..1..2....3..4..5.6..7..8....8.....7.1.....4.9.....5....4..1..8.2..3..1....6..9..
..1..2....3..4..5.5..6..7....7.....6.1.....2.8.....4....6..1..9.4..3..1....7..8..
..1..2....3..4..5.6..7..8....8.....7.1.....3.9.....5....2..1..6.4..5..2....6..9..
..1..2....3..4..1.5..6..7....7.....6.1.....3.8.....9....2..7..1.4..5..2....9..8..
..1..2....3..4..5.5..6..7....7.....6.1.....3.8.....9....9..3..2.2..1..4....7..8..
..1..2....3..4..5.5..6..3....7.....6.8.....4.2.....1....6..9..7.4..7..8....5..9..

So I take it your program can tackle them without any problems, but has trouble with the "Beyond Forcing Chains" ones, which could be solved fairly easily by other programs (e.g. Sudoku Explainer)? Interesting... I'd say it's likely that your program has a stronger brute force engine but weaker logical techniques implemented... But it's just speculation...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby daj95376 » Wed Nov 15, 2006 6:35 am

After SSTS in the puzzle presented by merallas, the elimination [r9c2]<>2 exists. However, I can only find a complicated explanation. Is there a simple explanation? (Unfortunately, the elimination doesn't seem to be beneficial.)

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    135678-2 1234567  | 34589    12459    234589   | 12679    13678    12789    |
 *--------------------------------------------------------------------------------------*
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Carcul » Wed Nov 15, 2006 10:14 am

Merallas wrote:Thanks for the link to difficult sudokus. However, my program could not be impressed after solving several puzzles. The most complicated one the program has met up to now is this one from http://diuf.unifr.ch/people/juillera/Sudoku/InterestingSudokus.html (first one in "Beyond Forcing Chains") (...) I am wondering what the opinion is of the specialist about this sudoku.


I am not the specialist you are referring to, but here is my opinion:

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 |
 *--------------------------------------------------------------------------------*

1. [r2c5]=5|7=[r2c7](-7-[r7c7])-7-[r456c7]=7=[r5c89]-7-[r5c2]=7|8=
=[r8c2]-8-[r7c1]=8|5=[r7c5]-5-[r2c5],

which implies: r9c7<>7; r5c346<>7; r8c1/r9c12<>8; r1469c5<>5.

2. {ATILA(5): r4c3|r4c4|r6c6|r7c6|r7c3|(r9c3)}, => r9c3=5 and the puzzle is solved.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby merallas » Wed Nov 15, 2006 3:43 pm

udosuk wrote:Merallas, these 10 puzzles are considered the hardest for now


So I take it your program can tackle them without any problems, but has trouble with the "Beyond Forcing Chains" ones, which could be solved fairly easily by other programs (e.g. Sudoku Explainer)? Interesting... I'd say it's likely that your program has a stronger brute force engine but weaker logical techniques implemented... But it's just speculation...:)



Thanks for supplying the 10 hardest puzzles. My program can solve them without using the most powerful option. Apparently I have implemented the killer routine for only one sudoku.
You are right that the program does not contain much logical techniques. My goal was to make a program which can solve any sudoku within a reasonable time interval. Only three basic logical methods are used (naked single, single cell and naked pair). Then gambling and finally systematical trials. Since I have more fun in making programs than in solving sudokus I will see in the future if more inteligence can be implemented.

Merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby GoSimon » Sun Nov 19, 2006 10:42 pm

Here is another impossible puzzle, i.e., trial and error is required.

Code: Select all
+-------+-------+-------+
| 2 3 . | . . 6 | . . . |
| 4 . . | . . 9 | . . . |
| . . . | . 4 . | 1 . . |
+-------+-------+-------+
| . . . | 2 . . | . 1 7 |
| . . 7 | . . . | 9 . . |
| 8 1 . | . . 3 | . . . |
+-------+-------+-------+
| . . 6 | . 8 . | . . . |
| . . . | 4 . . | . . 3 |
| . . . | 5 . . | . 7 8 |
+-------+-------+-------+


The Exhaustive Matrix Generator <http://www.hyperinfo.ca/Sudoku/> helps, but guessing is still necessary, except for "1" at (column 9, row 7).

Please let me know if you can solve it without having to guess!
Last edited by GoSimon on Sun Nov 19, 2006 7:16 pm, edited 1 time in total.
GoSimon
 
Posts: 10
Joined: 11 November 2006

Postby daj95376 » Sun Nov 19, 2006 11:10 pm

GoSimon, I believe you may have posted the wrong puzzle. The most complicated operation in this puzzle is resolving Naked Triples.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby merallas » Sun Nov 19, 2006 11:18 pm

GoSimon wrote:Here is another impossible puzzle, i.e., trial and error is required.
.......
Please let me know if you can solve it without having to guess!


Hi GoSimon,

My program needs a guess. Standard the guess routine generates two extra digits, but in this case one extra digit would be sufficient. So find the 2 and the puzzle can be solved with the three basic techniques (naked single, single cell and naked pair).

merallas

When I was composing this message a remark about naked triples was posted. I did not program that method.
Last edited by merallas on Sun Nov 19, 2006 7:26 pm, edited 1 time in total.
merallas
 
Posts: 39
Joined: 26 September 2006

Postby RW » Sun Nov 19, 2006 11:22 pm

merallas wrote:So find the 2 and the puzzle can be solved with the three basic techniques (naked single, single cell and naked pair).
Interesting definition of "basic techniques"... Why isn't the naked triplet included, that avoids the guess?

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

Postby merallas » Sun Nov 19, 2006 11:34 pm

RW wrote:
merallas wrote:So find the 2 and the puzzle can be solved with the three basic techniques (naked single, single cell and naked pair).
Interesting definition of "basic techniques"... Why isn't the naked triplet included, that avoids the guess?

RW


I call it basic techniques because they are rather easy to define in a computer program. Actually also naked triples could be programmed quite easy, but when I was testing the program I found very few cases of naked triples in unsolved puzzles. The techniques which have to be used after these four are very complex to implement in a program; at least for me.


merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby Havard » Sun Nov 19, 2006 11:39 pm

Here is the naked triple in question, allows a lot of eliminations!:)

Code: Select all
 2     3      1589 |  178   157    6    |  4578    458     459 
 4     5678   158  |  1378  12357  9    |  235678  23568   256 
 5679  56789  589  |  378   4     -2578 |  1       23568   2569
-------------------+--------------------+-----------------------
 3569  4569   3459 |  2     59     458  |  34568   1       7   
 356   2456   7    |  168   15    -1458 |  9       234568  2456
 8     1      2459 |  679   579    3    |  2456    2456    2456
-------------------+--------------------+-----------------------
 3579  24579  6    | -379   8     *27   |  245     2459    1   
 1579  25789  2589 |  4    -12679 *127  |  256     2569    3   
 139   249    2349 |  5    -12369 *12   |  246     7       8   


Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby GoSimon » Mon Nov 20, 2006 8:07 am

The Triple technique worked OK. I can solve this 5-star (very difficult) puzzle without trial and error (guessing) whatsoever. Thank you all!

The Exhaustive Matrix Generator <http://www.hyperinfo.ca/Sudoku/> helps a lot indeed.
GoSimon
 
Posts: 10
Joined: 11 November 2006

Postby ronk » Mon Nov 20, 2006 12:30 pm

SarahJ wrote:Yes, I'll definitely solve it for you. I'm at work right now but will take a look when I get home tonite.:)

I certainly hope SarahJ got home safely.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Mon Nov 20, 2006 2:47 pm

GoSimon wrote:The Exhaustive Matrix Generator <http://www.hyperinfo.ca/Sudoku/> helps a lot indeed.

Sometimes I wish I also had no conscience, then I could also profit from selling all kinds of crap to the unknowing people on the internet. Seriously, someone is asking $9.99 for some access codes that lets you use a strange "matrix generator" that apparently cannot even find a naked triplet?! GoSimon, if you paid for that, I feel really sorry for you. There's lots of free programs available for download that are a lot more helpful than the one you mentioned.
ronk wrote:
SarahJ wrote:Yes, I'll definitely solve it for you. I'm at work right now but will take a look when I get home tonite.

I certainly hope SarahJ got home safely.

ronk, she hasn't even had 20 days to solve it yet, let's not pressure her...:D

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

PreviousNext

Return to Help with puzzles and solving techniques