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   

The Good The Bad The Ugly a quick overview of my Sudoku.

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

Joined: 03 Nov 2006
Posts: 2
:
Location: Houston, TX

Items
PostPosted: Fri Nov 03, 2006 6:51 pm    Post subject: The Good The Bad The Ugly a quick overview of my Sudoku. Reply with quote

Howdy All!
I just finished recoding my Sudoku programs from C to C++/Classes and I thought I would share my pain / joy with others.
----
I go through a 4 step process to generate my puzzles for the web.
1st, I generate solved valid grids.
2nd, I generate puzzles.
3rd, I solve and score as much as I can
4th, Generate the PDFs for people to print.
----
My grid generator uses a random number in the firts cell, then randomly picks a valid number for the next cell. This loops until a cell cant be filled in, in that case it backtracks a cell and picks the next valid number.
This worked out very well.
----
My puzzle generator, it a bit more painfull.
I take a random cell, find the mirror of the cell and remove the numbers.
Run the resulting puzzle past a recursive solver. If it has more than one solution, I put the numbers back and pick another random location. If it only has 1 solution it keeps removing numbers until it can nolonger remove any more cells.
This is VERY SLOW! When the remaining cell count is less than around 26, the solver takes longer and longer to calculate.
----
My scoring system is based on human solving. It solves all naked singles, then moves on to all hidden singles. Looping each time to catch new naked/hidden.
That is as far as Ive taken it. Im going to give myself a break before starting up coding the solver again. The next two things I want to add is locked col/row and naked doubles. Right now almost a 3rd of the puzzles are solveable with only naked/hidden singles.
----
All this data is kept in a database, and I have some fairly simple code to produce PDF files of the puzzles for peoples playing pleasure. Mainly my family and they can only do the very easy ones.

Thats a generic overview of my Sudoku models.

Bill
Back to top
View user's profile Send private message Yahoo Messenger
misterunix

Joined: 03 Nov 2006
Posts: 2
:
Location: Houston, TX

Items
PostPosted: Tue Nov 07, 2006 3:16 pm    Post subject: Reply with quote

After a wipe of the Database and a new start rebuilding my data, here are the raw stats.

Current Database Sudoku Puzzle Stats
Total Entries 343672
Grids w/o Sudoku Puzzles 133935
Sudoku Puzzles waiting to be scored 200788

Givens Count
22 68
23 262
24 5543
25 7251
26 49434
27 25088
28 74836
29 16898
30 25679
31 2385
32 2056
33 153
34 78
35 7
36 1

Looks like my random puzzle makers favors 28 and 26 given puzzles.

Hmmm..

Bill
Back to top
View user's profile Send private message Yahoo Messenger
m_b_metcalf

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

Items
PostPosted: Tue Nov 07, 2006 7:57 pm    Post subject: Re: The Good The Bad The Ugly a quick overview of my Sudoku. Reply with quote

misterunix wrote:
My puzzle generator, it a bit more painfull.
I take a random cell, find the mirror of the cell and remove the numbers.
Run the resulting puzzle past a recursive solver. If it has more than one solution, I put the numbers back and pick another random location. If it only has 1 solution it keeps removing numbers until it can nolonger remove any more cells.
This is VERY SLOW! When the remaining cell count is less than around 26, the solver takes longer and longer to calculate.


You can speed this up be removing impossible candidates from the recursion. If you have, for example, a 4 in r1c1, then no other cell in the first row, the first box, and the first column can have a 4, so that value need never be tested for.

HTH,
Mike Metcalf
Back to top
View user's profile Send private message
holdout

Joined: 30 Dec 2006
Posts: 8
:
Location: Bowie, MD (USA)

Items
PostPosted: Sat Dec 30, 2006 10:25 pm    Post subject: Two Suggestions Reply with quote

1) After you have generated all 81 cells, instead of removing cells in pairs, you might try starting with an empty grid, and adding cells in pairs (you already know what the cell values should be). Cell 41 is a special case. Start with at least 17 cells (the current minimum) before running your solver.

2) You said that your solver is "VERY SLOW". Make it faster. Wink
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting 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