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   

Optimizing a Puzzle Generator written in C

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
maxdeliso

Joined: 28 Nov 2009
Posts: 3
:

Items
PostPosted: Sun Nov 29, 2009 8:51 pm    Post subject: Optimizing a Puzzle Generator written in C Reply with quote

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
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Sun Nov 29, 2009 9:57 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Dec 01, 2009 11:18 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
m_b_metcalf

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

Items
PostPosted: Tue Dec 01, 2009 2:37 pm    Post subject: Reply with quote

Lunatic wrote:

I know there are much better algorithms, ...

For instance here, in C and Fortran.

Regards,

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

Joined: 28 Nov 2009
Posts: 3
:

Items
PostPosted: Wed Dec 02, 2009 8:15 pm    Post subject: Reply with quote

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
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Wed Dec 02, 2009 9:47 pm    Post subject: Reply with quote

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
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Wed Dec 02, 2009 10:39 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
maxdeliso

Joined: 28 Nov 2009
Posts: 3
:

Items
PostPosted: Mon Feb 08, 2010 3:41 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
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