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   

rating puzzles with brute force -question

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

Joined: 08 Apr 2006
Posts: 40
:

Items
PostPosted: Tue Dec 09, 2008 6:21 pm    Post subject: rating puzzles with brute force -question Reply with quote

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
View user's profile Send private message
cardinal

Joined: 08 Apr 2006
Posts: 40
:

Items
PostPosted: Mon Dec 22, 2008 7:18 am    Post subject: Reply with quote

noahbody ? :(
that means i didn't make my point ? :?
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Mon Dec 22, 2008 1:32 pm    Post subject: Reply with quote

cardinal wrote:
noahbody ? Sad
that means i didn't make my point ? Confused

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
View user's profile Send private message
cardinal

Joined: 08 Apr 2006
Posts: 40
:

Items
PostPosted: Tue Dec 23, 2008 7:06 am    Post subject: Reply with quote

OK, but what do you think ? subjective, it is OK to rate brute force multiple times ?
once should be enough, imho
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Tue Dec 23, 2008 7:54 am    Post subject: Reply with quote

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
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Sat May 16, 2009 10:45 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Wed Oct 21, 2009 11:39 pm    Post subject: Reply with quote

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
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Thu Oct 22, 2009 6:05 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Thu Oct 22, 2009 11:03 am    Post subject: Reply with quote

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
View user's profile Send private message
wapati

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

Items
PostPosted: Thu Oct 22, 2009 7:50 pm    Post subject: Reply with quote

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
View user's profile Send private message
wapati

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

Items
PostPosted: Thu Oct 22, 2009 7:55 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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