View unanswered posts | View active topics It is currently Thu Mar 28, 2024 10:43 pm



← Back to the Calcudoku puzzle page




Reply to topic  [ 15 posts ]  Go to page 1, 2  Next
 Meanings of puzzle ratings 
Author Message

Posted on: Tue Jan 03, 2017 10:10 pm




Posts: 956
Location: Ukraine
Joined: Tue Mar 01, 2016 10:03 pm
Post Meanings of puzzle ratings
Most of the puzzles have a value assigned to them. For example, today's 9x9 has a rating value of 111.3 and has been allocated 6 stars. What does the rating value represent and what's the highest rating ever for a puzzle on this site?

PaulV


Profile

Posted on: Tue Jan 03, 2017 11:00 pm




Posts: 158
Joined: Sun Nov 03, 2013 10:28 pm
Post Re: Meanings of puzzle ratings
Patrick wrote a paper (http://www.calcudoku.org/papers/choice_ ... _v1.01.pdf) in which he described what the rating means:
'The difficulty of a puzzle is estimated by averaging the natural logarithm of the number of possible permutations for each row and each column (after applying the restrictions imposed by each cage)'. In the paper he also gives a few examples.
I'm still a bit puzzled as to what this actually means: since the restrictions imposed by all the cages in the puzzle give you a unique solution, doesn't every row/column have only one possible permutation? (which would mean that every puzzle gets a rating of 0 [confused] )


Profile

Posted on: Wed Jan 04, 2017 12:34 am




Posts: 956
Location: Ukraine
Joined: Tue Mar 01, 2016 10:03 pm
Post Re: Meanings of puzzle ratings
Thanks jpoos. Interesting paper, but I couldn't find the reference to the rating system and how it is calculated.


Profile

Posted on: Wed Jan 04, 2017 12:41 am




Posts: 956
Location: Ukraine
Joined: Tue Mar 01, 2016 10:03 pm
Post Re: Meanings of puzzle ratings
paulv66 wrote:
Thanks jpoos. Interesting paper, but I couldn't find the reference to the rating system and how it is calculated.


I just did what I should have done initially and did a search on the document. I kind of agree with you as I'm not sure I understand the logic due to the fact that there is an unique solution to each puzzle, which seems to imply that each puzzle has only one possible solution and therefore all puzzles are equally difficult - which clearly makes no sense.


Profile
User avatar

Posted on: Wed Jan 04, 2017 12:52 am




Posts: 3296
Joined: Thu May 12, 2011 11:58 pm
Post Re: Meanings of puzzle ratings
This question comes up every now and then.

With some effort I tracked down one thread about it:

viewtopic.php?f=2&t=195

but I'm sure there must be more.

I'll do some more digging..


Edit:
> 'The difficulty of a puzzle is estimated by averaging the natural logarithm of the number of possible permutations
> for each row and each column (after applying the restrictions imposed by each cage)'.

The key here is that the number of options for a single cell is determined by _only_ looking at the cage.


Profile

Posted on: Wed Jan 04, 2017 2:10 pm




Posts: 158
Joined: Sun Nov 03, 2013 10:28 pm
Post Re: Meanings of puzzle ratings
pnm wrote:
The key here is that the number of options for a single cell is determined by _only_ looking at the cage.


That still leaves it a bit unclear to me. Could you give an example?

I also just realised the following: if we take a n by n puzzle, the number of permutations for a row/column can at max only be n!, so the rating can at max be ln(n!), right? Well, many puzzles exceed this limit [confused] [confused] What am I doing wrong here?


Profile
User avatar

Posted on: Wed Jan 04, 2017 2:49 pm




Posts: 300
Joined: Fri Jun 17, 2011 8:15 pm
Post Re: Meanings of puzzle ratings
jpoos wrote:
pnm wrote:
The key here is that the number of options for a single cell is determined by _only_ looking at the cage.


That still leaves it a bit unclear to me. Could you give an example?

I also just realised the following: if we take a n by n puzzle, the number of permutations for a row/column can at max only be n!, so the rating can at max be ln(n!), right? Well, many puzzles exceed this limit [confused] [confused] What am I doing wrong here?


If the cell's values are only determined by the cage it belongs to, then that 'history' won't carry over to the next cell/cage, right? So, is the max
ln(n) * n * n?


Profile

Posted on: Wed Jan 04, 2017 3:44 pm




Posts: 158
Joined: Sun Nov 03, 2013 10:28 pm
Post Re: Meanings of puzzle ratings
jaek wrote:
jpoos wrote:
pnm wrote:
The key here is that the number of options for a single cell is determined by _only_ looking at the cage.


That still leaves it a bit unclear to me. Could you give an example?

I also just realised the following: if we take a n by n puzzle, the number of permutations for a row/column can at max only be n!, so the rating can at max be ln(n!), right? Well, many puzzles exceed this limit [confused] [confused] What am I doing wrong here?


If the cell's values are only determined by the cage it belongs to, then that 'history' won't carry over to the next cell/cage, right? So, is the max
ln(n) * n * n?


In my logic that would give a max of ln(n^n), which still leaves puzzles that exceed this rating...
I'm pretty sure I'm interpreting the averaging-part wrong...


Profile

Posted on: Wed Jan 04, 2017 3:51 pm




Posts: 956
Location: Ukraine
Joined: Tue Mar 01, 2016 10:03 pm
Post Re: Meanings of puzzle ratings
jpoos wrote:
pnm wrote:
The key here is that the number of options for a single cell is determined by _only_ looking at the cage.


That still leaves it a bit unclear to me. Could you give an example?

I also just realised the following: if we take a n by n puzzle, the number of permutations for a row/column can at max only be n!, so the rating can at max be ln(n!), right? Well, many puzzles exceed this limit [confused] [confused] What am I doing wrong here?


I think the maximum number of permutations would be n!^n. If this is correct, it would give the following maximum rating for each puzzle size from 4x4 to 12x12.

Size n! n!^n Rating
4 24 331776 12.71
5 120 24883200000 23.94
6 720 1.39314E+17 39.48
7 5040 8.26064E+25 59.68
8 40320 6.98496E+36 84.84
9 362880 1.09111E+50 115.22
10 3628800 3.95941E+65 151.04
11 39916800 4.09933E+83 192.53
12 479001600 1.459E+104 239.85

There must be something wrong with the above logic, as I know I've seen at least one 9x9 with a rating of 130+.

Paul


Profile

Posted on: Wed Jan 04, 2017 4:35 pm




Posts: 158
Joined: Sun Nov 03, 2013 10:28 pm
Post Re: Meanings of puzzle ratings
paulv66 wrote:
Size n! n!^n Rating
...
7 5040 8.26064E+25 59.68
...

There must be something wrong with the above logic, as I know I've seen at least one 9x9 with a rating of 130+.


If you want to be sure, todays 7x7 difficult also has a rating of 64.7.


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 15 posts ]  Go to page 1, 2  Next

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

Search for:
Jump to:  
cron
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.