
View previous topic :: View next topic 
Author 
Message 
 misterunix
 Joined: 03 Nov 2006  Posts: 2  :  Location: Houston, TX  Items 

Posted: Fri Nov 03, 2006 6:51 pm Post subject: The Good The Bad The Ugly a quick overview of my Sudoku. 


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 


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

Posted: Tue Nov 07, 2006 3:16 pm Post subject: 


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 


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

Posted: Tue Nov 07, 2006 7:57 pm Post subject: Re: The Good The Bad The Ugly a quick overview of my Sudoku. 


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 


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

Posted: Sat Dec 30, 2006 10:25 pm Post subject: Two Suggestions 


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. 

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
