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   

setting Difficulty level question, attempted second repost
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
louwin

Joined: 03 Jan 2010
Posts: 11
:
Location: Western Australia

Items
PostPosted: Wed Jan 06, 2010 2:26 pm    Post subject: setting Difficulty level question, attempted second repost Reply with quote

I posted this on the 3rd and this morning and now again in the evening as neither posting has shown up. The first two postings were in the Programming section so now I'm trying the Setting section. Wish me luck!

I played many games on a Sourceforge GPL Sudoku game. It is written in C# and the game play is the best I have EVER played with. OBTW it is on a PPC currently running WM2003SE.

I REALLY love playing this version from the MANY I've tried for its' features and game play. It generates many board sizes but I only ever play the 9X9. I downloaded the source and the first thing I did was hardwire the 9X9. I am using a 90 day trial of Visual Studio 2008. I tried the express version but it didn't seem to like projects for PPC.

It automatically restores the previous game to the state before PPC switch off or whatever. While you play the current game it generates the next game in the background. You can "pick up" any number on the board with the stylus and put it in any empty cell. It has automatic dynamic pencil marks. I hardwired the horizontal and vertical symmetry (were chooseable options). It uses the DLX solver.

Absolutely lovely implementation of Sudoku. BUT, there is always a BUT....

The generation of the next game is abysmally(sp?) slow, it can take 11seconds or 45minutes (yes! no mistake, 45 minutes) to generate the next game. While it is generating the next game (in a thread) the response to stylus taps etc is attrocious. This is the same with the VS2008 PDA Emulator so it isn't just MY PDA. So I set about trying to do something about this.

I thought the generator was the problem so I reasearched generators and selected one written in vb dotNET to replace it.

Out of curiousity I put a couple of timers in the existing code. It wasn't the Generator, that would run in 6 or 7 seconds. Not particularly good but not a problem. The program generates Very Easy, Easy, Medium, Hard, Very Hard and Expert level games. I always play the "hard" ones but left the logic for other levels intact.

After the generator finished with the grid it would enter the "Difficulty Setting routine". This would first clear a ratio of the cells, 59 of them in the case of a Hard game, and intelligently solve the grid. It applies logic to evaluate the difficulty of the resultant grid and it it isn't of the required difficulty it clears more numbers, if the grid was too easy, and replaces some numbers, if it was too hard and re-solves. And checks difficulty removes/replaces more numbers and re-solves and so on an so on until it arrives at the required difficulty.

It is this difficulty setting routine that could run for 4 seconds OR 45 minutes or 36 minutes or 21 minutes or 15 seconds etc. It can also run in 52 seconds or 41 seconds or 11 seconds etc, totally variable timing.

Here is my question.

Does anyone know of a better, faster difficulty setting routine? Preferably in C# or transalateable VB as a second choice.

Is it reasonable for a difficulty routine to run that long? I can sort of understand it but find it difficult Smile to accept.

It is marvellous Solver_Generator otherwise. As I said the code is from Sourceforge and is GNU GPL so what I'm doing is perfectly acceptable, legal and fair. I have no intentions stealing the original author's thunder I just want to modify_improve the program for my own use.

I would appreciate any help I'm offered in this venture and no, it isn't a project for school or university Smile Smile

I am retired and was an analyst_programmer for 35 years in assembly, COBOL and BASIC but no C# and no OOP etc till now.

I hope my 90 day trial doesn't run out before I finish these modifications Rolling Eyes

TIA

louwin

Smile Smile
Back to top
View user's profile Send private message Send e-mail
louwin

Joined: 03 Jan 2010
Posts: 11
:
Location: Western Australia

Items
PostPosted: Wed Jan 06, 2010 2:30 pm    Post subject: Reply with quote

The post kept failing because I had vb dot NET in the article! I also removed all the slashes in desperation. The third posting finally went through. Thank Heavens!

I hope I get some responses after all the trouble I've taken! Smile Smile Smile
Back to top
View user's profile Send private message Send e-mail
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Thu Jan 07, 2010 10:51 pm    Post subject: Reply with quote

I will give you my opinion, since you want a reply.

