Thoughts on creating a 'difficulty level' algorithm

I have created a word puzzle, and I'm interested in rating the puzzles by difficulty. There are nearly 2000 puzzles in my archive, so rating them by hand would be time-consuming and probably rather inconsistent, subjective.

Here's how the game works: https://gist.github.com/pgblu/1fa0dccd75ecba154776

Things I've noticed:

• 1a. The larger the ratio of known to unknown letters, the easier
• 1b. The more contiguous known letters you have, the easier
1. The more clue words you have (2 being the fewest), the easier
1. The larger the pool of 'candidate words' for any pattern, the harder
1. Finally, the more unusual the letters or patterns, the easier the puzzle (which is linked to #3 of course)
1. Having the first letter a 'known' letter makes the puzzle easier

Would anyone like to share their thoughts on designing a difficulty rating algorithm?

Easy puzzle:

• _ I M E _ _ _ _ _
• _ R A C _ _ _ _ _
• _ R E A _ _ _ _ _
• _ U R N _ _ _ _ _

Easy puzzle:

• _ _ _ F F _ _ I
• _ _ _ F F _ _ O
• _ _ _ P H _ _ E
• _ _ _ T U _ _ Y

Medium puzzle:

• C _ _ _ V _ _ E
• F _ _ _ B _ _ S

Hard puzzle:

• A _ _ _ _ _
• B _ _ _ _ _
• C _ _ _ _ _
• D _ _ _ _ _

Very hard puzzle:

• _ _ _ _ _ _ S
• _ _ _ _ _ _ T

solutions:

t...table, gra..it., .lea.ag., .erate, hideou. (the last one has more than one solution)

• My suggestion: Take three or four puzzles and guess what you'd set the difficulty as, then come up with an algorithm that hits those numbers for those puzzles and see what it looks like for the rest. Basically, work it backwards. – Bailey M Aug 3 '15 at 16:00
• Will you include a few of your puzzles so we can see them? Are they all roughly the same size? – JLee Aug 3 '15 at 16:19
• oh, ok. adding the answers helped, as now it makes more sense, seeing that one set of letters is applied to all lines! duh JLee! – JLee Aug 3 '15 at 16:53
• How many solutions there are and how hard it is to find one of them is not a perfect correlation, in my opinion. – pgblu Aug 3 '15 at 17:04
• I didn't know "cerate" and "derate" were words. – Joe Z. Aug 4 '15 at 5:52

So sorry for all the text you would have to read; I pity you. I also realize the paragraphs may not flow as much as they can, yielding a bit of a choppy feel. I apologize, and I hope to focus on creating a better flow at a later point. Here's a TL;DR:

I propose 4 methods, all of which are imperfect, as to be expected. 3 of them look similar.

I then endevour to use the cardinality of the solution set to modify a general method, along with respect to the possible solutions.

After, I publish a nice-looking chart that really was made with Microsoft© Excel© 2013&tm;.

Finally (for the moment), I use ETAONI HSRDLU WMCGFYBPVKXJQZ in tandem with possible solutions for a given line.

Here are my thoughts. Actually, my trial-and-error approach. Mainly, I'd use one or more of the formulas to find an easiest and hardest puzzle, then use a percent to indicate difficulty (e.g. 100% is easy, 21% is difficult).

Let $n$ be the number of lines, $b$ be the number of blanks per line, $g$ be the number of given letters per line, $c$ the number of distinct characters featured in a puzzle, and let $a$ be the average placement of a character in a line.

My approach states that the lower a puzzles score, the harder it is.

The product method: $nbg$

Based on the observation that, given more information, some problem will be easier.

Modified product method: $\dfrac{b(gn)^2}{c}$

Takes the previous product method multiplied by the character to distinct character ratio.

Über modified product method: $\dfrac{b(gn)^2}{ca}$

Based on the observation that letters in the first position yield easier puzzles, ergo, the closer the character to the end of a word, the tendency increases to yield harder puzzles.

The "I have run out of names for these methods please read on"-method: $n\left(\dfrac{g}{b}\right)^2$

Multiplying the lines by the ratio of given to blank numbers, based on the fact that more information is easier. Also note that the squaring bit is to put numbers closer to zero or further from $1$, depending if $0<k\leq 1$ ($k^2 \to 0$) or if $1\leq k<\infty$ ($k^2\to\infty$).

Example 3 on the GitHub has really gotten me thinking... perhaps a simple combination (or even a complex one, at that) is not enough to satisfy a difficulty test. So let $o$ be the number of solutions a given puzzle has, and let $q$ be the number of (sets of letters) that fulfill the puzzle in that they fail only in having another word being formed (as was the case in example 3). Then, let $M$ be some method/formula, either one here or some other method. We can more accurately portray method $M$ by modifying it as such:

$$\frac{oM}{f(q,x)}$$

for some variable $x$ and a function $f$. Now, what values best fit $x$ and $f$? I wish to put a higher significance on the fact that, if $q$ such pseudo-solutions exist, it will make the problem harder, regardless of there being $o$ solutions. If I set $f(q,x)=q^x$, I believe that it will skew the results of the problems hardness too much, as any $x\gg 1$ makes $q^x$ grow fast. Any $x\approx1$ with $x\notin\mathbb{Z}$ is undesirable, as this would make the algorithm tricky. But, if such was the contrary, that some $x\in\mathbb{R}$ was needed, then an $x$ for $f(q,x)=q^x$ could stand as $1<x\ll2$

Therefore, it will be useful to use a function that grows more slowly. This rules out $x^q$, $q!$, $^xq$, and pretty much anything that grows quicker. So, $f(q,x)=qx$. $x$ then is purely arbitrary.

Revised standards

I have compiled all the puzzles on the GitHub into a table. And currently, they all fall into the same problem: they generally work, but still classify some as easy that should be hard, etc. I must do some more work, and, until then, I will not have said data up.

Observations

(0 is Very Easy,..., 5 is Very Hard)

Idea number umpteen

ETAONI HSRDLU WMCGFYBPVKXJQZ! Alright, I'm not crazy, merely just “inspired”. The OP mentions that a puzzle like _ _ _ _ e _ is harder than a puzzle like _ _ _ _ z _. Therefore, if there are more words that could possibly match one line, then the puzzle earns a higher difficulty.

For this method, I will say that a higher number denotes a higher difficulty, and, likewise, a lower number denotes a lower difficulty. Let $k_i$ be the number of solutions that solve for just the $i$th line of the puzzle.

(I use this to get $k_i$)

Example: Let this be the puzzle (lines numbered):

0: _ y z y _ _
1: _ h a g _ _
2: _ c o d _ _

For line 0, $k_0=1$, as the only solution is the word syzygy. (Or so I believe; tell me if another word fits this!)

For line 1, $k_1=17$. (ᴜɴʟɪsᴛᴇᴅ)

And finally, for line 2, $k_2=3$. (ccodes, mcodes, and scodgy).

Now, how should we go about combining $k_i$? Shall we multiply it together, summate it, or perhaps some other function? Let us first observe, however, the $k_i$s for other puzzles. For fluidity and conciseness, I propose that $\overline{k}=\dfrac{\prod_{i=0}^{n}k_i}{n}$ (pronounced <k> bar) (the average of $k_0,...,k_n$).

0: _ I M E _ _ _ _ _  k_0 = 100
1: _ R A C _ _ _ _ _  k_1 = 163
2: _ R E A _ _ _ _ _  k_2 = 263
3: _ U R N _ _ _ _ _  k_3 = 99
k bar = 625 / 4 = 156.25

~

American Dictionary used from here on out.

0: _ _ _ F F _ _ I    k_0 = 1
1: _ _ _ F F _ _ O    k_1 = 1
2: _ _ _ P H _ _ E    k_2 = 43
3: _ _ _ T U _ _ Y    k_3 = 10
k bar = 55 / 4 = 13.75

These puzzles, however, were both on the easy side; not only does $\overline{k}$ contradict our supposition that higher numbers indicate higher difficulties (unless if we find more evidence to the contrary), but also the fact that two easy puzzles yield such different $\overline{k}$s is astounding.

So I will observe a very hard puzzle, in hopes that it would yield a high $\overline{k}$.

0: _ _ _ _ _ _ S    k_0 = 7677
1: _ _ _ _ _ _ T    k_1 = 1258
k bar = 8935 / 2 = 4467.5

In light of the previous results, the gap between the first two $\overline{k}$s decreases drastically. I will also conjecture that, for every/most puzzle line ending with S of length $m$ with $b$ blanks, $k_i\ggg (mb)^2$, if $m$ is sufficiently large and $b$ sufficiently small.

But how does ETAONI HSRDLU WMCGFYBPVKXJQZ fit in? Well, if you haven't noticed already, this is the frequency that a letter appears in a word. Let $p_{j,i}$ be the index of the $i$th letter in the $j$th line of a puzzle. $\overline{p_j}$ is the averages of $p_{j,i}$ for line $j$, and $\vec{p}$ is the averages of all $\overline{p_j}$s for the puzzle.

(Not fully developed) ideas:

1. Perhaps $\overline{k}\vec{p}$ would yield an elementary difficulty scale.
2. The implementation of $\overline{k}$ would be especially difficulty from a programatical point of view, requiring the use of an outside dictionar(ies). If you can do that, however, I believe that $\overline{k}$ would be a valuable asset in determining the difficulty of your puzzle; furthermore, this seems to be the only difficulty I can foresee in algorithm implementation.

[WIP still!]

• +1 for "I have run out of names for these methods please read on"-method: n(gb)2 – Going hamateur Aug 4 '15 at 12:17
• I will update the linked gist with more examples, stand by. – pgblu Aug 4 '15 at 14:04
• I've put a larger sample in the gist. Note that the border between 'hard' and 'medium' might be a bit soft... but your idea of a numeric scale is strongly preferred anyway. P.S., best to read a 'raw' version of the gist, my Markdown is a bit funky. – pgblu Aug 4 '15 at 17:04
• @pgblu Thank you, I will put the puzzles through each of my current methods and revise. This is a fun little project :D I love the puzzles, too! – Conor O'Brien Aug 4 '15 at 17:07
• I don't think we can realistically expect a difficulty algo that will satisfy everyone, but a rough one that's at least not marking tough puzzles as dead easy would be way better than what I currently have. – pgblu Aug 4 '15 at 17:10

Machine Learning

If you are willing to spend a little time formatting your data, this could be a great opportunity for a machine learning algorithm.

Why

Basically, the idea is that given some training set, you can create a model that will place new data points in the proper category. The appeal of a machine learning method is that you don't have to define what makes a problem easy or hard. You simply give it a few pre-defined problems to start with and it implicitly determines what is most important. So if you want N categories, I would say pick at least 5 samples for each. So 5 puzzles you have already decided are easy, 5 that are medium, etc...

Data

You can include any data you think might be relevant, adding extra almost never hurts. So for each puzzle, include all the metrics you have listed in your question. Add anything else you want that can be quantified.

Implementation

Python is maybe the easiest to code this in. Checkout scikit. There are a couple easier programs with GUIs if you prefer, I want to say GraphLab might be one?

• Why does it have to be Python? Machine learning can be implemented in any language as far as I know. – dennisdeems Aug 6 '15 at 17:35
• @dennisdeems That's true, I just think Python seems like it has the best libraries for the job. Like for Java, Hadoop is the goto library, and it's realllly involved to make anything run. With python, you can pretty quickly get a result, and with ipython notebook you can even visualize it easily. – Cain Aug 6 '15 at 17:39