Can You Find The Best Dungeons & Dragons Strategy?

Riddler Express

You sit down to a sudoku and notice the grid is oddly sparse: only a handful of numbers are filled in. No number repeats in any row, column or three-by-three box, so no rule is broken outright, yet the puzzle is impossible to complete. What is the smallest possible sum of the initial numbers in such a grid? (Repeated numbers count separately: a grid of eight 4s and two 5s would sum to $42$.)

The Riddler, FiveThirtyEight, May 15, 2020(original post)

Solution

To make a legal-looking grid unfillable as cheaply as possible, force one cell to need a value it cannot have, using the smallest digits. Ones are free to place and the cheapest to repeat, so build a contradiction around the digit $1$.

A three-by-three box must contain a $1$ somewhere. Take the central box (rows $4$ through $6$, columns $4$ through $6$). Knock out its rows and columns one at a time with ones placed elsewhere:

• a $1$ in row $4$ and a $1$ in row $6$ (each outside the central box) forbid the central $1$ from those two rows, so it must sit in row $5$;

• a $1$ in column $4$ and a $1$ in column $6$ force the central $1$ into column $5$.

Now the central box’s $1$ has only one home left, the centre cell (row $5$, column $5$). Put a $2$ there. The four ones can be arranged in four different boxes so that none share a row, column or box, so nothing is illegal on its face, yet the central box can no longer hold a $1$ anywhere. The grid is unfillable. Its numbers are four $1$s and one $2$, summing to $$4\cdot 1 + 2 = \boxed{6}.$$ You cannot do better: forcing a box to exclude a digit from two rows and two columns needs four blocking entries, and the contradiction needs a fifth entry (the $2$) in the doomed cell. Five ones would sum to $5$ but then nothing rules out the forced value; the swap to a $2$ is what makes it impossible, and $2$ is the smallest usable replacement.

The computation

Place the five clues, check no row, column or box already repeats a value (legal on its face), then show the central box has no cell where a $1$ could legally go. That is the impossibility, found without any backtracking.

clues = {(3, 0): 1, (5, 6): 1, (0, 3): 1, (8, 5): 1, (4, 4): 2}   # 0-indexed
g = [[0] * 9 for _ in range(9)]
for (r, c), v in clues.items(): g[r][c] = v

def can_be_one(r, c):                      # could a 1 legally sit at (r, c)?
    if g[r][c]: return False
    if any(g[r][k] == 1 or g[k][c] == 1 for k in range(9)): return False
    br, bc = 3 * (r // 3), 3 * (c // 3)
    return all(g[i][j] != 1 for i in range(br, br + 3) for j in range(bc, bc + 3))

centre = [(r, c) for r in range(3, 6) for c in range(3, 6) if can_be_one(r, c)]
print("sum of clues:", sum(clues.values()))          # 6
print("legal homes for a 1 in the centre box:", centre)   # []  -> impossible

The central box admits no $1$, so the grid cannot be completed, and the five clues sum to $6$.

Riddler Classic

In fifth-edition Dungeons & Dragons you roll with advantage by rolling twice and keeping the higher result, and with disadvantage by keeping the lower. Two richer combinations: “advantage of disadvantage” means you roll twice with disadvantage and keep the higher of those two results, and “disadvantage of advantage” means you roll twice with advantage and keep the lower. With a fair $20$-sided die, which gives the highest expected roll: advantage of disadvantage, disadvantage of advantage, or a single die? Extra credit: if instead you need to roll $N$ or better, which is best for each $N$?

The Riddler, FiveThirtyEight, May 15, 2020(original post)

Solution

A single die averages $\tfrac{1+20}{2} = 10.5$. Each compound roll uses four independent dice $a,b,c,d$, and the two schemes are mirror images: $$\begin{aligned} \text{adv of dis} &= \max\bigl(\min(a,b),\,\min(c,d)\bigr),\\ \text{dis of adv} &= \min\bigl(\max(a,b),\,\max(c,d)\bigr). \end{aligned}$$ “Advantage of disadvantage” applies the lowering operation first to two pairs and only then takes the better, so the lowering dominates: its mean sits below $10.5$. “Disadvantage of advantage” raises first and dominates upward. Averaging over all $20^4$ outcomes, $$\begin{aligned} \text{adv of dis} &= \tfrac{786667}{80000} \approx 9.833,\\ \text{dis of adv} &= \tfrac{893333}{80000} \approx 11.167, \end{aligned}$$ so the highest expected roll comes from $$\boxed{\text{disadvantage of advantage} \approx 11.17}.$$

For the extra credit the ranking flips with the target. “Disadvantage of advantage” bunches its results toward the high end, which helps for modest targets but, because both schemes use four dice, it rarely produces the extreme top values. Comparing the tail probabilities $\Pr(\text{result} \ge N)$:

The computation

Enumerate all $20^4$ four-dice outcomes, evaluate both schemes exactly, and compare their means against $10.5$. The same enumeration gives the tail probabilities for the extra credit.

from fractions import Fraction as F
faces = range(1, 21)
quads = [(a, b, c, d) for a in faces for b in faces
         for c in faces for d in faces]
def mean(f): return F(sum(f(*q) for q in quads), len(quads))
adv_dis = mean(lambda a, b, c, d: max(min(a, b), min(c, d)))
dis_adv = mean(lambda a, b, c, d: min(max(a, b), max(c, d)))
print("single      ", F(21, 2))                 # 10.5
print("adv of dis  ", adv_dis, float(adv_dis))   # 9.833
print("dis of adv  ", dis_adv, float(dis_adv))   # 11.167

def tail(f, N): return sum(1 for q in quads if f(*q) >= N)
best = []
for N in range(1, 21):
    s = sum(1 for v in faces if v >= N) * 8000        # single, scaled to 160000
    a = tail(lambda a, b, c, d: max(min(a, b), min(c, d)), N)
    d = tail(lambda a, b, c, d: min(max(a, b), max(c, d)), N)
    best.append((N, max([("single", s), ("dis_of_adv", d)], key=lambda t: t[1])[0]))
print(best)        # single wins for N>=14, dis_of_adv for N<=13