FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    rating puzzles with brute force -question          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message cardinal Joined: 08 Apr 2006 Posts: 40 : Items Posted: Tue Dec 09, 2008 6:21 pm    Post subject: rating puzzles with brute force -question I'm puzzled :) by something, what is the point in rating puzzles with brute force ? actually, AFTER using brute force? I mean, when all nonrecursive techniques have failed, and the last hope is using brute force, the puzzle is solved, why chose to reveal just one clue, and continue as usual ? with nonrecursive techniques? how you chose the clue that is revealed ? because the subsequent nonrecursive steps depend on this choice. for example, for this puzzle, rated 9957 in sudocue, the brute force is called 7 times ...3.9.7. 8..4..... 1........ 2..5..6.. .3.....4. ....1.... 5.....8.. ....2.1.. ...7....9 that's why the big rating, but just the first call solved it already. and i think that just the first call should count towards the rating hope i made my point Back to top cardinal Joined: 08 Apr 2006 Posts: 40 : Items Posted: Mon Dec 22, 2008 7:18 am    Post subject: noahbody ? :( that means i didn't make my point ? :? Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Mon Dec 22, 2008 1:32 pm    Post subject: cardinal wrote: noahbody ? that means i didn't make my point ? If you cross the Alps by taking one of a series of passes, is the difficulty determined by the height of the highest pass or by some combination of all their altitudes? These things are subjective. There are various ways of measuring the difficulty of a puzzle, all of them valid. Yer pays yer money and yer takes yer choice! Regards, Mike Metcalf Back to top cardinal Joined: 08 Apr 2006 Posts: 40 : Items Posted: Tue Dec 23, 2008 7:06 am    Post subject: OK, but what do you think ? subjective, it is OK to rate brute force multiple times ? once should be enough, imho Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Tue Dec 23, 2008 7:54 am    Post subject: cardinal wrote: OK, but what do you think ? I think that difficulty cannot be expressed as a single number. Regards, Mike Metcalf Back to top lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Sat May 16, 2009 10:45 am    Post subject: I think that before brute force is used you should try solving by compilcated logical methods, if no logical method can solve the puzzle, the puzzle may be rated by the number of times guessing was required However, I personally, preffer to play with puzzles that can be solved logically, if there is no logical solution and guessing is required, I do not find the puzzle as interesting You may choose to discard puzzles with no logical solution Back to top sudoking Joined: 20 Oct 2009 Posts: 40 : Items Posted: Wed Oct 21, 2009 11:39 pm    Post subject: lkSudoku wrote: I think that before brute force is used you should try solving by compilcated logical methods, if no logical method can solve the puzzle, the puzzle may be rated by the number of times guessing was required There's another aspect to rating puzzles that I'd love to implement in code, if I had the time. Something that takes into account the number of possible moves at any given time. A minimal puzzle with only one initial move is obviously harder than one with several possible moves, yet most puzzle raters will not take this into account. Here's a method I've used to rate very difficult puzzles (it only works with very difficult puzzles). Firstly, I pass the puzzle though a logical solver that will solve all but the hardest of puzzles. It uses all the standard human techniques, up to fishes. It also uses a method I call copy-comparison. It's rather complex, but it basically compares the results of applying each of the candidates for a particular cell, and applies any common results. After that, only the very hardest of puzzles will be unsolved. So, I look at the number of candidates remaining in each cell, assigning each a value. If the cell is solved, it's worth 0. If the cell has n candidates, it's worth n^2. I then add all these up, and divided by the number of empty cells in the original puzzle. Anything over about 15 is pretty good. The highest I've seen is the Platinum-Blonde, which scored 18.7833. Obviously, there's a lot that this method doesn't take into account. Quote: However, I personally, preffer to play with puzzles that can be solved logically, if there is no logical solution and guessing is required, I do not find the puzzle as interesting You may choose to discard puzzles with no logical solution I don't believe there is such a thing as a puzzle without a logical solution. Back to top lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Thu Oct 22, 2009 6:05 am    Post subject: Quote: If the cell has n candidates, it's worth n^2 The difficulty of the cell is not always in correspondence with the number of candidate values; suppose you have a cell with 2 candidates, where after you guess one value all the puzzle is solved with simple logical methods, and when guessing the other you get an error from the beginning, comparing to another cell with two values in which whatever value you are guessing, all logical methods lead to another guess; in such case, the difficulty does not seem to be the same although your grading value assigns the same value to the two cases Back to top sudoking Joined: 20 Oct 2009 Posts: 40 : Items Posted: Thu Oct 22, 2009 11:03 am    Post subject: lkSudoku wrote: Quote: If the cell has n candidates, it's worth n^2 The difficulty of the cell is not always in correspondence with the number of candidate values; suppose you have a cell with 2 candidates, where after you guess one value all the puzzle is solved with simple logical methods, and when guessing the other you get an error from the beginning, comparing to another cell with two values in which whatever value you are guessing, all logical methods lead to another guess; in such case, the difficulty does not seem to be the same although your grading value assigns the same value to the two cases Agreed, however, such a case is unlikely to exist, as the semi-solver would most likely be able to solve such a puzzle. But this grading method does correlate reasonably well with others I've compared it too. Does anyone have some C source code for a decent puzzle rater which I can use to compare my results? (Even though "decent" may be quite arbitrary in this case.) Back to top wapati Joined: 12 Jun 2007 Posts: 622 : Location: Canada Items Posted: Thu Oct 22, 2009 7:50 pm    Post subject: lkSudoku wrote: I think that before brute force is used you should try solving by compilcated logical methods, if no logical method can solve the puzzle, the puzzle may be rated by the number of times guessing was required However, I personally, preffer to play with puzzles that can be solved logically, if there is no logical solution and guessing is required, I do not find the puzzle as interesting You may choose to discard puzzles with no logical solution Numerically, our logical methods increase with time. Back to top wapati Joined: 12 Jun 2007 Posts: 622 : Location: Canada Items Posted: Thu Oct 22, 2009 7:55 pm    Post subject: If you run out of methods and hit brute force: I think the key factor is the number of shortest step brute forces required. You should consider that picking one of two is easier than one of 5. Secondary, but a factor, is the # of candidates in the key cells. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming 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