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   

Best way to implement a Generator w/ difficulty rating ?

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

Joined: 07 Feb 2006
Posts: 4
:

Items
PostPosted: Tue Feb 07, 2006 8:22 pm    Post subject: Best way to implement a Generator w/ difficulty rating ? Reply with quote

I've been toying around for some time with at Sudoku solver in J2ME (Java for cellphones), and so far it's first of all some damned huge code, and second of all it only implements the following four algorithms for solving the puzzles:

Single Cell
Single Solution
Single Box
Disjoint Subsets

These were the names I found at the web, and they could probably differ from what's used in this forum usually (I'm new in here).

Regardlessly I'd like to be able to generate a puzzle as well as solving it, and I figure I could use the solver to generate it - My only problem with this is, that cellphones are usually not equipped with a fast CPU, thus I'm afraid the performance will be lousy at best.
Does anyone have any experience regarding this ?

So I've been reading alot about DLX, and while I still haven't read enough about it to fully comprehend how it works, it seems like the way to go, if I wish for the ability to solve any puzzle in a reasonable amount of time.
So I'm wondering, should I give up on my current approach (the human methods of solving the puzzles) and start working on DLX, or is there anything DLX cannot do ?

Particularly I figure I could handle the difficulty rating by enabling or disabling some of the techniques used to solve the puzzle, thus making it extremely easy if only Single Solution is used, and then increasing the difficulty up to somewhat easy where all four techniques are used (yes I'm aware none of the techniques are sufficient for solving a hard puzzle)

Would this be viable or am I heading off in a wrong direction here ?

Thanks alot for all your assistance in advance, and if I broke any forum rules please let me know Smile
Back to top
View user's profile Send private message
eclark

Joined: 28 Dec 2005
Posts: 70
:

Items
PostPosted: Wed Feb 08, 2006 5:32 am    Post subject: Reply with quote

DLX will give an aproximation of difficulty. Though depending upon what what posiblities are picked to fill the squares it can give results skewed one way or another.

If you are looking at an embbedded generator. Defintaly look at dlx, another exact cover implementation, or another recursive solver. Humanistic solvers will give a better rating but will take MUCH longer.

Right now I have a humanitic solver that solves 10 puzzles on a pentium-m chip

Code:
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 13
model name      : Intel(R) Pentium(R) M processor 1.50GHz
stepping        : 8
cpu MHz         : 1495.353
cache size      : 2048 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 2
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat clflush dts acpi mmx fxsr sse sse2 ss tm pbe nx est tm2
bogomips        : 2994.41


in 0m0.269s


Though a signifigant portion of my time is spent in outputint hints. I extimate that I might be able to get a 30% reduction if I removed those.

A generator will need to run the solver many different times. So trying to run a solve method 10 times on a slow memory hampered system would be time prohibitive.

How large is your code? My java code is 3000 lines for a humanistic solver. My c++ is 3900 without my lookuptable(wich it 16000 lines of code).

My only hint for making faster code is to make position/posibility arrays first then check them. Its faster.

In a little bit I will be releasing my code both java and c++.
Back to top
View user's profile Send private message
NQbbe

Joined: 07 Feb 2006
Posts: 4
:

Items
PostPosted: Wed Feb 08, 2006 8:01 pm    Post subject: Reply with quote

Well since alot of my code is for drawing the graphics, etc. I guess the total number of lines is useless, the four algorithms though take up around 300 lines Sad

I use an array of 9x9 cells, each cell has an array of up to 9 possibilities, and then I merely use the four algorithms until it's solved, or no solution could be found. I haven't done any speed measurement, but I guess now would be a good time to do so Smile

But I guess the only way to go by now is DLX, since I also feel the silly humanistic solver I have is just insufficient at best (it solves easy puzzles only).

Does anyone have a good link for more information about DLX, like maybe some pseudo code or such ?

Also how do you use DLX for generating puzzles

My thought was to fill in random numbers (chosen from the possiblity array for the given cell) in one of the cells with least possibilities, and once the solver could solve it, I'd call it a puzzle. Is this a proper way of doing it, or are there better methods ?
Back to top
View user's profile Send private message
Henk

Joined: 13 Nov 2005
Posts: 105
:

Items
PostPosted: Wed Feb 08, 2006 9:20 pm    Post subject: Reply with quote

I have some experience in programming in J2ME. Speed will not be an issue for what you want. You will not be able to generate hundreds of puzzels per second, but who cares. This is only important when you are searching for a very specific puzzle, but you are not. 99% of the puzzles are solvable with the techniques you want to implement, so when you generate 2/3 puzzles, you will have one thats suits you. So don't worry about speed! My generater does 4000 puzzles a minute and checks for 24 different techniques. The 'clean' generater, with only 2 techniques can generate and rate about 13000 puzzles each minute.

About the solving techniques, you might want to consider that a cell phone has quite a small screen. So, you need to adjust the rating of the solving techniques for that. Example; a naked single is easy to find when you have pencil marks visible. Easier then a hidden single. But when you don't have pencil marks, a naked single is harder to find and a hidden single is relative easier.

Another thing:
Please don't mess up the battery by generating in the background or so! But you probably though about this allready.

Good luck!
_________________
Generate and solve Sudoku puzzles with Into Sudoku!
Back to top
View user's profile Send private message
NQbbe

Joined: 07 Feb 2006
Posts: 4
:

Items
PostPosted: Thu Feb 09, 2006 7:17 pm    Post subject: Reply with quote

I'm not a 100 % certain about what you mean, about the small screen ?

The way I've implemented it, you can type into each cell, which possibilities it has, so it's fairly easy to see which cells can contain what. If this is not what you had in mind, please feel free to explain further Smile

About generating in the background I have no intentions of doing that, as you say it wastes battery, and if the user quits the application I'd either have to save the puzzles that was generated (quite troublesome in J2ME IMO) or I would just had wasted the battery for nothing Smile

But you say that 99 % of the puzzles are solvable with only those four techniques I've currently implemented - are you certain of this ? I think they seem fairly "weak", and I'm quite afraid I will not be able to create difficult puzzles at all - but I guess I'll just need more techniques then Very Happy

Btw. In case I didn't clarify this earlier, I've already implemented the solver, the GUI and all the functionality for this. The only thing I lack is the generator Smile

Oh and thank you all very much for your replies Smile
Back to top
View user's profile Send private message
Henk

Joined: 13 Nov 2005
Posts: 105
:

Items
PostPosted: Thu Feb 09, 2006 7:21 pm    Post subject: Reply with quote

Quote:
But you say that 99 % of the puzzles are solvable with only those four techniques I've currently implemented - are you certain of this ?


yes, I know this for sure... I have build a generator myself that is also for produring as hard as possible puzzles. This is hard to do, because most are pretty easy to solve, even with the techniques you described.
_________________
Generate and solve Sudoku puzzles with Into Sudoku!
Back to top
View user's profile Send private message
eclark

Joined: 28 Dec 2005
Posts: 70
:

Items
PostPosted: Fri Feb 10, 2006 3:47 am    Post subject: Reply with quote

Henk wrote:
Quote:
But you say that 99 % of the puzzles are solvable with only those four techniques I've currently implemented - are you certain of this ?


yes, I know this for sure... I have build a generator myself that is also for produring as hard as possible puzzles. This is hard to do, because most are pretty easy to solve, even with the techniques you described.


99% is a high estimate.

after a run of around a million I would place it closer to 60%

That is for no symetry puzzles though so that may explain some of the difference.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Feb 10, 2006 3:58 pm    Post subject: Reply with quote

Here are my results (over 600,000 mixed symmetric/non symmetric):

73% - Solved with singles and upto 2 locked candidates (easy)
12% - Solved with tabling, forcing chains (diabolical)
1% - Solved with naked/hidden pairs only (moderate)
14% - Solved with a blend of techniques (hard-very hard)
0.05% - Solved with an interesting blend of techniques (nightmare)

These are very rough classifications. I am currently refining the "easy" category, because for a human player, they're not all so very easy. There are more aspects of rating than techniques only.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
NQbbe

Joined: 07 Feb 2006
Posts: 4
:

Items
PostPosted: Fri Feb 10, 2006 7:56 pm    Post subject: Reply with quote

Nice statistics Smile

And I agree there is more to difficulty than merely the techniques involved, however I'd think if you only need to look for singles, it's far easier than if you need to use for instance 3 different techniques in total.

But yes defining difficulty is very difficult 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