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   

How to create a valid sudoku puzzle
Goto page Previous  1, 2
 
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 Jan 18, 2008 9:12 pm    Post subject: Reply with quote

Ruud wrote:
Mike, 2 questions:

isn't it possible for this deadlock to occur at row 9 as well?

No. The six values in rows 1 to 6 of column 1 can appear only in columns 2 and 3 in rows 7 to 9. The three other values go straight into column 1.
Quote:

when you generate puzzles for the Patterns Game, are you just generating solutions and overlaying the pattern, or do you use methods to adjust the puzzle when it is unsolvable or not minimal? Having tried the game a few times myself, my generator has a very low yield of usable puzzles using only the random solution + pattern.

Well, without giving away trade secrets, I can confirm that the method of generating a full grid and checking whether the overlayed pattern yields a unique solution (it must have at least one) is, indeed, not very productive. However, it can be improved by checking for uncovered unavoidable 4- and 6-sets while generating the grid. This is very simple using my row-by-row technique. For instance, once the first three rows are in place, a first check is possible and a restart can be made if necessary. And so on for each horizontal chute, and then the whole grid. This is faster than trying permutations of a solution grid (for me).

The method I use in the Patterns Game is based on assigning values to the cells in the pattern in accordance with the basic constraints, and then checking whether the result yields zero, one or more than one solution. As you might guess, my attempts to chase JPF and TTHsieh have led to my adding many refinements that I'm reluctant to discuss in public, but varying the values is one of them.

HTH

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 Jan 19, 2008 2:48 pm    Post subject: Reply with quote

in hopes of adding more patterns game players
I'll hint at another, different, trade secret
look at the techniques that led to a flurry of 17's and easter monster class puzzles
or maybe my solver --man (you'll have to dig for that one)
Back to top
View user's profile Send private message Visit poster's website
m_b_metcalf

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

Items
PostPosted: Mon Feb 04, 2008 8:19 pm    Post subject: Reply with quote

m_b_metcalf wrote:
Ruud wrote:
when you generate puzzles for the Patterns Game, are you just generating solutions and overlaying the pattern, or do you use methods to adjust the puzzle when it is unsolvable or not minimal? Having tried the game a few times myself, my generator has a very low yield of usable puzzles using only the random solution + pattern.

Well, without giving away trade secrets, I can confirm that the method of generating a full grid and checking whether the overlayed pattern yields a unique solution (it must have at least one) is, indeed, not very productive. However, it can be improved by checking for uncovered unavoidable 4- and 6-sets while generating the grid. This is very simple using my row-by-row technique. For instance, once the first three rows are in place, a first check is possible and a restart can be made if necessary. And so on for each horizontal chute, and then the whole grid. This is faster than trying permutations of a solution grid (for me).


Ruud,
As a footnote, for the current Patterns Game, this method does much better than usual (not that it's given me a playable puzzle, but only because I used it too late). Maybe it's because of the relatively large number of givens and their even distribution.

Regards,

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

Joined: 17 Feb 2008
Posts: 1
:

Items
PostPosted: Sun Feb 17, 2008 2:43 pm    Post subject: Reply with quote

Now no digit can be placed where the ? is. Note that by working with rows rather than cells, the row constraint is always fulfilled.

Great .That's perfect.
Back to top
View user's profile Send private message
bhavina

Joined: 23 Feb 2008
Posts: 6
:

Items
PostPosted: Sat Feb 23, 2008 2:52 pm    Post subject: Sudoku solver Reply with quote

Hi, what is the best algorithm to implement a 9x9 sudoku? Is it backtracking (forward checking or backjumping?), genetic algorithms, stochastic methods, brute force methods, constraint propagation etc? Also how do you rate the difficulty of a puzzle - I know you look at what methods you use to solve the puzzle and rate it accordingly but how do you know which methods will be used to solve the puzzle? What algorithms do you use to generate sudoku puzzles - easy, medium and hard? I am doing an undergraduate project and would appreciate some help. Thank you.
Back to top
View user's profile Send private message
MacroSudoku

Joined: 06 Nov 2008
Posts: 4
:

Items
PostPosted: Thu Nov 06, 2008 10:30 pm    Post subject: Way to generate sudoku Reply with quote

Hey everyone, here is my method to generate sudoku.

1_ It sets 10 random numbers on the grid
2_ It tries to solve the grid, without looking for all solutions (1 is enough)
3_ If the grid is unfeasible, it goes back to 1. Else, continue to 4.
4_ From the grid solved, it will remove 1 number (chose randomly)
5_ From the grid with a number removed, it will solve the grid and count how many solutions are possible.
6_ If the grid has more than 1 solution, then it put back the removed number.
7_ It does that until all numbers has been checked (i.e. removed OR put back).

The idea is that it takes too much time to add numbers 1 by 1 (it is never sure that the grid will be feasible, OR that there will be only 1 solution), especially as it seems that there is no link between the number of figures given and the difficulty of the Sudoku.

On the other hand, setting a valid grid from a limited number of figures and then removing the numbers allows the software to be always sure that the grid is feasible. It can also stop when all numbers have been checked and eventually removed (though the result depend on which order the figures have been removed).

Then, you only need to solve a last time the grid to evaluate its rank/difficulty.

What do you guys think about this?

Check out macrosudoku_dot_blogspot_dot_com if you want to see the results (which can still be improved).
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
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