Knights asks for one piece in every region of a partitioned grid, no two of them a knight’s move apart or touching. The usual way to prove such a puzzle hard is to encode a bit in a small region and chain those regions together into wires. Here that provably cannot work: the conflict relation is short-ranged enough that such a chain can never turn. What does work is to make each wire a single region — a region is any connected set, so it can cross the whole board, and forced pieces beside it can reduce it to two usable cells wherever we like. The bishop’s rule is hard for a different reason and yields to a different device: diagonals are scarce, every piece spends one of each kind, and a long connecting path can be blocked by two pieces rather than cell by cell.
The decision problem, membership in NP, and the single fact about the conflict relation on which everything rests.
An instance of Knights is an n by n grid of cells partitioned into regions R1,…,Rk, each orthogonally connected. A placement is a choice of one cell from each region. Cells u and v conflict when u − v lies in
C = { (±1, 0), (0, ±1), (±1, ±1), the king's moves
(±1, ±2), (±2, ±1) } the knight's moves
a set of sixteen offsets, symmetric under negation, under reflection in either axis, and under transposition. The decision problem is whether some placement has no conflicting pair.
Knights is in NP: a placement is k cell indices and is checked in O(k²) lookups.
‖u − v‖∞ ≥ 3 then u and v do not conflict.
Every offset in C has sup-norm 1 or 2: the eight king offsets have sup-norm 1, and the eight knight offsets have sup-norm 2. So no offset of sup-norm 3 or more lies in C.
Lemma 1 is used constantly below in the following form: two sets of cells at sup-distance 3 or more place no constraint on each other at all. In a grid reduction the fiddliest obligation is usually proving that gadgets do not interfere; here it is a distance check.
Not a digression: this is what forces the construction to take the shape it does. The argument is a complete case analysis of the conflict set.
A two-cell region is a bit. Say two disjoint regions A, B form a faithful link if the two-region system has exactly two placements and each region takes a different cell in each of them, so that fixing one determines the other.
Since a placement of a two-region system is a compatible pair, the number of placements is |A|·|B| minus the number of conflicting pairs. For two dominoes that is four minus the conflicts. Two of the four placements must survive; and if the two surviving pairs shared a cell of A, then A would take the same cell in both, so the link would not be faithful. Hence:
A link is faithful exactly when the two conflicting pairs form a perfect matching between A and B, equivalently when the two surviving pairs do.
γ = ±2 and δ ∈ {0, ±1}. The step copies the bit when δ = 0 and negates it when δ = ±1.
Write a0 = (r,c), a1 = (r+1,c), and b0, b1 likewise. The four pair offsets are
b0−a0 = b1−a1 = (δ,γ), and
b1−a0 = (δ+1,γ), and
b0−a1 = (δ−1,γ).
So the two "parallel" pairs always share an offset, and the two "cross" pairs have offsets differing from it by ±1 in the first coordinate. By the characterisation above, faithfulness means either
(i) (δ,γ) ∈ C while (δ±1,γ) ∉ C, or
(ii) both (δ+1,γ) and (δ−1,γ) lie in C while (δ,γ) does not.
Split on γ, using that (d,γ) ∈ C holds for d ∈ {±1} when γ = 0; for d ∈ {0,±1,±2} when |γ| = 1; for d ∈ {±1} when |γ| = 2; and never when |γ| ≥ 3.
|γ| ≥ 3. No pair conflicts, so there are four placements. Neither case holds.
γ = 0. In case (i), δ = ±1, but then A and B share a cell, contrary to disjointness. In case (ii), δ+1 and δ−1 must both be ±1, forcing δ = 0 and B = A.
|γ| = 1. In case (i) we need |δ| ≤ 2 with |δ+1| ≥ 3 and |δ−1| ≥ 3; the first two force δ = 2, which fails the third. In case (ii) we need |δ+1| ≤ 2 and |δ−1| ≤ 2, giving −1 ≤ δ ≤ 1, while |δ| ≥ 3 is required. Both impossible.
|γ| = 2. In case (i), |δ| = 1 with |δ+1| ≠ 1 and |δ−1| ≠ 1; both δ = 1 and δ = −1 satisfy this. The surviving placements are the cross pairs, so the bit is negated. In case (ii), δ+1 = ±1 and δ−1 = ±1 force δ = 0, and |0| ≠ 1 as required; the surviving placements are the parallel pairs, so the bit is copied.
|Δrow| ≤ (m−1) = |Δcol| / 2
between the two ends.
By Lemma 2 each step changes the column by exactly ±2 and the row by at most 1. Suppose the column direction reverses at index i, so that Di−1 and Di+1 both lie two columns to the same side of Di and therefore occupy the same column. Their rows differ by δi + δi+1, which has absolute value at most 2. A difference of 0 makes them the same region; a difference of 1 makes them share a cell, contradicting disjointness; a difference of 2 places the lower cell of the upper domino and the upper cell of the lower domino at offset (1,0) ∈ C, so they conflict, again contrary to hypothesis. Hence no reversal occurs, the column is monotone, |Δcol| = 2(m−1), and each of the m−1 steps contributes at most 1 to |Δrow|.
So a chain of two-cell regions travels in one horizontal direction only, and never rises faster than one row per two columns. It cannot double back, and it cannot move straight up. Any construction that needs to route a signal freely around a plane therefore needs something other than a chain of small regions.
One might hope a larger region placed at the turn could bridge the gap. Lemma 4 rules that out for the reason that matters.
|A|·|B| placements. In particular a faithful link between two regions of two or more cells each is impossible at that separation.
By Lemma 1 no pair conflicts, so every pair is a placement. A faithful link has exactly two placements, so |A|·|B| = 2, forcing one of the regions to be a single cell.
A single-cell region is not a bit: it has one state. So no region, of any size, can carry a signal to another region that is wholly 3 or more away. Signals move only between regions that come close, and by Proposition 3 a chain of small ones cannot get anywhere useful. The way out is to make the regions themselves large.
A wire does not have to be a chain of small gadgets. A region is any orthogonally connected set of cells, so a single region may be a path across the whole board; forced pieces placed alongside it reduce it to exactly two usable cells, and those two may be chosen anywhere along it. One region is the whole wire.
A region consisting of a single cell forces a piece onto that cell. Call such a region an anchor. Anchors are the only device the construction needs beyond the regions being encoded.
A cell (r, y) has offset (−1, y−x) from the anchor. The offsets in C with first coordinate −1 are exactly (−1, d) for d ∈ {0, ±1, ±2}.
An anchor is a one-cell region, so every placement puts a piece on it. A cell conflicting with an anchor therefore appears in no placement, and removing it from its region removes no placement. Conversely removing cells cannot create placements.
This is the lemma that makes the layout tractable, and it is worth pausing on. After the anchors are fixed, a region is equivalent to its set of live cells: everything else is inert. Two wires may therefore run alongside each other, share a lane, even interleave — collisions between dead cells are not collisions at all. The only things that constrain each other are live cells and anchors, of which there are few and whose positions we choose. What looked like an obligation about the whole board reduces to an obligation about a sparse set of designated cells.
Two further facts, read off C the same way, are used below: two cells in one row conflict only when they are adjacent, since the offsets (0, d) in C are exactly d = ±1; and an anchor reaches no further than two rows, by Lemma 1.
(a) A nonzero difference of lattice points is (3i, 3j), of sup-norm at least 3, so Lemma 1 applies. (b) and (c) are a check on the nine residue classes of (r mod 3, c mod 3). A cell of residue (a, b) has a lattice neighbour for each δ ∈ C with δ ≡ (−a, −b) (mod 3). Since every coordinate appearing in C lies in {0, ±1, ±2}, the congruence pins each coordinate of δ to at most two values, and reading off C gives: residue (0, 0) has none; (0, 1), (0, 2), (1, 0) and (2, 0) have exactly one, namely (0,−1), (0, 1), (−1, 0) and (1, 0); and the four diagonal residues have exactly three, for instance (1, 1) has (−1,−1), (−1, 2) and (2,−1). The three offsets in each such triple differ pairwise by (0, ±3), (±3, 0) or (±3, ∓3), all of sup-norm 3.
So Λ is a set of cells that may all hold anchors at once, and whose anchors between them block the entire rest of the board. That is the whole anchor problem solved in one stroke: the placement is global, fixed in advance, and independent of what the wires are doing.
⋃P ∈ Ω { P, P±(1,0), P±(0,1) },
one plus-shaped cluster of five around each point of Ω.
A cell is usable exactly when it conflicts with no anchor, that is when every one of its lattice neighbours lies in Ω. By Lemma 6 a cell of Λ has no lattice neighbours, so it is usable precisely when it carries no anchor, that is when it lies in Ω. A cell with exactly one lattice neighbour is usable precisely when that neighbour lies in Ω; by Lemma 6(c) these cells are the four orthogonal neighbours of each lattice point, giving the four arms. A cell with three lattice neighbours would need all three in Ω, which the hypothesis forbids. No other cells exist, again by Lemma 6.
Immediate from Lemma 7: the usable cells of W are W intersected with the union of the clusters.
The hypothesis is easy to meet. A window P has a cluster of five cells lying in three consecutive rows and three consecutive columns; a wire running along a single row through P±(0,1) but avoiding row Prow meets that cluster once. Since a wire may be routed anywhere subject to avoiding Λ — that is, along any row or column whose index is not divisible by 3 — its two usable cells may be put at any two windows on the board. This is the routing that Proposition 3 denied to chains, and it now costs nothing: the anchors were placed once, globally, before any wire was drawn.
With bits that can be read anywhere, the remaining pieces are short arguments from Lemma 1.
The pairwise differences of the four diagonal offsets are (0, ±2), (±2, 0) and (±2, ±2), none of which lies in C. For the orthogonal four, (0, 1) − (1, 0) = (−1, 1), which does lie in C.
So a live cell may be met by up to four other regions at once without those regions constraining one another, provided they approach on the diagonals. This is what allows a variable to be read by several clauses, and it is a genuine bound: five neighbours of one cell always contain a conflicting pair.
The pairs (x0,y0) and (x1,y1) are excluded by hypothesis. The cross pairs join cells at the two separate meeting places, which are at sup-distance 3 or more, so by Lemma 1 they do not conflict and both survive. Two placements remain, and in each the two bits take opposite indices.
Stating the hypothesis as conflict rather than adjacency widens what counts as a meeting. In particular two wires running parallel two rows apart, with live cells at (R, p), (R, q) and (R+2, p+1), (R+2, q+1) and |p − q| ≥ 4, form a link: the offset (2, 1) lies in C while (2, q+1−p) does not. Two links in series restore the sign, so copying and negation are both available.
By Lemma 1 the only conflicts in the system are the three adjacent pairs (zi, fi). Fix a choice for each bit. Cell zi is available exactly when Xi did not take fi, that is exactly when Xi took ti. Region Z needs one available cell, so the system extends the given choice if and only if some Xi took ti. Since the bits are otherwise unconstrained, a placement of the whole system exists precisely when some assignment makes one of them true.
Lemma 7 supplies such a Z: it is a path region with three live cells, each placed beside its own input at a separate location, so the sup-distance condition is met by construction.
A layout precise enough for the interference conditions to be checked by distance, and the two directions of correctness.
Let φ be a planar 3-CNF formula with n variables and m clauses, given with a planar embedding of its variable–clause incidence graph. Planar 3-satisfiability is NP-complete (Lichtenstein, 1982). Fix an integer T = 8 and divide the board into T by T tiles. Within each tile, in tile-local coordinates:
Scale the planar embedding so that every vertex of the incidence graph sits at a tile, and every edge becomes a rectilinear path along track lines. Realise each edge as a wire by Lemma 8, routing it along rows and columns whose indices are not divisible by 3, and giving it a window at each end. Chain the occurrences of each variable through links (Lemma 10), inserting one extra link wherever a literal is negated; place each clause as a three-live-cell region (Lemma 11). Give every cell not used by a wire, a clause or an anchor to a filler region, one per tile, consisting of that tile’s free block together with any unused track and lane cells of the tile, each attached through a neighbour already in the region.
Two wires never share a cell because distinct edges of a planar embedding are disjoint; this is exactly why the embedding must be planar, and exactly what planar 3-satisfiability supplies.
Take the cell at tile-local position (5, 5), which lies in the free block and so belongs to this tile’s filler region. Track and lane cells occupy tile-local rows 0 and 1 and columns 0 and 1, of this tile and of its neighbours. Within the tile, the distance from row 5 to rows 0 and 1 is 5 and 4, and to the next tile’s rows 8 and 9 is 3 and 4; the same holds for columns. So every track or lane cell is at sup-distance 3 or more, and Lemma 1 applies.
Each filler region is orthogonally connected: its free block is a solid 6 by 6 rectangle, and every other cell was attached through a neighbour already in the region.
If φ is satisfiable, the board has a placement. Put every anchor on its forced cell. For each variable, place its bits on the live cells matching the satisfying assignment, respecting the sign changes introduced by the links; Lemma 10 says this is consistent. For each clause, Lemma 11 gives an available cell, since the assignment makes some literal true. Put each filler piece on the cell given by Lemma 12. No two placed pieces conflict: within a gadget this is Lemmas 10 and 11; between gadgets it is Lemma 1, since distinct gadgets meet only at the designated meeting places and are otherwise at sup-distance 3 or more; anchors conflict with neither each other, by Lemma 6(a), nor with any usable cell, since by Lemma 7 a cell is usable precisely when every lattice neighbour of it carries no anchor; and filler pieces conflict with nothing by Lemma 10.
If the board has a placement, φ is satisfiable. Each bit takes one of its two live cells, by Lemma 8, so the placement determines a truth value for each variable occurrence. Lemma 10 forces all occurrences of one variable to agree up to the known signs, so the values are consistent and define an assignment. Each clause region holds a piece on one of its three live cells, so by Lemma 11 the corresponding literal is true. Hence every clause is satisfied.
The board has side O(n + m) tiles, so O((n+m)²) cells; each wire has length at most the perimeter; the number of anchors is at most the total wire length; and every step of the layout is computable in polynomial time.
Lemmas 6 to 8 discharge what used to be the hard part. The anchors are a fixed lattice, chosen before anything else and independent of the formula; they never conflict with one another by Lemma 6(a), they never conflict with a usable cell because a cell is usable precisely when its lattice neighbours were omitted, and they leave alive exactly the clusters we asked for. Two conditions on the windows remain, and the next two lemmas settle them.
The differences are (0, 2), which is not in C, and (1, −1) and (1, 1), which are. For the second part, P has both coordinates divisible by 3, so among the five cluster cells the rows taken are Prow (by P and P±(0,1)) and Prow±1 (by one cell each), and likewise for columns; a line avoiding Λ is one whose index is not divisible by 3, which excludes the row and column of P itself.
This is the piece that makes an attachment local. A variable wire running along the row Prow+1 takes the cluster cell P+(1, 0) as one of its two live cells. Two clause wires running down the columns Pcol±1 take P±(0, 1). Each clause cell conflicts with the variable cell, so a clause is blocked exactly when the variable sits there; and the two clause cells do not conflict with each other, so the clauses do not interfere. One window hosts a variable’s value together with the two clauses that read it, and no second window is needed.
A variable therefore supports two readings at each of its two live cells, four occurrences in all. That is enough: replacing a variable of high degree by a cycle of copies joined by equality clauses — the standard normalisation, which preserves planarity because the cycle can be drawn around the original vertex — leaves every variable with at most three occurrences, at most two of either sign. Equality between consecutive copies of the cycle is itself Lemma 10, realised the same way, with one copy taking P+(1, 0) and the next taking P+(0, 1) at each of two shared windows.
For Lemma 7 we need that no three windows are the three lattice neighbours of a common cell. By Lemma 6(c) any such triple lies pairwise at sup-distance 3, and distinct windows are at sup-distance at least 12. For Lemma 8 we need each wire to meet exactly one cell of each of its own clusters and no cell of any other. A cluster is contained in a 3 by 3 box about its window, and the boxes of distinct windows are disjoint and at sup-distance at least 9, while the wires follow edges of D, which after scaling are at least 12 apart except where they meet at an attachment site. A wire entering a cluster does so along a line avoiding Λ, and by Lemma 13 such a line meets the cluster in exactly one cell.
Nothing is left to arrange. The anchors are fixed by Lemma 6 before the formula is read; the windows are fixed by Lemma 14 from the drawing; the live cells and their conflicts are fixed by Lemma 13; and the correctness of the encoding is Lemmas 10 and 11. Every condition invoked along the way is a statement about the offset set C or a sup-distance, and each has been checked.
Membership in NP is immediate. Hardness is the construction above, from planar 3-satisfiability, computable in polynomial time on a board of side O(n + m) after scaling. Connectivity holds throughout: wires and clause regions are rectilinear paths, anchors are single cells, and filler regions are a solid rectangle with cells attached through neighbours.
The same question for the bishop’s rule. The obstruction that shapes the knights construction is absent here, and a different one takes its place: diagonals are a scarce resource, every piece spends one of each kind, and the count alone forces the regions to be few and large.
An instance of Bishops is an n by n grid partitioned into orthogonally connected regions, with n odd. Cells u and v conflict when u − v lies in
Cⁱ = { (±1, 0), (0, ±1) } the orthogonal king moves
∪ { (±t, ±t) : t ≥ 1 } every bishop move
the diagonal king moves being the case t = 1. As before, the decision problem is whether some placement has no conflicting pair, and membership in NP is immediate.
A step along a diagonal alters each coordinate by one in absolute value, so it alters r + c by 0 or ±2 and preserves its parity, which is (a). Orthogonal neighbours differ by one in exactly one coordinate, so they have opposite colours; two cells of the same colour are therefore never orthogonally adjacent, and with (a) the only offsets of Cⁱ still available to them are the diagonal ones, which is (b). For (c), by (a) cells of opposite colour lie on no common diagonal, so the only offsets left are the two orthogonal ones.
Index the up-diagonals of the board by r + c and the down-diagonals by r − c. There are 2n − 1 of each, of which n carry dark cells and n − 1 carry light ones. By Lemma 15(b) two pieces of the same colour must differ in both indices, so a piece consumes an up-diagonal and a down-diagonal of its own colour and leaves the other colour untouched.
k ≤ 2n − 1.
Distinct pieces of one colour lie on distinct up-diagonals by Lemma 15(b). At most n pieces are dark and at most n − 1 light.
That count shapes what follows. A board of n² cells carries at most 2n − 1 regions, so the average region has at least about n/2 cells: the regions cannot be small, and a reduction cannot proceed by cutting the board into many little pieces with few options each. Everything below is arranged around large regions instead.
A region must be orthogonally connected, so joining two distant cells costs a path, and every cell of that path is another cell the region might be placed on. In the knights construction, blocking those cells is the expensive part of the argument. Under the bishop’s rule it is free.
(r, c) be dark and d = r − c. In the walk
(r, c), (r, c+1), (r+1, c+1), (r+1, c+2), (r+2, c+2), …
consecutive cells are orthogonally adjacent, every dark cell has r − c = d, and every light cell has r − c = d − 1.
The steps alternate between (0, 1), which lowers r − c by one and changes the colour, and (1, 0), which raises it by one and changes the colour back. Beginning dark at d, the value is d at every dark cell and d − 1 at every light one. Each step moves one square orthogonally.
Every dark cell of the walk shares down-diagonal d with the first piece and every light cell shares d − 1 with the second. By Lemma 15(b) each is a conflict.
Connectivity is a property of the region and not of the cells a placement may use, so a region may be connected entirely through cells that no placement can occupy. That is what the scarcity of Lemma 16 would otherwise forbid: blocking cells one at a time is unaffordable, while blocking a whole staircase costs two pieces whatever its length.
For integers U, V such that the cells below lie on the board, write
D(U, V) = { (r, c), (r, c+1), (r, c+2) }
where (r, c) = (U + V, U − V)
and call it a domino. It is three cells in a row, hence orthogonally connected.
D(U, V) are (r, c), on up-diagonal 2U and down-diagonal 2V, and (r, c+2), on up-diagonal 2U + 2 and down-diagonal 2V − 2. The middle cell is light, on down-diagonal 2V − 1.
From r = U + V and c = U − V we get r + c = 2U and r − c = 2V. Adding two to the column raises r + c by two and lowers r − c by two; adding one gives the odd value 2U + 1, hence a light cell, with r − c = 2V − 1.
A light piece on down-diagonal 2V − 1 makes the middle cell unavailable, by Lemma 15(b). An anchor does it: a region of one cell, exactly as in the knights construction, which takes that cell in every placement.
D(U, V) and D(U, W) both be unavailable. Then in every placement exactly one of the two dominoes takes its cell on 2U and the other takes 2U + 2, and no other piece lies on either up-diagonal. If D(U, V) does, the two pieces lie on down-diagonals 2V and 2W − 2; if D(U, W) does, they lie on 2V − 2 and 2W.
Each domino has only its two dark cells available, on up-diagonals 2U and 2U + 2 by Lemma 19. By Lemma 15(b) the two pieces may not share an up-diagonal, so one takes each, and the down-diagonals follow from Lemma 19. Both up-diagonals are then occupied, so a piece of any third region on either of them would share an up-diagonal with a domino, which Lemma 15(b) forbids. The exclusion is therefore a consequence and not a hypothesis, which matters because the filler regions of Lemma 24 are staircases crossing every up-diagonal of the board, so it could not have been assumed.
Write x = 1 for the case in which D(U, V) takes the lower up-diagonal. The four down-diagonals 2V, 2V − 2, 2W, 2W − 2 then split into two complementary pairs: the variable’s own pieces occupy 2V and 2W − 2 when x = 1, and 2V − 2 and 2W when x = 0. So 2V − 2 and 2W are clear of them exactly when x = 1, and 2V and 2W − 2 exactly when x = 0. Each literal is carried by two down-diagonals, and a diagonal runs the width of the board, so the bit is legible arbitrarily far from the domino that holds it and no wire is needed to carry it there.
Two down-diagonals per literal means a variable can be read four times. That is enough: satisfiability of a formula in conjunctive normal form with three literals to a clause is already NP-complete when no variable occurs in more than four clauses, so no gadget for copying a variable is required.
ℓ₁, …, ℓ₃ be carried by down-diagonals 2v₁, …, 2v₃, let T be an integer, and let m and M be the least and greatest of the vᵢ. Put
teeth = { (T − 1 + vᵢ, T − 1 − vᵢ) }
trunk = { (T + v, T − v) : m − 2 ≤ v ≤ M + 1 }
∪ { (T + v, T − v − 1) : m − 2 ≤ v ≤ M + 1 }
Then the union is orthogonally connected; the teeth lie on up-diagonal 2T − 2 and on the down-diagonals 2vᵢ; and if some piece lies on up-diagonal 2T and some piece on 2T − 1, the only available cells of the region are the teeth.
The tooth for vᵢ has r + c = 2T − 2 and r − c = 2vᵢ, as claimed. Its right neighbour (T − 1 + vᵢ, T − vᵢ) has r + c = 2T − 1 and is the trunk cell of the second family for v = vᵢ − 1, which lies in range; that cell’s right neighbour (T − 1 + vᵢ, T + 1 − vᵢ) has r + c = 2T and is a trunk cell of the first family. Within the trunk, the cells (T + v, T − v) and (T + v + 1, T − v − 1) of the first family are both orthogonally adjacent to (T + v, T − v − 1) of the second, so the trunk is a single staircase in the sense of Lemma 17 and the teeth hang from it. Every trunk cell of the first family has r + c = 2T and every one of the second has r + c = 2T − 1, so by Lemma 15(b) a piece on each of those two up-diagonals conflicts with all of them, while the teeth, on 2T − 2, are unblocked.
Give each clause two anchors, one on up-diagonal 2T and one on 2T − 1. The clause region is then placeable exactly when at least one of its teeth is free of other pieces, that is, exactly when some literal’s down-diagonal carries no other piece. The trunk may be as long as the board without adding a single option, which is Lemma 18 doing the work that a wire does in the knights construction.
The regions must partition the grid, so every cell no gadget uses belongs to a filler region, and each filler is one more piece competing for the diagonals on which the gadgets signal. This is not bookkeeping: a filler landing on a literal’s down-diagonal would block the tooth that reads it.
|d| ≤ n − 1 let Sd be the dark cells on down-diagonal d together with the light cells on down-diagonal d − 1. These sets are pairwise disjoint, each is orthogonally connected, and together they cover every cell of the board.
A dark cell has r − c even and lies only in the set indexed by d = r − c; a light cell has r − c odd and lies only in the set indexed by d = r − c + 1, which is even. Every cell is therefore accounted for once: a dark cell has |r − c| ≤ n − 1 by definition, and a light cell has r − c odd, hence at most n − 2 in absolute value since n is odd, so its index r − c + 1 is even and lies in range. Each set is exactly the walk of Lemma 17 begun at the first dark cell of its down-diagonal, hence connected.
Say a filler is homed at a down-diagonal reserved to it alone, and that it has a private crossing if some dark cell on its home diagonal lies on an up-diagonal reserved to it alone. A filler with a private crossing can be placed there in any circumstance whatever, since nothing else may occupy either diagonal. If every filler has one, the fillers can be disposed of once and for all.
d = 2v occupy exactly the up-diagonals 2u with |v| ≤ u ≤ n − 1 − |v|, that is n − |d| of them, and these sets are nested about u = (n − 1)/2. Consequently no assignment of distinct private up-diagonals to all of the staircases of Lemma 22 exists.
A dark cell with r − c = 2v and r + c = 2u is (u + v, u − v), which lies on the board exactly when u ≥ |v| and u ≤ n − 1 − |v|, giving n − 2|v| = n − |d| values of u, an interval centred at (n − 1)/2 and shrinking as |v| grows. Take the family of staircases with |v| ≥ a for any a ≥ 1. It has n + 1 − 2a members, since v ranges over ±a, …, ±(n−1)/2, while the union of their up-diagonal sets is the largest of them, of size n − 2a. As n + 1 − 2a > n − 2a, Hall’s condition fails.
The corners are the obstruction: the short staircases are too numerous for the few up-diagonals they can reach. Cutting the tiling off before the corners repairs it.
|d| ≤ D that is not one of those h, attach every remaining cell to a filler adjacent to it, and suppose n − D − g ≥ D + 1. Then the fillers partition what the gadgets leave, each is orthogonally connected, and each has a private crossing.
There are at most D + 1 homed fillers. By Lemma 23 the filler homed at d meets n − |d| ≥ n − D up-diagonals on its home diagonal, of which at most g are reserved to gadgets, leaving at least n − D − g candidates for its private crossing. Since that number is at least D + 1, which is at least the number of fillers, every subfamily has at least as many candidates available as it has members, so Hall’s condition holds and distinct private up-diagonals may be chosen. The cells left over — those with |r − c| > D, and those on the h reserved down-diagonals — are attached to an adjacent filler, which keeps every region connected and can only add options to it, never remove the private crossing.
Since g and h are proportional to the number of variables and clauses, taking n a large enough constant multiple of that number and D about n/3 satisfies the hypothesis with room to spare.
Given a formula with V variables and C clauses, three literals to a clause and no variable in more than four clauses, allocate to each variable a pair of consecutive up-diagonals and four down-diagonals as in Lemma 20, to each clause an up-diagonal triple as in Lemma 21, and to each anchor its cell, all distinct and pairwise non-conflicting — in particular each light anchor is placed far enough along its diagonal that it is orthogonally adjacent to no tooth and no domino cell, which by Lemma 15(c) is the only way it could reach them; this is possible on a board of side n = Θ(V + C), since each gadget consumes a bounded number of diagonals of each kind. Tile the remainder by Lemma 24.
Membership in NP is immediate. For hardness, suppose the formula is satisfiable and fix a satisfying assignment. Place each variable’s dominoes as in Lemma 20 according to its bit, each clause on a tooth belonging to one of its true literals, which exists and is available because by Lemma 20 no piece of that literal’s variable lies on the carrying diagonal and by construction no other gadget does, each anchor on its cell, and each filler on its private crossing. No two pieces conflict: two fillers are both dark and lie on distinct home down-diagonals and distinct private up-diagonals, so Lemma 15(b) is satisfied; a filler and a gadget piece differ in up-diagonal by at least two and in down-diagonal, so they satisfy Lemma 15(b) if of a colour and Lemma 15(c) if not; and gadget pieces are pairwise non-conflicting by the allocation. So a placement exists.
Conversely, let a placement be given. Each variable’s two dominoes take one of the up-diagonals 2U and 2U + 2 each, by Lemma 20, which reads off a bit. Each clause region has its piece on a tooth, since by Lemma 21 the anchors on its two up-diagonals leave nothing else available. That tooth lies on the down-diagonal carrying some literal of the clause, and no other piece lies on that diagonal — in particular neither piece of the corresponding variable — so by Lemma 20 the variable’s bit makes that literal true. Every clause therefore has a true literal, and the assignment satisfies the formula. The reduction is computable in polynomial time, the board having O((V + C)²) cells, and every region is orthogonally connected: dominoes are three cells in a row, anchors are single cells, clause regions are combs by Lemma 21, and fillers are staircases with adjacent cells attached by Lemma 24.
The two constructions are worth comparing. Under the knight’s rule the conflict relation is short-ranged, so no bit can be read at a distance and the whole difficulty is transporting one; a wire has to be a single region reduced to two usable cells, and Proposition 3 shows nothing shorter can turn a corner. Under the bishop’s rule transport is free, because a diagonal already spans the board; the difficulty moves to scarcity instead, since Lemma 16 caps the regions at 2n − 1 and forbids the board from being cut into many small ones. Lemma 18 is what resolves it, by making a long connecting path cost two pieces rather than one per cell.
This says nothing about the boards a generator produces. Any fixed board is of course decided in constant time, so the question is not about size but about shape: the reduction leans on long wires and on regions of a single cell, while a played board has regions of a few cells each, none of them huge and none of them a lone square. Whether the problem stays hard when region size is bounded by a constant, or when the regions are required to be compact as the board grows, is a separate question this construction does not address.
It is also worth contrasting with the unconstrained packing problems. Asking for the largest set of mutually non-attacking knights, with no regions at all, is in P: a knight’s move changes the colour of the square, so the knight’s graph is bipartite, and by König’s theorem the maximum independent set is the vertex count minus a maximum matching. The bishops packing problem is in P as well, and for a reason visible in Lemma 15: on either colour class the map (r, c) ↦ ((r+c)/2, (r−c)/2) carries diagonals to rows and columns, so non-attacking bishops become non-attacking rooks and the maximum is read off a matching. In both cases requiring one piece per region is what turns a two-dimensional matching problem into a three-dimensional one, and that is where the hardness enters.