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

Question

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 ?

Answer 1

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.

Answer 2

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 "

Answer 3

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.