
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 reinsert 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 boardpuzzle 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 reinsert 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) 7272 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 2828 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 runtime. 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 




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
