NP-complete puzzles difficulty

The Game Room
#1

Sudoku, Cross Sums, Minesweeper, Slitherlink, Sokoban, etc.

You know them, maybe love them, possibly hate them. Guaranteed to waste an arbitrary amount of time.

My question is: is there a general difficulty rating system for this category of puzzles? I mean an algorithm such that, given a particular Sudoku or Cryptarithm, the computer will respond that the instance is, e.g., “medium-hard”, and that this rating more or less means something across different types of puzzles?

I am aware of Ercsey-Ravasz and Toroczkai’s Sudoku rating system, which should extend to other puzzles as well, but do newspaper editors actually use such a system, and, if so, how does it correspond to readers’ experiences? If not, who decides how hard a particular puzzle is, using what criteria?

#2

I used to contribute logic puzzles to Dell and PennyPress and found their difficulty ranking to be defective. For example, a 7-item puzzle can be harder than a 10-item puzzle if the clues are carefully formulated and pruned, but the larger puzzle may seem more difficult. I spent considerable time honing the detailed solutions, finding shortcuts to reduce word-count. All that effort was counter-productive since the number of “stars” a puzzle gets may be proportional to the word-count in the detailed solution and the puzzle composer is paid $25 per star! (Dell’s 5-star logic puzzles are ridiculously difficult.)

I tried to make my puzzles hilarious and lost interest in the whole thing after I bought a magazine and saw what the editor was doing to them. My “Seven dwarfs and their seven felonies” became “Seven old ladies have seven different hat colors.”

#3

If they’re going to be changing them that much, then why even pay developers? Just use a computer program to automatically come up with puzzles.

#4

Even if that software were free (and in fact it doesn’t exist at all), you’d need a human operator to drive it through its paces. And the detailed English solutions take much more effort than the actual puzzles. Why pay for all that when you can get retired hobbyists to do it for a mere $25 per “star.” :slight_smile:

ETA: I used my own software to assist in puzzle construction and verification. I think at one point I asked the editress if she had any interest in that. “No,” was the answer.