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   

developing a level of difficulty

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

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Mon Jun 01, 2009 4:44 pm    Post subject: developing a level of difficulty Reply with quote

Hi,
From the help of this forum, I was able to understand the basic concept of how to create a generator/solver Sudoku puzzle. I got my resources from a member here at the forums who posted a link to an example of a brute force generator/solver in C, which you can find here http://users.telenet.be/mpq/sudoku/random_sudoku_generator.c

Afterwards, I was able to successfully accomplish the generator/solver, and I am now ready to implement a level of difficulty to the puzzle. I have tried searching the forums for help, but I am difficulties understanding what the other members have said when helping others out.

eg. here is one from another post
Quote:
You have to make difficulty measureable, for example by assigning a score to each step in the solving path. Advanced techniques score high and basic techniques score low. Setting the thresholds depends on the audience you want to serve. For the average puzzler, a sudoku with X-Wings is very hard, but advanced players consider this a basic technique. You could generate some puzzles with different scores and have them tested, so that you can use the feedback to set the limits.

Ruud


What does Ruud mean by "each step in the solving path?" Is this in terms of how many cells where a "1, 2, 3, or etc" can be placed at?

What are advanced and basic techniques?

... anywho, besides the confusion, the original poster posted this...

Quote:
Posted: Sat Feb 10, 2007 6:47 am Post subject:

--------------------------------------------------------------------------------

thnx Ruud... I think we'll introduce that on our site!

However this still leaves the question: What determines the difficulty of the sudoku (most)... the advancedness of the needed techniques, the number of needed thechniques or the the number of iterations the solver has to do before it reaches a solution?

What makes it more difficult: When a human no longer sees any logic, he (she) will guess and guessing may be easier than the advanced technques, so how should guessing be rated?

Regards
Arnold


.. and then no one else replied back since.

I am still very lost. Can someone help me out?
Back to top
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Mon Jun 01, 2009 6:12 pm    Post subject: Reply with quote

Generally, the level of difficulty is defined by the methods that are required to solve a puzzle

Difficulty is subjective, thus different players may consider different difficulty to the same method and puzzle

The way my sudoku generator, lkSudoku determines the difficulty is as follows:

I have created a solver that uses some logical algorithms to solve a puzzle; in addition, I have categorized different algorithms with different difficulties. To determine a puzzle difficulty, I solve it with different algorithms, and the algorithms that solve it, while the algorithms of previous difficulty do not solve it, determine its difficulty

Others may choose difficulty by considering also the number of times a difficult method was used and assigning a score to each solution step
Back to top
View user's profile Send private message Send e-mail
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Mon Jun 01, 2009 8:27 pm    Post subject: Reply with quote

IkSudoku,
Quote:
Generally, the level of difficulty is defined by the methods that are required to solve a puzzle


from the above quote you mentioned, the problem is that I do not know the name of the method I am using, since the original code was not mine. What I did was, first I copied the code onto my friend's computer that has a C/C++ complier. I then ran the program in debug mode and watched how the code solved the puzzle. Then once I had the basic idea, I converted the code to work with the scripting language I am using, which is Director 8.5, it is sort of like Flash.

By running the original code in debug mode on my friend's computer, what I think it is doing, is this...

1. start with an empty grid

2. randomize the unsolved cells

3. start solving the empty grid by solving the random cells that have less possible numbers then the current cell that the loop is pointing to

4. while continuing through the loop of the 81 cells, and if there are no possible numbers left in the current cell, then backtrack to the last cell that does contain multiple possible numbers.

5. When the grid has been filled, then conceal 58 cells by....

5a. continuing to conceal a pair of cells in a 180 degree rotation fashion, until it reaches 58 concealed cells. eg. if you are concealing cell 20 then you would also conceal cell 61

5b. for each concealed pair, check for uniqueness by

5b-1 First solve all concealed cells who's cells only have one possible number

5b-2 When there are no more single possible numbers, use the same solver method that are in steps 3 and 4

5c. when thats finished, it will either result in a single solution or multiple solutions.

5d. if there are multiple solutions, then replace the previous concealed paired cells and try the next pair.

6. The entire process will be finished when, 58 concealed cells produce a single solution.

So what method would this be called and what part of this solver detirmines the level of difficulty?

I am thinking the level of difficulty should be detimend by the amount of multiple possible numbers it encouters itself in a row, column, or region.

For example,
you are trying to find out where the 5 goes in reagion 1, but you cannot figure it out because the 5 could go inside of cells 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 20, 29, or 38. If this happens to the 6 and the 8 as well, then I would think this would make it a harder puzzle. Wouldn't you think so?
Back to top
View user's profile Send private message
wapati

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

Items
PostPosted: Mon Jun 01, 2009 9:08 pm    Post subject: Reply with quote

