Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Extremely hard puzzles thanks to a bug in my generator

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
crosspollinator

Joined: 24 Jun 2006
Posts: 4
:

Items
PostPosted: Fri Jun 30, 2006 4:01 am    Post subject: Extremely hard puzzles thanks to a bug in my generator Reply with quote

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
View user's profile Send private message
shar

Joined: 16 Apr 2008
Posts: 2
:

Items
PostPosted: Wed Apr 16, 2008 8:07 pm    Post subject: sudoku Reply with quote

regarding this "extremely hard puzzle"; according to Sudoku Duck problem solver, this particular puzzle that your computer generated in unsolvable.
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Wed Apr 16, 2008 9:53 pm    Post subject: Re: sudoku Reply with quote

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
View user's profile Send private message
Sisophon2001

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Thu Apr 17, 2008 11:17 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Thu Apr 17, 2008 11:38 am    Post subject: Reply with quote

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
View user's profile Send private message
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Thu Apr 17, 2008 12:40 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Thu Apr 17, 2008 4:11 pm    Post subject: Reply with quote

Definition: Puzzle Types

Code:
unsolvable: ambiguous ... and should be ignored

  valid:    contains one solution
invalid:    not valid
Back to top
View user's profile Send private message
shar

Joined: 16 Apr 2008
Posts: 2
:

Items
PostPosted: Thu Apr 17, 2008 4:16 pm    Post subject: Reply with quote

Thank you all for your solutions. Shar
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron