Author 
Message 
paulv66
Posted on: Tue Jan 03, 2017 10:10 pm
Posts: 346 Joined: Tue Mar 01, 2016 10:03 pm

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




jpoos
Posted on: Tue Jan 03, 2017 11:00 pm
Posts: 126 Joined: Sun Nov 03, 2013 10:28 pm

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 )




paulv66
Posted on: Wed Jan 04, 2017 12:34 am
Posts: 346 Joined: Tue Mar 01, 2016 10:03 pm

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.




paulv66
Posted on: Wed Jan 04, 2017 12:41 am
Posts: 346 Joined: Tue Mar 01, 2016 10:03 pm

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.




pnm
Posted on: Wed Jan 04, 2017 12:52 am
Posts: 2335 Joined: Thu May 12, 2011 11:58 pm

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=195but 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.




jpoos
Posted on: Wed Jan 04, 2017 2:10 pm
Posts: 126 Joined: Sun Nov 03, 2013 10:28 pm

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 What am I doing wrong here?




jaek
Posted on: Wed Jan 04, 2017 2:49 pm
Posts: 233 Joined: Fri Jun 17, 2011 8:15 pm

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 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?




jpoos
Posted on: Wed Jan 04, 2017 3:44 pm
Posts: 126 Joined: Sun Nov 03, 2013 10:28 pm

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 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 averagingpart wrong...




paulv66
Posted on: Wed Jan 04, 2017 3:51 pm
Posts: 346 Joined: Tue Mar 01, 2016 10:03 pm

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 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




jpoos
Posted on: Wed Jan 04, 2017 4:35 pm
Posts: 126 Joined: Sun Nov 03, 2013 10:28 pm

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.