You don't know much about Sudoku.


To write, or edit, a program knowledge about the gestalt is essential.

You don't have it. You know close to nothing about sudoku puzzles.

Oh, best advice? Learn the constraints.
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 61
:
Location: Silver Spring, MD

Items
PostPosted: Fri Jan 08, 2010 3:19 am    Post subject: Reply with quote

A puzzle solver should run at thousands of puzzles a second or faster. Creating a fully filled in valid grid should also run at thousands of puzzles a second or faster. On a desktop machine my code runs at about 100,000 puzzles per second, on the iPhone I get more like 10,000/second. Even a rather slow interpreted environment ought to be getting around 1,000/second.

Creating a puzzle of a given difficulty is a bit more complex. There are several ways to approach this problem. The one you describe is not one of the common ones.

The most common approach is to create a sequence of random puzzles and rate their difficulty. As soon as you find one of the correct difficulty you stop. My puzzle creator can occasionally take a couple of seconds to create a puzzle at an extremely high difficulty level on an iPhone. Ordinary difficulties are created at about 20 or 30 a second, again on the iPhone. Desktop machines typically are ten to one hundred times as fast, or faster.

There are many open source puzzle solvers, for various definitions of open source. You can find several on this site. There are very few open source programs that can produce puzzles of a specific difficulty, ast-sudoku is the only one I can think of off hand, though I know there are at least a few others.
Back to top
View user's profile Send private message
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Fri Jan 08, 2010 11:44 pm    Post subject: Reply with quote

Hmmm,

Did you notice that the generator of choice equates difficulty to the number of givens?

I am probably wrong. My answer was based on that mis-observation.

<sigh>
Back to top
View user's profile Send private message
louwin

Joined: 03 Jan 2010
Posts: 11
:
Location: Western Australia

Items
PostPosted: Sat Jan 09, 2010 1:45 am    Post subject: Your opinion - wapati Reply with quote

I'm sorry you have such a poor opinion of my Sudoku skills but I suppose that's YOUR problem not mine.

The program uses the number of givens as a starting point as my original question states.

I notice you are quick to critise but you haven't come up with any suggestions to equal to your claimed vast knowledge of Sudoku.

I'm sorry but that is enough said to wapati.


On to JasonLion - thanks for your ideas and I take your point. I have evaluated a generator that generates about half a million grids a second (on my PC) and I will, in time, port this logic to my PPC. Allowing for the difference of power I estimate that my PPC should be able to generate in the order of 10,000 grids per second. But I can live with, for the moment, a 6 or 7 second generator. It is the totally variable difficulty setting routine I am having trouble with - 4 seconds to 45 minutes is unacceptable.

I think you are suggesting - generate a grid, remove some (how many?) numbers, estimate its' difficulty, if wrong, discard and try again, right?

Okay, that's longer term and a bigger project then I was hoping but I will give it a try. First I will implement the fast generator. Then I will search this site for the aforementioned open sources for faster difficulty routines.

You program an iPhone? I AM impressed. Surprised

I hope I got the right smiley Smile

I thought of programming an iTouch, not into fancy phones, but gave up the idea when I found out you need a Mac.... Sad

Your solver isn't one of the open source programs, is it? Wink
Back to top
View user's profile Send private message Send e-mail
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Sat Jan 09, 2010 4:47 am    Post subject: Re: Your opinion - wapati Reply with quote

louwin wrote:
I'm sorry you have such a poor opinion of my Sudoku skills but I suppose that's YOUR problem not mine.

The program uses the number of givens as a starting point as my original question states.

I notice you are quick to critise but you haven't come up with any suggestions to equal to your claimed vast knowledge of Sudoku.

I'm sorry but that is enough said to wapati.



Number of givens is not relevant, unless below 17 or above 76.


Last edited by wapati on Tue Jan 12, 2010 5:39 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: Sat Jan 09, 2010 9:12 am    Post subject: Reply with quote

I noticed the variable time for new puzzle generation in my lkSudoku program, where the time for creating Hard level puzzles varies between 1/4th of a second to ~3 seconds (the Extreme level puzzles is quicker though)