BigPapa wrote:
IkSudoku,
Quote:
Generally, the level of difficulty is defined by the methods that are required to solve a puzzle


from the above quote you mentioned, the problem is that I do not know the name of the method I am using, since the original code was not mine.


Pretty much you have a brute force solver that can solve any valid puzzle but has no concept of human solving steps.

There is no reasonable way to go from that to using human steps.
Human steps are what matters for difficulty rating.

You are at the wrong end of solvers for establishing a rating for a puzzle,
unless you mean some least steps possible algorithm?
Back to top
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Mon Jun 01, 2009 9:32 pm    Post subject: Reply with quote

Quote:
5b-1 First solve all concealed cells who's cells only have one possible number

You may consider this step as a solving algorithm
Quote:
5b-2 When there are no more single possible numbers, use the same solver method that are in steps 3 and 4

And this step as another algorithm

If the first algorithm finds the full solution, then this is a simpler puzzle than a puzzle that can only be solved by the second method

If you implement more methods, between the first 5b-1 and the second 5b-2 methods, you could refine the difficulty level

Regarding the amount of multiple possible numbers in a row, column, or region, there can probably be example puzzles where this criteria does not correspond with the method difficulty required for a puzzle solution
Back to top
View user's profile Send private message Send e-mail
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Tue Jun 02, 2009 1:45 am    Post subject: Reply with quote

wapati wrote:

... unless you mean some least steps possible algorithm?


Yes, I think that is what I mean. Here is what I see what has happend when I, meaning I as the player, tried solving a generated puzzle from the code. What I did was, in Director, you can save arrays as a text string, Doing so, this allowed me to replay the same puzzle over and over again. Now because the puzzle was a little difficult for me, since I am a beginner, I noticed things like this...

1 x x | 3 4 7 | 8 9 2
3 x x | 9 2 1 | 4 x x
x x x | x x x | x x x
---------------------
x 9 x | x x x | x x x

as you can see, this is not a full grid but partial example of what might happen) you will see what I mean in my description.
In row 1 the 5 could go in column 2 or 3, and in row 2 the 5 could go in column 2, 3, 8, or 9. However, this example would of been easier if the 9, in row 2 column 4, was a 5 instead like so...

1 x x | 3 4 7 | 8 9 2
3 x x | 5 2 1 | 4 x x
x x x | x x x | x x x
---------------------
x 9 x | x x x | x x x

Now, I do not mean lets throw away this puzzle, but I just think the first example should be categorized as a harder puzzle than the last example.


wapati wrote:

Pretty much you have a brute force solver that can solve any valid puzzle but has no concept of human solving steps.

There is no reasonable way to go from that to using human steps.
Human steps are what matters for difficulty rating.


Oh, there are solvers that can do human solving steps from an empty grid?
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Jun 02, 2009 10:06 am    Post subject: Reply with quote

BigPapa wrote:
Here is what I see what has happend when I, meaning I as the player, tried solving a generated puzzle from the code. What I did was, in Director, you can save arrays as a text string, Doing so, this allowed me to replay the same puzzle over and over again. Now because the puzzle was a little difficult for me, since I am a beginner, I noticed things like this...

1 x x | 3 4 7 | 8 9 2
3 x x | 9 2 1 | 4 x x
x x x | x x x | x x x
---------------------
x 9 x | x x x | x x x

as you can see, this is not a full grid but partial example of what might happen) you will see what I mean in my description.
In row 1 the 5 could go in column 2 or 3, and in row 2 the 5 could go in column 2, 3, 8, or 9. However, this example would of been easier if the 9, in row 2 column 4, was a 5 instead like so...


Since number 5 in row 1 can only be at column 2 or 3, number 5 cannot appear anywhere else in that box. We call that a locked candidate. Therefore number 5 in row 2 can only be at column 8 or 9
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Jun 02, 2009 12:08 pm    Post subject: Reply with quote

For more info about, and an overview of, most known 'human' solving techniques, I can recommend you the following website: http://www.scanraid.com/sudoku.htm
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Tue Jun 02, 2009 3:47 pm    Post subject: Reply with quote

Lunatic wrote:


Since number 5 in row 1 can only be at column 2 or 3, number 5 cannot appear anywhere else in that box. We call that a locked candidate. Therefore number 5 in row 2 can only be at column 8 or 9


LOL, I knew someone would eventually find something wrong with my demostration. When I get a chance, I will take more time out to draw out a better scenario. The reason for this is because I am still stuck on something that I cannot explain without showing you with a drawing
Back to top
View user's profile Send private message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Tue Jun 02, 2009 6:53 pm    Post subject: Reply with quote

Ok,
I have an idea that I think might work, but I have one problem. What I will need is to create a unique puzzle every time, until I have exhausted every possible unique puzzle there can be generated. Is this possible using a brute-force generator, and should I be asking this in the programming sudoku forum on how to do it?
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