| View previous topic :: View next topic |
| Author |
Message |
| crosspollinator
| | Joined: 24 Jun 2006 | | Posts: 4 | | : | |
Items |
|
 Posted: Fri Jun 30, 2006 4:01 am Post subject: Extremely hard puzzles thanks to a bug in my generator |
 |
|
This is one of the hardest puzzles that my puzzle generator has made so far. I believe that it can only be solved using trial and error or other brute force techniques. If someone finds a way to solve it without brute force, please let me know.
| Code: | . . . 2 . . . 9 .
. . 1 . 6 . 2 . .
. 3 . . . 1 . . 7
7 . . 8 . . . 4 .
. . 9 . 1 . 7 . .
. 6 . . . 7 . . 5
6 . . 4 . . . 3 .
. . 7 . 9 . 8 . .
. 2 . . . 8 . . .
|
| Code: | ...2...9...1.6.2...3...1..77..8...4...9.1.7...6...7..56..4...3...7.9.8...2...8...
|
I wrote a Sudoku generator last Winter. Most of the puzzles it generated were easy to medium, with a few hard ones. A co-worker recently asked me for more difficult puzzles, so I added a new algorithm to the solver in the generator. In one test of the new code, it generated 59 puzzles, which I fed into Sudoku Susser's AutoRate. There were two surprises. One was that 18 of the puzzles were not valid. They had multiple solutions. The other surprise was that some of the valid puzzles were far more difficult than I had expected based on the algorithm that I had written. I found and fixed the bug, and reran the test. With the bug fixed and the same input, it only found 7 puzzles that matched the template. All of them were valid, but there were no hard ones. So I put the bug back into the code, and found a simple heuristic to reject the multiple-solution puzzles using data that was already available in the generator. After those changes, the generator found 41 puzzles, all valid, with a very wide range of difficulty. Since then, I've generated about 700 puzzles using a variety of different templates, and validated them using Sudoku Susser. The generator hasn't produced any more invalid puzzles, and it has produced many very difficult puzzles. I think I've figured out why the bug allows the generator to find more puzzles and harder puzzles, and I'm thinking about how to turn it into a proper algorithm.
Jim Turner |
|
| Back to top |
|
 |
| shar
| | Joined: 16 Apr 2008 | | Posts: 2 | | : | |
Items |
|
| Posted: Wed Apr 16, 2008 8:07 pm Post subject: sudoku |
|
|
| regarding this "extremely hard puzzle"; according to Sudoku Duck problem solver, this particular puzzle that your computer generated in unsolvable. |
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Wed Apr 16, 2008 9:53 pm Post subject: Re: sudoku |
|
|
| shar wrote: | | regarding this "extremely hard puzzle"; according to Sudoku Duck problem solver, this particular puzzle that your computer generated in unsolvable. |
That's strange: | Code: |
0 0 0 2 0 0 0 9 0
0 0 1 0 6 0 2 0 0
0 3 0 0 0 1 0 0 7
7 0 0 8 0 0 0 4 0
0 0 9 0 1 0 7 0 0
0 6 0 0 0 7 0 0 5
6 0 0 4 0 0 0 3 0
0 0 7 0 9 0 8 0 0
0 2 0 0 0 8 0 0 0
No. of givens = 25
brute found 1 solution(s). Last was:
5 7 6 2 8 3 1 9 4
4 8 1 7 6 9 2 5 3
9 3 2 5 4 1 6 8 7
7 1 3 8 5 6 9 4 2
2 5 9 3 1 4 7 6 8
8 6 4 9 2 7 3 1 5
6 9 8 4 7 2 5 3 1
3 4 7 1 9 5 8 2 6
1 2 5 6 3 8 4 7 9 |
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| Sisophon2001
 | | Joined: 05 Mar 2008 | | Posts: 32 | | : | | Location: Cambodia |
Items |
|
| Posted: Thu Apr 17, 2008 11:17 am Post subject: |
|
|
This is what my code found,
3 locked candidates
2 naked pair
1 Swordfish
1 finned Swordfish
1 Sashimi Swordfish
1 Jellyfish
2 Sashimi Jellyfish
1 XYZ-Wing
1 Sue De Coq
4 Forcing Net
No brute force necessary, but the forcing net is my technique of last resort, and I avoid it in the generator.
Garvan |
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Thu Apr 17, 2008 11:38 am Post subject: |
|
|
| Sisophon2001 wrote: |
No brute force necessary, |
Correct, but I was using it to count the number of solutions as the puzzle was claimed to be invalid.
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| Jean-Christophe
| | Joined: 19 Mar 2006 | | Posts: 126 | | : | | Location: Belgium |
Items |
|
| Posted: Thu Apr 17, 2008 12:40 pm Post subject: |
|
|
Shar didn't claim it was invalid, but unsolvable which probably means the program or person could not solve it.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes. |
|
| Back to top |
|
|
| daj95376
| | Joined: 05 Feb 2006 | | Posts: 349 | | : | |
Items |
|
| Posted: Thu Apr 17, 2008 4:11 pm Post subject: |
|
|
Definition: Puzzle Types
| Code: | unsolvable: ambiguous ... and should be ignored
valid: contains one solution
invalid: not valid
|
|
|
| Back to top |
|
|
| shar
| | Joined: 16 Apr 2008 | | Posts: 2 | | : | |
Items |
|
| Posted: Thu Apr 17, 2008 4:16 pm Post subject: |
|
|
| Thank you all for your solutions. Shar |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
