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   

Generating puzzles with 20-23 clues

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
m_b_metcalf

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

Items
PostPosted: Fri Dec 05, 2008 9:40 am    Post subject: Generating puzzles with 20-23 clues Reply with quote

On a neighbouring thread people have described the ways in which sudoku puzzles are usually produced. For the sake of completeness, I describe here two other approaches that are good at producing asymmetric, minimal puzzles with clue counts in the range 20-23, whilst being rather slow.

Have these methods been described before and I've simply missed them?

METHOD A
Step 1. Generate a solution grid.

Step 2. Remove clues at random until a minimal puzzle is achieved.

Step 3. Simultaneously change the value of n clues (n can be say 1, 2 or 3) such that a new valid puzzle is created, which of course corresponds to a new grid with different unavoidable sets, so allowing a renewed check on whether the fresh puzzle is minimal. If it is not, remove further random clues until it is.

Step 4. Repeat step 3 until no further changes to the values can be made and hence no further deletions are possible.

METHOD B
Step 1. Generate a solution grid.

Step 2. Find as many unavoidable sets as possible in the grid.

Step 3. Create an empty puzzle and copy into it the minimal possible set of clues from the solution grid that, combined, cover all the found unavoidable sets.

Step 4. Add further clues until there are at least 17, selecting cells based on their impact (most likely to lead rapidly to a unique solution).

Step 5. Once there about 20 clues and the puzzle still has no unique solution, find all the solutions to the candidate puzzle, and ensure that new clues are added only from those cells that are not in the set of common values in the multiple solutions (i.e. don't add redundancy).

Step 6. Repeat steps 4 and 5 until a single solution is reached.

Step 7. Remove, optimally, redundant clues.

Step 8. Optionally, apply steps 3 and 4 of Method A. An example is then
Code:

 8 2 . . . . 1 . .
 . . . 7 . . 3 . 9
 . . 5 . 6 . . . .
 9 . . . . . 4 . 8
 . . 4 . 2 . . . .
 . . . . . 5 . . .
 . . 6 . 3 . . . .
 . 5 . . . . . . 2
 . . . . . 8 . . .    19 clues


Regards,

Mike Metcalf
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sat Dec 06, 2008 3:20 pm    Post subject: Re: Generating puzzles with 20-23 clues Reply with quote

the method I've had most success with in lowering the clue count
is to start with a minimal puzzle and then place it through multiple rounds
of {-n+m}Xr (drop n clues add m clues for r rounds)
each round checks for minimal puzzles and discards the rest
the next round continues with the new pool of puzzles

this is how I'm doing the 17 search now

here are the sequences that have panned out for initial 23 and 22 clue seed puzzles
Code:
23 {-3+1}{-2+1}x4{-1+1}x4{-2+1}
22 {-2+1}x4{-1+1}x4{-2+1}

the {...}X... notation is accepted by the -go option of my solver

this is also a way to generate "hard" puzzles
seed a {-n+n} tour with a known hard puzzle
(although puzzles on the player's forum have probably already been subjected to {-2+2})
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku 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