✨ The horse, water, and walls version of enclose.horse is in P

A proof for boards containing grass, water, and one horse

enclose.horse is a puzzle game in which you place a limited number of walls on a square grid to keep a horse from reaching the edge, while leaving it as much room as possible. This article studies boards with only grass, water, and one horse. For any such board, we can find the best enclosure in polynomial time. The proof algorithm is far too large to be a practical puzzle solver; its point is to settle which complexity class this version belongs to.

The question

As the game's tutorial shows, you place walls on grass cells. The horse can walk up, down, left, or right, but cannot cross water or a wall. If it can reach the edge of the board, it escapes. In the grass-and-water version studied here, an enclosed horse scores one point for each cell it can reach, including its own cell.

The theorem concerns boards made of only grass, water, and one horse. A wall may replace any grass cell, even on the outer edge, and costs one unit. The input is an explicitly listed n × n board, a wall budget B, and a target score K. The decision problem is:

Can placing at most B walls achieve score at least K?

Both numbers may be written in binary. An escaping placement scores zero. “At most” matters: spare walls may be left unused.

The result: this decision problem is in P. The optimum score and a set of walls attaining it can also be found in polynomial time. The proof account goes further: the same conclusion holds for any explicitly embedded finite plane graph, even with vertices of arbitrarily high degree. In that version, escape vertices are those on the designated exterior face of the input embedding; they stay fixed while walls are deleted.

Why the square board was hard to classify

The generalized regular game, with scoring tiles such as apples, cherries, and bees, is NP-complete. Nathan Cho’s “enclose.horse is NP Complete” (June 26, 2026) reduces rectilinear Steiner tree to the game on a square grid1. The restriction with only unit-value grass, water, and freely wallable grass cells requires a separate proof: removing features can remove the gadgets on which a hardness proof relies.

In earlier, unpublished AI-assisted work, GPT-5.6 Sol produced a proof that the corresponding hexagonal-grid version is in P and a proof that the three-dimensional cubic-grid version is NP-complete. Those results pointed in opposite directions for the square grid. The cube grid can route paths through three dimensions; the hexagonal and square grids have different local geometry. The square-grid case remained open.

I spent roughly 200 million tokens with Fable 5 and GPT-5.6 Sol trying to settle the square-grid case without success. The eventual proof came from treating an enclosure as a planar separator, then proving that its boundary can be searched without enumerating exponentially many shapes.

First, say exactly what a solution is

Make a graph G whose vertices are the traversable cells (grass and the horse) and whose edges join cells sharing a side. Let h be the horse and T the traversable cells on the outer edge. After placing walls, let S be the component the horse can still reach. For a positive score, S must be connected, contain h, and avoid T.

Write NG(S) for the cells outside S with a neighbor in S. Every one of those cells must be walled: otherwise the horse could step into it. Conversely, walling precisely those cells makes S the horse’s component. When K = 0 the answer is immediately yes. For K > 0, the question is exactly whether there is a set S satisfying

S connected, h ∈ S, S ∩ T = ∅,   |S| ≥ K,   |NG(S)| ≤ B.

This also shows the problem is in NP: given walls, a flood fill checks escape and score. The difficult part is finding the best S.

A board with nine green cells reachable from the horse, three yellow grass cells sealed off by water, brown placed walls, and blue water. The geometric enclosure contains twelve traversable cells but the score is nine.
A boundary can surround grass the horse cannot reach. Here it surrounds 12 traversable cells, but only the nine green cells score. Any proof that simply counts cells inside a curve gets this example wrong.

From walls to a curve

Discard irrelevant cells and connect the remaining boundary exits to an undeletable exterior vertex t. An enclosure is now a set of wall vertices separating h from t. We can focus on a best solution whose walls are minimal: restoring any one of them would allow escape. It is also important: no separator of equal or smaller size keeps strictly more grass with the horse. A globally best solution has this property.

Such a wall has a neighbor on the horse side and a neighbor on the exterior side. An ordinary selected wall actually needs two exterior neighbors. If it had only one, call that neighbor z. Move the wall from its present cell to z. Every old escape path through the restored cell would have to continue through z, which is now blocked. The old horse component survives and gains the restored cell, at the same cost. That contradicts importance.

Before: a wall has three horse-side neighbors and one exterior neighbor z. After: the wall is moved to z, and its old cell joins the horse side without opening an escape route.
The wall-swap argument uses the fact that every ordinary square-grid cell has at most four neighbors.

Now put a point in each cell and each face of the embedded graph, and connect a cell to each incident face. This is the radial graph; its links are called spokes. A minimal wall separator is represented by a simple closed radial curve, or noose, alternating between selected wall cells and face centers. Its wall vertices are exactly the selected walls. At an ordinary selected wall of degree d, the two-exterior-neighbor argument leaves at most d − 3 unused spokes pointing inward. On the square grid, d ≤ 4, so that is at most one. A selected boundary exit has a separate degree-two rule and no unused inward spoke.

Correct the curve before counting

