setting Difficulty level question, attempted second repost

louwin

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

louwin · Posted: Wed Jan 06, 2010 2:30 pm Post subject:

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

wapati · Posted: Thu Jan 07, 2010 10:51 pm Post subject:

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.

JasonLion · Posted: Fri Jan 08, 2010 3:19 am Post subject:

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.

wapati · Posted: Fri Jan 08, 2010 11:44 pm Post subject:

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>

louwin · Posted: Sat Jan 09, 2010 1:45 am Post subject: Your opinion - wapati

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

wapati · Posted: Sat Jan 09, 2010 4:47 am Post subject: Re: Your opinion - wapati

lkSudoku · Posted: Sat Jan 09, 2010 9:12 am Post subject:

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

louwin · Posted: Sat Jan 09, 2010 11:37 pm Post subject: wapati is pathetic!

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 ****

louwin · Posted: Sun Jan 10, 2010 12:02 am Post subject: good idea lksudoku

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

lkSudoku · Posted: Sun Jan 10, 2010 8:12 pm Post subject:

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

humble_programmer · Posted: Tue Jan 12, 2010 1:54 am Post subject:

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
,,,^..^,,,

wapati · Posted: Tue Jan 12, 2010 5:37 am Post subject:

wapati · Posted: Tue Jan 12, 2010 7:32 am Post subject: Re: wapati is pathetic!

louwin · Posted: Tue Jan 12, 2010 11:08 am Post subject: Apology accepted

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.