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:
- Perhaps $\overline{k}\vec{p}$ would yield an elementary difficulty scale.
- 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!]