The cause for the varying time is the probablility to encounter a puzzle that is not too easy and not too hard

If the puzzles of requested difficuly are rare, the probability of randomally generating them is smaller, thus requiring an expected larger amount of cells replacing and checking; this number is probabalistic, so if you are lucky, it can be that on the first puzzle checking you get the desired puzzle level, and in an unlucky case, it can take an almost infinite amount of cells replacing (and if you do not mark your previous random choices, it can take an infinite time to find the rare puzzle)

Probabalistic laws show that the expected distribution is what you are usually going to get and the farther you are from that amount of changes, the less likely it is going to be

You may try to reduce time by optimizing the logic solving routing, this will improve the expeted overall time, but only by some factor, and only in expected time terms

In my program generator, after some cells removal trials, I start the entire generation proces from the beginning, generating a new full solution

You may also optimize the logical solver so that it will not try to solve the entire puzzle, but instead, it will only try to solve up to the point which identifies whether the puzzle has the requested difficuly level

In order to avoid the variable generation time on my website www.lksudoku.co.cc I have created in advance hundreded of thousands of puzzles for all difficulty levels, and the website only loads puzzles, this approach can also work for machines with lesser computation resources
Back to top
View user's profile Send private message Send e-mail
louwin

Joined: 03 Jan 2010
Posts: 11
:
Location: Western Australia

Items
PostPosted: Sat Jan 09, 2010 11:37 pm    Post subject: wapati is pathetic! Reply with quote

you must be a pathetic individual wapati.

I don't know you and you don't know me but you cjoose to be rude and offensive.

If you don't have a reasonable idea and cannot contribute to this conversation - why don't you shut the **** up and die. I'm sure a lot of people would be a lot happier if you did. Make the world a better place, leave it....

Stupid ****
Back to top
View user's profile Send private message Send e-mail
louwin

Joined: 03 Jan 2010
Posts: 11
:
Location: Western Australia

Items
PostPosted: Sun Jan 10, 2010 12:02 am    Post subject: good idea lksudoku Reply with quote

I can see that getting this program working better is going to be a long term project as I will have to replace the generation/difficulty setting routines.

Funnily, I had come to the conclusion of adding a new mode into the program. Because it is a memory limited PPC and I can't store hundreds of thousands of pre-generated games I have been thinking of an overnight generation mode. Plug the PPC in for recharge and run the generator mode which will generate hundreds of games and store them to memory and modify the "play" mode to load these stored games and delete them after play. A few days later run the generator mode again and replace (regenerate) the deleted games so there will always be more than enough games for the day.

Because of the dymanic pencil marks and the structure of the arrays each game is about 1K on disc. This is so large because it currently stores the game's, possibily half played, state.

I could change this to just store each generated (and difficulty set) game to the 81 values and store over 12000 games to a megabyte.

Thanks for your ideas lksudoku. Is your game open source? Smile
Back to top
View user's profile Send private message Send e-mail
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Sun Jan 10, 2010 8:12 pm    Post subject: Reply with quote

There was a discussion as to the amount of memory required to store a sudoku puzzle, both theoretically, and with practical implementation, see http://www.setbb.com/sudoku/viewtopic.php?t=1845&mforum=sudoku for more details

The most efficient storage would require some fast deterministic generator with random number generator, and a seed per puzzle (with the generated puzzle from the seed ranked in advance)

My game is not open source for now, although I did divide it into a library part and gui part, so the library part source could be released someday
Back to top
View user's profile Send private message Send e-mail
humble_programmer

Joined: 27 Jun 2006
Posts: 69
:
Location: Colorado Springs, USA

Items
PostPosted: Tue Jan 12, 2010 1:54 am    Post subject: Reply with quote

I downloaded the same open source program, and noticed that it was unusually slow at generating puzzles, especially when compared to some of the solvers that I--and other esteemed members of this forum--have created. I spent a few minutes reviewing the codebase, and came to the following conclusions:

(1) The author(s) have a reasonable understanding of Sudoku, as the solver correctly uses XY-Wings, Basic Fish, Simple Coloring, and so on. It uses these to determine the "difficulty" of the puzzle.

