Behind "Fluffy Sheep Pasture Enclosure":
From Minimum Vertex Cut to Budgeted Maximum-Weight Connected Subgraph

01Puzzle Rules and Graph Representation

The board is modeled as an undirected grid graph G = (V, E), where orthogonally adjacent passable cells form the edge set E. Each vertex (cell) v ∈ V has the following properties:

The player's goal is to place at most K fences so that all paths between the wolves W and the sheep S are blocked, while maximizing the total score of the connected pasture reachable from the sheep S.

02What If We Only Minimized Fence Count? (Minimum s-t Vertex Cut)

Suppose we temporarily ignore tile scores and ask only: "What is the minimum number of fences required to separate the wolves W from the sheep S?"

Whereas the standard minimum cut problem removes graph edges, here we block grid cells (vertices) with fences. This corresponds to the Minimum s-t Vertex Cut problem in graph theory.

Why This Puzzle Goes Beyond a Pure Minimum Cut

Two structural features make this puzzle richer than a textbook minimum cut problem:

1. Maximizing Enclosed Value Under a Fence Budget K:
   Even when a narrow choke point can be sealed with 1 fence, spending 2 fences further forward to hold a branch junction may capture a rich strawberry patch (🍓 +5) beyond it. Deciding where to invest the fence budget K introduces a knapsack-like trade-off across multiple fronts.
2. Negative Weights from Pitfalls (🕳️ -5):
   Even in a dead-end corridor with no wolves, if a pitfall 🕳️ (-5) lies connected to the pasture, spending a fence to seal off that corridor—or driving a fence post directly into the pit to plug it—improves the score by +5. Conversely, if three strawberries (+15) lie behind a pitfall (-5), deliberately leaving the pitfall open inside the pasture to keep the path open yields a net gain of +10 (as seen in Stage 7).

03MILP Formulation (Part 1): Decision Variables and the Flood Constraint

To formulate the puzzle as a Mixed-Integer Linear Program (MILP), we introduce two sets of binary decision variables over the passable cells $v \in V$:

First, we state the boundary conditions, mutual exclusion, and the fence budget constraint:

The Flood / Cut Constraint Across Adjacent Cells

Next, we express the propagation rule: "If cell $u$ is inside the pasture ($r_u = 1$) and its neighbor $v$ has no fence ($f_v = 0$), then $v$ must also be inside the pasture ($r_v = 1$)."

This single linear inequality $r_u \le r_v + f_v$ simultaneously enforces two essential properties:

• Role A (Complete Wolf Separation):
  If any open path from a sheep ($r_s = 1$) reaches a wolf ($r_w = 0$) without encountering a fence ($f_v = 1$), chaining the inequality along the path yields $1 = r_s \le \dots \le r_w = 0$, which is infeasible. Thus every wolf-to-sheep path must contain at least one fence.
• Role B (Preventing Cherry-Picking Around Pitfalls):
  Without this constraint, an optimizer could set $r_v = 1$ on positive tiles (🍓 +5) while arbitrarily setting $r_v = 0$ on an unfenced pitfall (🕳️ -5) right next to the sheep. Because of the flood constraint, any pitfall adjacent to the pasture forces a strict choice: spend a fence post to plug/block it ($f_v = 1, r_v = 0$) or include it in the pasture and accept the $-5$ penalty ($f_v = 0, r_v = 1$).

04MILP Formulation (Part 2): Disconnected Pockets and Single-Commodity Flow

Here we encounter a classic mathematical modeling pitfall: the flood constraint alone is not sufficient to define the pasture accurately.

Why does this happen? Because r_u <= r_v + f_v forces every cell reachable from the sheep to have r_v = 1 (a lower bound), but it does not forbid setting r_v = 1 inside an isolated pocket walled off by fences and water.

Solution: Single-Commodity Network Flow

To guarantee that $r_v = 1$ holds only if cell $v$ is genuinely connected to at least one sheep in $S$, we add Single-Commodity Flow conservation constraints.

Over the directed arc set $A = \{(u, v), (v, u) \mid \{u, v\} \in E\}$, we define a non-negative continuous variable $\text{flow}_{u \to v} \ge 0$ representing the amount of flow sent from $u$ to $v$ (where $M = |V|$ is the total number of passable cells):

05Objective Function and 1-Move Hint Diagnosis (Partial Fixing)

Finally, we combine "maximizing total pasture score (primary objective)" and "using as few fences as possible among tied scores (secondary tie-breaker)" into a single linear objective using a lexicographic weight of $100$:

The in-game "💡 1-Move Hint" button does not merely look up a static answer key. Instead, it fixes the player's currently placed fences $F_{\text{cur}}$ ($f_v = 1$ for all $v \in F_{\text{cur}}$) and re-solves the MILP in real time:

• If the restricted problem is still Feasible and achieves the optimal target score $Z^*$:
  The player's current fences are on a valid optimal path, so the game highlights one remaining unplaced fence $f_v^* = 1 \; (v \notin F_{\text{cur}})$ in yellow.
• If the restricted problem is Infeasible or its optimal objective falls short of $Z^*$:
  At least one placed fence is blocking the optimal enclosure, so the game identifies that fence and highlights it in red for removal.

Model Construction Excerpt

// 1. Flood constraint (if u is in the pasture and v has no fence, v must also be in the pasture)
if (vFence) {
  model.constraint(expr`${uReach} - ${vReach} - ${vFence} <= 0`);
} else {
  model.constraint(expr`${uReach} - ${vReach} <= 0`);
}

// 2. Single-commodity flow (flow is active only when both u and v are in the pasture)
const flowUV = model.continuous(`flow_${r}_${c}_to_${nr}_${nc}`, { lb: 0, ub: maxFlowM });
model.constraint(expr`${flowUV} - ${maxFlowM} * ${uReach} <= 0`);
model.constraint(expr`${flowUV} - ${maxFlowM} * ${vReach} <= 0`);

// 3. Flow conservation at every non-sheep cell (inflow - outflow == r_v)
model.constraint(expr`sum(${inList}) - sum(${outList}) - ${rVar} == 0`);