FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    How to create a valid sudoku puzzle Goto page Previous  1, 2          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 Posted: Fri Jan 18, 2008 9:12 pm    Post subject: 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 gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Sat Jan 19, 2008 2:48 pm    Post subject: 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 m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Mon Feb 04, 2008 8:19 pm    Post subject: 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 Horsewell Joined: 17 Feb 2008 Posts: 1 : Items Posted: Sun Feb 17, 2008 2:43 pm    Post subject: 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 bhavina Joined: 23 Feb 2008 Posts: 6 : Items Posted: Sat Feb 23, 2008 2:52 pm    Post subject: Sudoku solver 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 MacroSudoku Joined: 06 Nov 2008 Posts: 4 : Items Posted: Thu Nov 06, 2008 10:30 pm    Post subject: Way to generate sudoku 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Setting sudoku All times are GMT Goto page Previous  1, 2 Page 2 of 2   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron