In the Undead Game, what makes one board more difficult than another?

In the Undead Game, what makes one board more difficult than another?

The game is defined like this:

1. A 4x4 (or 5x5, etc) grid has some random squares filled with diagonal lines representing mirrors.
2. The grid has numbers added on both ends of the rows and the columns, indicating how many undead you will see if you look straight (horizontally/vertically) into the grid from that point.
3. You are provided with a set number of zombies, ghosts, and vampires, with the following properties:
1. Zombies can always be seen when they are in your line of sight (which extends along the reflection-paths of the mirrors
2. Vampires can only be seen if they are directly in your line of sight, but cannot be seen through a mirror
3. Ghosts cannot be seen when they are directly in your line of sight, and can only be seen via a mirror.
4. Your task is to place the given undead into the empty squares of the grid so that every number around the outside accurately describes the number of undead seen from that point.

An image to help with visualization:

I want to understand what decides the level of difficulty in this game, aside from grid size. For example, the linked website offers 4x4 Easy, 4x4 Normal, and 4x4 Tricky options.

I have written some code to generate a game board and I can generate thousands of 4x4 games by selecting random values for each cell. How do I assign a difficulty to them ?

Is there a way I can do it by just looking at the board ?

• As a regular on Puzzling, I think this question first needs some fleshing out to be on-topic. How does the puzzle work? What are your your observations of what makes some puzzles more difficult than others? Why are your interested in this -- is it just curiosity, or is this to use in a program you're writing?
– xnor
Commented Jul 15, 2015 at 7:07
• Can you describe the rules of the puzzle so we don't need to click a link (that might eventually die)? Commented Jul 15, 2015 at 20:18
• I like the game idea. You could add phantoms:visible in straight line direction (ignoring mirrors) bit only behind at least one mirror... Commented Jul 17, 2015 at 8:59
• To clarify - can you see through/past a mirror into the next square? And can you have a monster in the same square as a mirror? If the latter answer is yes, does it matter which side of the mirror the monster is on, or are they considered a superposition of sorts? Commented Jul 17, 2015 at 10:11
• Answered my own question, I think - you can't see through a mirror, and a mirror can't share with a monster. Solution for the above puzzle: [m,v,v,g][z,v,m,m][m,m,g,v][g,m,m,m], where m is mirror, v is vampire, g is ghost and z is zombie. Also, you count a creature twice if you see it twice Commented Jul 17, 2015 at 10:39

I don't think there's any hard-and-fast way to rank the boards, but here are a few thoughts.

Let $z =$ the number of zombies.
Let $g =$ the number of ghosts.
Let $v =$ the number of vampires.
Let $n =$ the size of the board ($n=4$ indicates a 4 $\times$ 4 board).
Let $s =$ the sum of all the numbers around the edges of the board.
Let $m =$ the number of mirrors on the board.

• As $(g+v)/z$ increases (there are more ghosts/vampires and less zombies), the difficulty will increase as well. This is because ghosts and vampires have two different "states", while zombies have only one (always visible).
** Note that if $g = 0$ or $v = 0$ then there will be a point where the difficulty decreases again, since a board with all ghosts and one zombie is probably easier to solve than a board with several of each. (All you have to do is figure out where to put the one zombie.)

• You could use the sum of the numbers around the board as a potential metric, though it wouldn't be perfect. On a 4$\times$4 grid, a board with all $0$s (total $=0$) is trivial, as is a board with all $4$s (total $=64$). So I might try something like $32 - |(32 - s)|$, or, to generalize for any board size: $\frac{4n^2}2 - \left|\frac{4n^2}2 - s\right|$.

• You could count the number of mirrors on the board, which would end up providing a very similar metric to my second point above, because both a board with no mirrors and a board with all mirrors will both be trivial to solve. Thus you could use a similar equation: $n^2 - | n^2 - m|$

An overall metric could combine these different observations (and weight them accordingly) to try to rank the difficulty of each board:

Let $w_1 =$ the weight for the first metric.
Let $w_2 =$ the weight for the second metric.
Let $w_3 =$ the weight for the third metric.
Let $d =$ the overall difficulty of the board.

Then you could use an equation like

$d = w_1(\frac{g+v}z) + w_2(\frac{4n^2}2 - \left|\frac{4n^2}2 - s\right|) + w_3(n^2 - | n^2 - m|)$

to rank the difficulty of the board.

It probably won't be perfect, but it might at least give you a starting point.

I got in touch with the the owner of the puzzle page and here is his reply:

" I had to look this up myself in the source code (Undead was submitted by another developer, not written by me). Apparently the effects of the difficulty level setting are:

• constrain the maximum length of a line of sight. At easier difficulty levels, the game avoids really long twisty reflected lines.

• adjust the proportion of sight-lines which are deliberately arranged to have obvious unique solutions. Those are filled in first, and then the rest of the monsters chosen at random.

• at Tricky difficulty, enforce that there's more than one monster of every type.

• finally, the grid is put through a solver to ensure the solution is unique, and some statistics from the solver are recorded. Most noticeably, the 'iterative depth', which as far as I can see is defined as the longest chain of deductions (in the sense that each deduction can't be made until you take into account the result of the previous one) needed to solve the puzzle. If the puzzle doesn't have a unique solution or the iterative depth is not appropriate for the difficulty level, it's thrown away and generation is restarted.

Cheers, Simon "

While not optimal, there is also the opportunity to rank empirically. If you store past games and the time it took to solve and the success rate, then you can build a database from there. If the game is on a social platform and played by many, this will eventually be the most accurate rating. Of course that doesn't help at the start....

Btw, are solutions unique? Otherwise the amount of possible solutions can reciprocally add to the difficulty rating.

• The solutions are not unique so the number of possible solutions will also be a factor. Commented Jul 21, 2015 at 22:23