|
View previous topic :: View next topic |
Author |
Message |
| NQbbe
| Joined: 07 Feb 2006 | Posts: 4 | : | | Items |
|
Posted: Tue Feb 07, 2006 8:22 pm Post subject: Best way to implement a Generator w/ difficulty rating ? |
|
|
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 |
|
Back to top |
|
|
| eclark
| Joined: 28 Dec 2005 | Posts: 70 | : | | Items |
|
Posted: Wed Feb 08, 2006 5:32 am Post subject: |
|
|
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 |
|
|
| NQbbe
| Joined: 07 Feb 2006 | Posts: 4 | : | | Items |
|
Posted: Wed Feb 08, 2006 8:01 pm Post subject: |
|
|
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
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
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 |
|
|
| Henk
| Joined: 13 Nov 2005 | Posts: 105 | : | | Items |
|
Posted: Wed Feb 08, 2006 9:20 pm Post subject: |
|
|
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 |
|
|
| NQbbe
| Joined: 07 Feb 2006 | Posts: 4 | : | | Items |
|
Posted: Thu Feb 09, 2006 7:17 pm Post subject: |
|
|
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
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
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
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
Oh and thank you all very much for your replies |
|
Back to top |
|
|
| Henk
| Joined: 13 Nov 2005 | Posts: 105 | : | | Items |
|
Posted: Thu Feb 09, 2006 7:21 pm Post subject: |
|
|
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 |
|
|
| eclark
| Joined: 28 Dec 2005 | Posts: 70 | : | | Items |
|
Posted: Fri Feb 10, 2006 3:47 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Fri Feb 10, 2006 3:58 pm Post subject: |
|
|
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 |
|
|
| NQbbe
| Joined: 07 Feb 2006 | Posts: 4 | : | | Items |
|
Posted: Fri Feb 10, 2006 7:56 pm Post subject: |
|
|
Nice statistics
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 |
|
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
|