(2) The author(s) are not skilled programmers, or at the very least, are not experts at CLR/C# coding. For example, all of the candidates/pencil marks are coded using arrays of booleans instead of bitmaps.

(3) The real slowdown comes in the way that puzzles are graded: every puzzle is solved to completion, even if it is more difficult than the user requested. An obvious--and easily implemented optimization--would be to discard a puzzle as soon as all of the level-specific solving techniques are exhausted.

I hope to spend a few hours this weekend looking at porting my own home-grown sudoku solver/generator to a Windows Mobile-compatible format, so that I can post some real PC vs. PocketPC comparisons.

Lastly, I want to scold wapati for being rude. The original poster posed a legitimate question, and backed it up with a description of what he had already "figured out for himself". To respond with "You're a dumber than sh!t n00bie" is undeserved and reflects more poorly on wapati than on the poster. Compared to some of the "will you do my homework for me?" posts we've seen in the past, this gentleman is more than welcome to my time and talent. Shame on you, wapati.

Cheers!
Humble Programmer
,,,^..^,,,
Back to top
View user's profile Send private message Visit poster's website
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Tue Jan 12, 2010 5:37 am    Post subject: Reply with quote

humble_programmer wrote:


Lastly, I want to scold wapati for being rude. The original poster posed a legitimate question, and backed it up with a description of what he had already "figured out for himself". To respond with "You're a dumber than sh!t n00bie" is undeserved and reflects more poorly on wapati than on the poster. Compared to some of the "will you do my homework for me?" posts we've seen in the past, this gentleman is more than welcome to my time and talent. Shame on you, wapati.

Cheers!
Humble Programmer
,,,^..^,,,


Good points. I am rude.

The concern about number of givens doesn't disturb you?

A new grid for each puzzle?

There is a lack of very basic knowledge here, and I don't mean yours.
Back to top
View user's profile Send private message
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Tue Jan 12, 2010 7:32 am    Post subject: Re: wapati is pathetic! Reply with quote

louwin wrote:
you must be a pathetic individual wapati.

I don't know you and you don't know me but you cjoose to be rude and offensive.

If you don't have a reasonable idea and cannot contribute to this conversation - why don't you shut the **** up and die. I'm sure a lot of people would be a lot happier if you did. Make the world a better place, leave it....

Stupid ****


Perhaps I was wrong.

You do understand sudoku.

You can write a program.

I await results.


I have been rude. I apologize.
Back to top
View user's profile Send private message
louwin

Joined: 03 Jan 2010
Posts: 11
:
Location: Western Australia

Items
PostPosted: Tue Jan 12, 2010 11:08 am    Post subject: Apology accepted Reply with quote

Apology accepted.

I admit you are mostly right. I only play "Hard" games so am NOT an expert in Sudoku.

I am an expert Assembly and commercial programmer and I said, up front, that this is my first attempt at C#. I'm too impatient to learn the language so I just jumped in. It took me weeks to understand the little I know about the program in question, what took Humble Programmer a "few" hours to learn and an expected few hours to convert his program to PPC environment.

I would love to be so adept. I am very willing to learn from my peers, hence I end every post with the question if the responder has released his code to "open source".

I have played the few Sudoku games available for the PPC (and a few more for the PC for comparison) and I love this particular programs' game play. I am very sorry to say I am not into playing Sudoku on my PC. I love the portability and convenience of the PPC.

Maybe I will change my mind when I get my notebook, you never know....

In my limited experience I had wondered about bit fields but because they weren't in the program currently I didn't take my wondering any further. Would bit fields be any faster though? Certainly the data footprint would be smaller but faster?

I have seen some of Humble Programmers posts and have always been impressed, your response to my post confirms my good opinion of you. The fact that you can port your program to the PPC in a few hours further impresses me. I have been at this for over a month and have hardly scratched the surface.

I will ask my usual question - is your solver/generator open source? What is it written in? Did you notice the source has the DLX solver but I don't think it is used? I could be wrong (I usually am!).

I will make an effort to try out your solver (if I can!).

Thank you - I need all the help I can get.
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
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