The original noose can surround an isolated patch like the yellow one in the board diagram. The one-inward-spoke bound makes those errors local. Here is why the errors cannot link distant parts of the curve. Take a chord whose ends lie on the noose and whose selected wall vertices already belong to the wall set. Joining it to either old arc gives two cycles; exactly one separates the horse from the exterior. Minimality forces that separating cycle to use every selected wall. Its length is therefore unchanged, so the discarded arc is exactly as short as the chord. A one-spoke chord from a wall to a face already on the noose makes that wall an actual neighbor of the face. A two-spoke chord through an unused face makes its two walls consecutive on the noose. No face can support a larger independent correction. The proof packages these possibilities as one-wall and two-wall ears.

Radial graph ear correction: an old path from wall u through face g to wall v is replaced by a path from u through inward face f to v. The four links form a local quadrilateral, with the same two selected walls before and after.
For a two-wall ear, the old arc u–g–v is replaced by u–f–v. A one-wall ear is a bigon made of parallel spokes. The selected walls never change.

Correct all ears simultaneously. Their wall footprints are disjoint, and their face-use rules ensure that the corrected curve is still simple. On the designated inside, all additional spokes from selected walls are now just pendant slits. Removing pendant slits cannot split a disk. If this side contains the horse and excludes the exterior, its nonwall cells are exactly the horse’s component.

We also need to show that the correction preserves the horse’s side. Every ear uses at most two walls. If an ear alone separated the horse from the exterior, those one or two walls would already be a separator, contrary to minimality when the solution has at least three walls. Crossing parity then shows that all the corrections preserve which side contains the horse and which contains the exterior. The proof checks solutions with zero, one, or two walls directly.

Turn the true score into local values

Let g be the number of traversable board cells and set M = g + 1. Give every traversable cell charge 1, give the horse an extra charge M, put a balancing negative charge at the exterior mark, and subtract one for each selected wall counted on the inside. For a corrected candidate curve C, call the resulting inside charge F(C).

If the exterior is inside, F(C) ≤ 0.

If the horse is outside, F(C) < M.

If the horse is inside and the exterior outside, F(C) = M + the actual score.

For the positive-target branch, F(C) ≥ M + K therefore recognizes exactly the correctly oriented enclosures meeting the target. The bonus distinguishes the horse’s side; the negative exterior charge rejects a curve wrapped around the wrong side.

A discrete version of Green’s theorem makes this global-looking quantity additive. Route each charge from the exterior to its cell, assigning a signed value whenever that route crosses a radial spoke. Summing those spoke values around the curve counts exactly the charges inside it. Since every ear is a fixed local change to a few spokes, each turn or ear block can be given a fixed signed value before the search. Adding the values of the chosen blocks gives F(C).

The exponentially many possible curves call for a structured search beyond the local scoring formula. Choose a face on an optimal noose as a root and compute radial breadth-first distances. Among optimal nooses, choose one enclosing a maximal set of radial faces. If a shortest tree path made an excursion outside its disk, replacing the corresponding noose arc would use no more walls and either improve the horse component or enlarge that disk. The selected noose therefore works with a shortest-path tree rooted there. The algorithm tries every root and root corner, so it finds such a choice.

The tree is chosen canonically: run depth-first search only along spokes that increase breadth-first distance, scanning incidences in the order opposite to the clockwise contour. This is still a breadth-first tree, because every tree step advances one distance level. The tie-breaking matters for the next geometric property.

Cut the drawing along that tree and list its boundary ports in clockwise order. Tree spokes appear on the outward and return sides of the cut; each non-tree spoke is a noncrossing chord directed from an earlier port to a later one. The chosen noose becomes a forward path through a finite graph of turns. Port numbers strictly increase, so this turn graph is acyclic.

A cut-open tree has a left-to-right clockwise contour. Forward noncrossing chords connect ordered ports. An interval I-f encloses the ports of a face's subtree; repeated uses of face f on a path constrain the blocks between them.
Cutting the radial graph along a canonical tree gives the search a left-to-right order. Tree-subtree ports form intervals; the non-tree chords do not cross.

A turn may visit a face f, written Vf, or use an unused inward spoke to borrow it, written Bf. A repeated borrow allowed by a two-wall ear must appear as one indivisible block Bf, Vg, Bf, where g is the face actually visited between the walls. Parallel single-wall ears are absorbed into their neighboring face visit. Every block emits the face labels it uses. Distinct blocks on a valid path must emit disjoint labels.

Those rules are exact. They make every accepted path a simple noose with a sound ear correction; and, for the chosen root and tree, they represent an optimal important noose. The proof chooses a root cut outside every two-wall ear: the inward-spoke mates form a matching, so at least one of two neighboring face cuts is unpaired. Root/corner enumeration finds it. Grouping a two-wall ear then prevents a path from borrowing the same face three times while pretending that two overlapping ears are independent.

Why the constrained path search is polynomial

Face labels still create a global constraint: two separated blocks that emit the same label cannot both appear. Forbidden pairs can make longest-path search difficult even in an acyclic graph. The proof uses one more geometric theorem.

