The New Sudoku Players' Forum

[merallas]

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

[QBasicMac]

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


[udosuk]

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

[daj95376]

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


[Carcul]

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

[merallas]

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

[GoSimon]

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!

[daj95376]

GoSimon, I believe you may have posted the wrong puzzle. The most complicated operation in this puzzle is resolving Naked Triples.

[merallas]

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.

[RW]

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

[merallas]

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

[Havard]

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

[GoSimon]

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.

[ronk]

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.

[RW]

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.

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

RW