
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 6sets while generating the grid. This is very simple using my rowbyrow 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: 408  :  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 6sets while generating the grid. This is very simple using my rowbyrow 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 




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