Fix the first and last blocks of a path, exclude other blocks that reuse their labels, and trim blocks that lie on no endpoint-to-endpoint path. For every remaining arc u→v and exact wall cost b, maintain Luv[b]: the greatest signed value of a represented passage of that cost, together with a witness path. There are three simplifying moves:

  1. Delete an arc whose endpoints use the same face label.
  2. Forget a forbidden pair if no current path can contain both endpoints.
  3. Bypass an interior block with no reachable forbidden mate. Combine incoming and outgoing tables by trying every split i + j = b and keeping the best value.

Bypassing preserves the conflict constraints: a shortcut expands to an older path, and an eliminated block had no reachable mate when removed. The proof states this as an invariant about every current path and its stored witnesses. Values may be negative, so the tables retain exact costs and signed scores, including locally unattractive passages.

Why must these moves finish? Rank face labels first by depth in the breadth-first tree and then by their clockwise subtree order. Suppose a reduced nontrivial path graph remains and take the highest-ranked label f used by two blocks that could occur together. All surviving interior blocks have a reachable forbidden mate. The witness invariant means that a path through this pair cannot secretly repeat a higher-ranked label.

The simplest case already shows the mechanism. If both uses of f are anchored in its tree-subtree interval If, every block strictly between them is also trapped in that interval. Every label such a middle block emits is f or higher. Higher labels cannot provide its forbidden mate, by the choice of f; so it must emit f. Its first edge from an f block would have been deleted. Contradiction.

Other owners of f can sit just outside that interval: at a lower-depth non-tree neighbor, an early turn at f’s parent, a higher-depth non-tree neighbor, or a late parent turn. For most pairs, noncrossing chords trap the middle blocks in If and adjacent, higher-ranked child intervals. Late-parent cases also involve a later, equal-depth sibling face q. They need a separate sibling-mate argument; one apparent escape is exactly the strict Bf, Vq, Bf block and cannot be two conflicting blocks. The proof first eliminates visit/borrow pairs and then exhausts the possible ordered pure-borrow pairs:

Borrow pairObstruction
Inside–insideThe subtree-interval argument above.
Lower or early-parent → insideA noncrossing chord or parent turn traps a higher-ranked cap.
Lower, early-parent, or inside → higherThe two borrowed spokes confine the middle to higher-ranked caps and If.
Higher → late-parentThe late turn forces a consecutive sibling interval that excludes the pair.
Lower or inside → late-parentThe sibling-mate argument or strict ear block makes the pair impossible.
All remaining ordersClockwise order, noncrossing chords, or the one-spoke wall bound forbids them.

This is the longest part of the square-grid proof account, pages 14–20. The PDF states the cap and sibling lemmas and sketches their incidence arguments, while referring some full literal-incidence checks to unpublished companion notes. Together these cases rule out every highest active label in a reduced nontrivial graph. Therefore some simplifying move always applies until only the endpoints and their exact-cost table remain. The terminal table gives the best valid path at each cost for this branch. Taking the best over all roots and branches, along with the direct zero-to-two-wall cases, gives the decision answer.

What the time bound says

Let m = n2, the number of cells in the explicit input board. There are polynomially many roots, turns, blocks, endpoint choices, and table entries. The proof’s deliberately generous accounting has O(m12) compiler vertices and O(m29) endpoint branches per root/corner choice. A budget larger than the number of wallable cells is capped before any table is allocated. Scores, local charges, and stored path values have polynomial bit length. Table sizes and work bounds remain polynomial in input bit length even when B and K are binary.

To find the optimum, binary-search the score between zero and m using the decision procedure. Further decision calls can recover a wall set. This is a uniform polynomial-time result, but those enormous bounds are a warning against using the proof algorithm as a practical daily-puzzle solver.

The plane-graph extension needs a different local argument. At a high-degree wall there may be many inward spokes, so the square-grid ear rule fails. The proof compresses neutral regions attached through one or two vertices, tracks each wall’s full inward fan of faces, and subtracts the rewards of inside components that remain disconnected from the horse. A ranked face-resource search then replaces the degree-four shortcut. It gives a polynomial-time algorithm for arbitrary vertex degrees; the full proof supplies the additional ownership and termination casework.

Proof and verification

Enclosing a horse in polynomial time contains the precise theorems, algorithms, and detailed proofs for the square-grid and plane-graph versions. It reports Lean proofs connecting executable decision procedures to the original enclosure questions, along with polynomial work and operand bounds, finite comparisons against exhaustive solvers, and source audits. The PDF was prepared from that research record; its formal project was not freshly rebuilt for this edition, and the formal source and companion incidence notes are not bundled with it. The exported formal interface is a decision procedure; optimization and wall recovery are mathematical corollaries.

The theorem here is about explicitly given boards, unit-cost walls on grass, positive unit cell scores, one horse, and escape at the original boundary. Under these rules, a square-grid enclosure problem that looked like a candidate for NP-completeness has a polynomial-time solution—and the same geometric method reaches all finite plane graphs.