FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Optimizing a Puzzle Generator written in C          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message maxdeliso Joined: 28 Nov 2009 Posts: 3 : Items Posted: Sun Nov 29, 2009 8:51 pm    Post subject: Optimizing a Puzzle Generator written in C Hello folks. I have written a Sudoku board generator in C and I'm fairly certain that there are much better ways to go about it than I have. My method of generation is this: start with an empty board while( the board is not filled ) { find out how many moves are legal in each cell sort to find the most constrained if ( the board isn't filled and there is an empty cell into which no numbers can be legally placed ) { clear the board } } Then to make a puzzle out of it, I simply remove a random cell's value, check to see if that board has at least one cell who's value can be logically deduced (i.e. there is only one possible move ), and re-insert that value if there is no such cell. (And I repeat this 100 times ). This is the best I could come up with for a generation algorithm. And I've also coded the whole thing up in C. It generates a board-puzzle pair in about 0.1s typically. the code can be found here: www [dot] maxdeliso [dot] com [slash] sudoku.zip EDIT: The code has been moved to www [dot] maxdeliso [dot] com/downloads/sudoku.zip Any feedback/suggestions for improvement of the algorithms is invited. Thanks! --max Last edited by maxdeliso on Sun Jan 03, 2010 4:55 am; edited 1 time in total Back to top lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Sun Nov 29, 2009 9:57 pm    Post subject: Some notes: - When creating the full puzzle in the board creation algorithm, when the board isn't filled and there is an error, you can backtrack to the last guessed value instead of restarting the entire puzzle creation thus continuing from a more advanced puzzle state - You may use more logic in the full puzzle generation process, it seems that that you only apply logic for finding naked singles and not hidden singles Quote: Then to make a puzzle out of it, I simply remove a random cell's value, check to see if that board has at least one cell who's value can be logically deduced (i.e. there is only one possible move ), and re-insert that value if there is no such cell. (And I repeat this 100 times ). I am not sure this removal method ensures a unique solution puzzle, if you remove one cell, say at row 1 col 1, and can logically deduce another cell, say row 7 col 7, but not row 1 col 1, there is no theoretical reasoning that shows that there is a unique solution; if you could deduce the exact cell that you removed, this would prove a unique solution though, but the resulting puzzle will be fairly easy to solve Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Tue Dec 01, 2009 11:18 am    Post subject: You can check the c code from my random sudoku generator example at http://users.telenet.be/mpq/sudoku/random_sudoku_generator.c I know there are much better algorithms, but I wanted to provide a C code example with a low threshold... _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Tue Dec 01, 2009 2:37 pm    Post subject: Lunatic wrote: I know there are much better algorithms, ... For instance here, in C and Fortran. Regards, Mike Metcalf Back to top maxdeliso Joined: 28 Nov 2009 Posts: 3 : Items Posted: Wed Dec 02, 2009 8:15 pm    Post subject: Quote: For instance #I couldn't post this link because I don't have 5 posts yet# in C and Fortran. Although these are excellent routines for random number generation, I was hoping for a better algorithm specifically for board generation. Although perhaps the routines discussed there would execute more quickly than calls to rand(), if coded correctly. Quote: I am not sure this removal method ensures a unique solution puzzle, if you remove one cell, say at row 1 col 1, and can logically deduce another cell, say row 7 col 7, but not row 1 col 1, there is no theoretical reasoning that shows that there is a unique solution; All puzzles generated by my code have unique solutions ( so far ) as tested by various solvers. Staring from a completed board, each updated puzzle is guaranteed to have a unique solution, otherwise the number that was just removed ( randomly ) is reinserted. Quote: if you could deduce the exact cell that you removed, this would prove a unique solution though, but the resulting puzzle will be fairly easy to solve This seems to be the case so far, although because of the random nature of the generation, certain puzzles can be more difficult than others. However it is true that the average difficulty is quite low ( this is probably because simple solvers do exactly what my code does, except in reverse ). Perhaps the best way to generate difficult boards is to remove cells in such a way as to force the use of difficult techniques, but how to implement this in code is not yet clear to me. Also, making the board difficult to solve by a machine would be an entirely different process than making the board difficult to solve by a human. Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Wed Dec 02, 2009 9:47 pm    Post subject: There is a thread in the Players' Forums about generating unbiased filled grids. Methods are presented there for generating the grids quickly. I don't care if a grid is biased or not. For me, the problem isn't the grid, but rather the time it takes to search the grid for a puzzle with something more interesting than a solution by basic techniques. Right now, the second step is orders of magnitude more time consuming! ===== ===== ===== ===== ===== ===== Something to consider about generating puzzles from filled grids. In the grid below, there's a UR4 unavoidable set (deadly pattern) 7-2-7-2 in r16c45. This means that one of these cells must be provided as a given in any puzzle created from this grid. You might wish to bias your puzzle generation logic to remove values last from cells in UR4 unavoidable sets. Especially cells that appear in more than one UR4 unavoidable set -- like the <2> in r1c5 that's also in a 2-8-2-8 pattern! Code:  +-----------------------+  | 9 3 6 | 7 2 8 | 4 5 1 |  | 1 7 4 | 6 5 3 | 8 9 2 |  | 5 2 8 | 4 9 1 | 7 3 6 |  |-------+-------+-------|  | 3 5 1 | 8 6 4 | 9 2 7 |  | 7 8 2 | 1 3 9 | 5 6 4 |  | 4 6 9 | 2 7 5 | 3 1 8 |  |-------+-------+-------|  | 6 4 3 | 9 8 2 | 1 7 5 |  | 8 9 7 | 5 1 6 | 2 4 3 |  | 2 1 5 | 3 4 7 | 6 8 9 |  +-----------------------+ Back to top lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Wed Dec 02, 2009 10:39 pm    Post subject: maxdeliso wrote: Quote: I am not sure this removal method ensures a unique solution puzzle, if you remove one cell, say at row 1 col 1, and can logically deduce another cell, say row 7 col 7, but not row 1 col 1, there is no theoretical reasoning that shows that there is a unique solution; All puzzles generated by my code have unique solutions ( so far ) as tested by various solvers. Staring from a completed board, each updated puzzle is guaranteed to have a unique solution, otherwise the number that was just removed ( randomly ) is reinserted. According to your code, your puzzles have unique solution, your algorithm tries to solve the entire board after removing a cell, and only if it succeeds, it acceepts the cell removal You could optimze your algorithm so that after removing a cell, you try to deduce the removed cell from the partial puzzle, instead of solving it entirely Back to top maxdeliso Joined: 28 Nov 2009 Posts: 3 : Items Posted: Mon Feb 08, 2010 3:41 am    Post subject: Quote: You could optimze your algorithm so that after removing a cell, you try to deduce the removed cell from the partial puzzle, instead of solving it entirely I like your idea, that would definitely result in a faster average run-time. I will update my code according to your suggestion when I get the time ( I haven't had the time to do it lately ). But when I do I'll post the results. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Page 1 of 1   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