FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    developing a level of difficulty          Sudoku Programmers Forum Index -> Setting sudoku View previous topic :: View next topic   Author Message BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Mon Jun 01, 2009 4:44 pm    Post subject: developing a level of difficulty 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 lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Mon Jun 01, 2009 6:12 pm    Post subject: 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 BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Mon Jun 01, 2009 8:27 pm    Post subject: 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 wapati Joined: 12 Jun 2007 Posts: 622 : Location: Canada Items Posted: Mon Jun 01, 2009 9:08 pm    Post subject: 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 lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Mon Jun 01, 2009 9:32 pm    Post subject: 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 BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Tue Jun 02, 2009 1:45 am    Post subject: 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 Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Tue Jun 02, 2009 10:06 am    Post subject: 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 Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Tue Jun 02, 2009 12:08 pm    Post subject: 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 BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Tue Jun 02, 2009 3:47 pm    Post subject: 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 BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Tue Jun 02, 2009 6:53 pm    Post subject: 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Setting sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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