Knights and Bishops each ask for one piece in every region of a partitioned grid, with no two pieces attacking each other. Both are NP-complete. The two proofs look quite different, because the two rules are. A knight only reaches cells near it, so in the Knights proof information has to be carried by long regions. A bishop reaches the whole length of its diagonals, so in the Bishops proof information travels along diagonals, and the difficulty is that there are not many of them.
One piece in every region, and no two pieces touching or a knight’s move apart.
An instance of Knights is an n by n grid of cells divided into regions R1, …, Rk, each orthogonally connected. A placement chooses one cell from each region. Two cells u and v conflict when u − v is one of the sixteen offsets
C = { (±1, 0), (0, ±1), (±1, ±1), touching
(±1, ±2), (±2, ±1) } a knight's move
The question is whether some placement has no two conflicting cells. A placement can be checked by comparing every pair of its k cells, so Knights is in NP.
The set C is unchanged by negating offsets, by reflecting in either axis, and by swapping the two coordinates. So anything shown for one orientation of the board holds for all eight.
Every offset in C changes the row by at most 2 and the column by at most 2.
Lemma 1 is how we show that the parts of the construction do not affect each other: it is enough to keep them three rows or three columns apart. Below, the distance between two cells means the larger of their row difference and their column difference, so the lemma says that cells at distance 3 or more never conflict.
A common way to prove a puzzle like this hard is to let a region with two cells stand for a bit, and to pass the bit along a chain of such regions. For Knights this does not work, and the reason shapes the construction that follows. Nothing later depends on this section.
Say two disjoint regions A and B, each with two cells, form a link if exactly two of the four pairs (a, b) with a ∈ A and b ∈ B are free of conflict, and those two pairs use different cells of A and different cells of B. Then the cell used in A determines the cell used in B, and the other way round.
Write a0, a1 for the top and bottom cells of A, and b0, b1 for those of B. Then b0 − a0 = b1 − a1 = (δ, γ), while b1 − a0 = (δ+1, γ) and b0 − a1 = (δ−1, γ). The two pairs that use the same height conflict together or not at all. So there are two ways to get a link: (i) (δ, γ) is in C and neither (δ±1, γ) is, which leaves the two crossing pairs; or (ii) both (δ±1, γ) are in C and (δ, γ) is not, which leaves the two pairs at the same height.
Reading off C: an offset (d, γ) is in C exactly when d = ±1 if γ = 0; when |d| ≤ 2 if |γ| = 1; when d = ±1 if |γ| = 2; and never if |γ| ≥ 3.
If |γ| ≥ 3, nothing conflicts. If γ = 0, case (i) needs δ = ±1, so A and B share a cell, and case (ii) needs δ = 0, so B = A. If |γ| = 1, case (i) needs |δ| ≤ 2 together with |δ+1| ≥ 3 and |δ−1| ≥ 3, which is impossible, and case (ii) needs |δ| ≤ 1 together with |δ| ≥ 3, also impossible. If |γ| = 2, case (i) holds for δ = ±1 and case (ii) for δ = 0, and for no other δ.
By Lemma 2 each step moves exactly two columns and at most one row. Suppose the direction reverses at Di. Then Di−1 and Di+1 are in the same column, and their tops differ by at most two rows. A difference of 0 makes them the same region, a difference of 1 makes them share a cell, and a difference of 2 puts the bottom cell of one directly above the top cell of the other, so they conflict. All three contradict the hypotheses.
This is Lemma 1.
So two regions can only pass a bit between them if they come within two cells of each other, and a chain of two-cell regions cannot turn a corner. The construction below does not use chains. Each variable is a single region, long enough to reach every place where it is used, and everything else is arranged so that the region has only a few cells where its piece can go.
We reduce from a restricted form of satisfiability. A formula in conjunctive normal form is planar if its incidence graph is planar: the graph with a vertex for each variable and each clause, and an edge for each occurrence of a variable in a clause. Planar 3-satisfiability is NP-complete [Lichtenstein].
We also want every variable to occur at most three times and every literal at most twice. Both can be arranged while keeping the formula planar. If a variable x occurs k > 3 times, replace its occurrences by new variables x1, …, xk, in the order the occurrences appear around x in a planar drawing, and add the clauses
(¬x1 ∨ x2), (¬x2 ∨ x3), …, (¬xk ∨ x1)
which force all the copies to be equal. The new clauses can be drawn as a cycle around the place where x was, so the formula stays planar, and each copy occurs three times: once positively and once negatively in the new clauses, and once in the clause it replaced [Tovey]. Finally, a variable whose occurrences all have the same sign can be set to make them all true, and those clauses deleted. After this, every clause has at most three literals, every variable occurs at most three times, and every literal occurs at most twice.
A region with a single cell forces a piece onto that cell. The construction uses many of them. Call a cell dead if it conflicts with a one-cell region.
Every placement puts a piece on each one-cell region, and a piece on a dead cell would conflict with it.
The lattice is the set of cells whose row and column are both multiples of 3.
(a) Two different lattice points are at least three rows or three columns apart, so Lemma 1 applies.
(b) and (c) depend only on the row and column of the cell modulo 3. A cell with remainders (a, b) conflicts with one lattice point for each offset in C congruent to (−a, −b) modulo 3. For the remainders (0, 1), (0, 2), (1, 0) and (2, 0) there is one such offset, namely (0, −1), (0, 1), (−1, 0) and (1, 0): the lattice point next to the cell. For the other four remainders there are three. For example, for (1, 1) they are (−1, −1), (−1, 2) and (2, −1), and the lattice points they lead to differ pairwise by (0, 3), (3, 0) and (3, −3). The other three cases are reflections of this one.
We will put a one-cell region on almost every lattice point. The few lattice points without one are called open. For an open point P, the cross at P is the five cells P, P ± (1, 0) and P ± (0, 1).
A lattice point conflicts with no other lattice point, by Lemma 6(a), so an open point is not dead. A cell next to a lattice point P conflicts with no other lattice point, by Lemma 6(c), so it is dead exactly when P is not open. That covers the crosses. Every other cell outside the lattice conflicts with three lattice points at distance 3 from each other, and since open points are at least 6 apart, at most one of the three is open.
The conditions on the board make sure the lattice points this needs are on the board. Because the last row and column are multiples of 3, a cell next to a lattice point always has that lattice point on the board, and a cell that conflicts with three lattice points always has one of them diagonally next to it on the board. If that one is open, the cell is within one step of an open point and so at least 5 from the edge, and then all three of its lattice points are on the board, with at most one of them open.
Every open point in the construction is an end of a variable. At an end P, the variable’s region contains the three cells P − (1, 0), P and P + (1, 0) of the column through P. The two cells P ± (0, 1) beside it are reading cells, and they belong to the clauses that use the variable at that end.
From P + (0, 1) the three cells of the column are at offsets (−1, −1), (0, −1) and (1, −1), all touching; the other side is the mirror image. The two reading cells differ by (0, 2), which is not in C.
A variable region has two ends, at open points P and Q. It contains the column at each end, and a path joining the two along rows and columns whose index is not a multiple of 3, so that it meets no lattice point other than P and Q. If no clause reads the variable at one of its ends, the two cells beside that end belong to the variable region as well. Say the variable is true when its piece is at Q and false when it is at P.
By Lemma 7, the cells that are not dead are the cells of the crosses.
A clause containing the literal x reads it at the end where x’s variable puts its piece when x is false, which is P. A clause containing ¬x reads it at Q. Each literal occurs at most twice, so each end is read by at most two clauses, and if there are two, each takes one of the two reading cells. If an end is read by only one clause, that clause takes both reading cells, joined over the top of the column by the dead cells P − (1, ±1), P − (2, ±1) and P − (2, 0).
A clause region consists of its reading cells, at most three ends of at most three variables, and paths joining them, again along rows and columns that miss the lattice.
By Lemma 7 the clause can only use its reading cells. Take a reading cell beside the end E of a variable y. By Lemma 8 it conflicts with every cell of the column at E, and with nothing else that any other region can use: the other reading cell at E does not conflict with it, and the cells of every other cross are at least 4 away. So the cell is available exactly when y’s piece is not at E, which is exactly when the literal the clause reads there is true.
Start from the incidence graph of the formula and split each variable vertex into two vertices joined by an edge, its two ends: one carries the occurrences of x and the other those of ¬x. This keeps the graph planar. A variable has at most three edges, at most two of each sign, and of three edges around a vertex any two are next to each other in the circular order. So the edges of one sign can be pulled off together, without crossing anything. The new graph has maximum degree 3.
Every planar graph of maximum degree 4 can be drawn in the grid, with vertices at grid points and edges as paths along grid lines that meet only at common endpoints, in area polynomial in the size of the graph, and such a drawing can be found in polynomial time [Valiant]. Take such a drawing, enlarge it by a factor of 30, and shift it one row down and one column to the right, so that every grid line becomes a row or column whose index is one more than a multiple of 3 and so contains no lattice point. Each vertex becomes a block of 30 by 30 cells, and each edge becomes a path along one of those rows or columns, at least 30 cells from every other edge’s path except where two edges meet.
Inside the block of an end, put its open point at a lattice point near the middle of the block and arrange the paths that arrive there as in the figure of an end: the variable’s path leaves the column downward and turns along the row two below the open point, and the clause paths come down the two columns beside it. That fixes one circular order of the three paths. Reflecting the picture left to right gives the other order, and since C does not change when the board is turned a quarter turn, the paths can arrive from any side of the block. Inside the block of a clause, the paths of its edges simply meet, so a clause region is a tree.
Now make the regions. Every lattice point that is not an open point becomes a one-cell region. Each variable region is the two columns at its ends with the path between them, and each clause region is its reading cells with the paths of its edges. Every remaining cell is dead, by Lemma 7, and is added to a region next to it (Lemma 5). This is possible because the cells that are not one-cell regions form a connected set, so every group of remaining cells touches some region.
The size, the side and the distances come from the drawing, the enlargement, and a margin of a few rows and columns around it. Variable and clause regions are paths and trees, and adding remaining cells to a neighbouring region keeps it connected. The paths run along rows and columns that contain no lattice point, and they stay at least 30 cells from the ends they do not use. Inside the block of an end, the arrangement in the figure meets the cross only in the cells described.
Knights is in NP. For hardness, build the board above from a formula. This takes polynomial time.
Suppose the formula has a satisfying assignment. Put a piece on every one-cell region. Put each variable’s piece on the middle of the column at the end given by its value. Put each clause’s piece on a reading cell of one of its true literals. One-cell regions do not conflict with each other (Lemma 6(a)) or with any other piece, since every other piece is on a cell that is not dead. Pieces in different crosses are at least 4 apart. Within one cross, a clause piece is only placed where the variable’s piece is not, and two clause pieces there do not conflict (Lemma 8). So the placement has no conflicts.
Conversely, take a placement without conflicts. By Lemma 9 each variable’s piece is at one of its ends, which gives a value to every variable. By Lemma 10 each clause’s piece is on a reading cell for some literal, and the variable of that literal does not have its piece at that end, so the literal is true. Every clause has a true literal, so the formula is satisfied.
One piece in every region, and no two pieces on a common diagonal or orthogonally next to each other.
An instance of Bishops is again an n by n grid divided into orthogonally connected regions. Two cells conflict when they lie on a common diagonal or are orthogonally next to each other. That is, u − v is (±1, 0), (0, ±1), or (±t, ±t) for some t ≥ 1. Bishops is in NP for the same reason as Knights.
Call a cell (r, c) dark when r + c is even and light otherwise. Its up-diagonal is r + c and its down-diagonal is r − c.
A diagonal step changes r + c by 0 or ±2, which gives (a). An orthogonal step changes the colour, so cells of the same colour are never orthogonally next to each other, which gives (b). Cells of different colours share no diagonal, by (a), which gives (c).
The up-diagonals are numbered 0 to 2n − 2. The even ones contain dark cells and the odd ones light cells, so there are n up-diagonals of dark cells and n − 1 of light ones. By Lemma 12, a dark piece uses up one up-diagonal and one down-diagonal of dark cells, and has no effect on light pieces except on its four orthogonal neighbours.
Pieces of the same colour are on different up-diagonals, by Lemma 12(b). So there are at most n dark pieces and n − 1 light ones.
So the regions of a solvable board are few, and on average they have at least about n/2 cells. A reduction cannot cut the board into many small regions. The construction below uses small regions only for the gadgets, and puts everything else into one large region.
Joining two distant cells into one region takes a path between them, and every cell of the path is a cell the region might use. In the Knights construction those cells are ruled out by the lattice of one-cell regions. Here that would take far too many regions, so we use paths that can be ruled out by just two pieces.
A staircase is a path that alternates horizontal and vertical steps, always one cell right and one cell down, or always one cell left and one cell down.
A step right lowers r − c by one and a step down raises it by one, and each step changes the colour. So r − c alternates between two neighbouring values, one on the dark cells and one on the light cells. For left and down the same argument applies to r + c.
By Lemma 14 every cell of the staircase shares a diagonal with one of the two pieces, and has its colour, by Lemma 12(a). By Lemma 12(b) they conflict.
Ruling out a region one cell at a time would use up the scarce diagonals of Lemma 13, but a staircase of any length costs two pieces.
Satisfiability is NP-complete for formulas whose clauses have at most three literals and whose variables each occur at most three times [Tovey]. As before, we may also assume every literal occurs at most twice. The formula does not need to be planar, because diagonals can cross each other.
For integers U and V, the bar B(U, V) is the three cells (r, c), (r, c+1), (r, c+2) with r = U + V and c = U − V.
For the left end, r + c = 2U and r − c = 2V. Each step to the right adds one to r + c and subtracts one from r − c. The last part is Lemma 12(b).
Each bar can only use its two ends, on up-diagonals 2U and 2U + 2 (Lemma 16). Both pieces are dark, so they cannot share an up-diagonal, and one takes each. The down-diagonals then follow from Lemma 16.
Let the variable x be true when B(U, V) uses its left end. Then the down-diagonals 2V − 2 and 2W carry no piece of this variable exactly when x is true, and 2V and 2W − 2 carry none exactly when x is false. We say the first two diagonals show the literal x and the second two show ¬x. A diagonal runs across the whole board, so a clause anywhere on the board can read a literal from it.
Each occurrence of a literal in a clause is read on one of the two down-diagonals that show it. A literal occurs at most twice, so different occurrences can always use different diagonals.
(b) and (c) are direct calculations of r + c and r − c. For (a), the staircase cells, taken in order of w and alternating between the two kinds, form a staircase going left and down: from (T+w, T−w−1) one step down reaches (T+w+1, T−w−1), and one step left from there reaches (T+w+1, T−w−2). The cell to the right of the literal cell for vi is (T−1+vi, T−vi), which is the staircase cell of the second kind with w = vi − 1, and that value is in range. The last sentence is Lemma 15.
With its staircase ruled out, a clause’s piece goes on one of its literal cells, and it can only go on the cell for vi if no other piece is on down-diagonal 2vi. When the literal read there is false, the literal’s variable has a piece on that diagonal (Lemma 17). So a clause can only be placed if one of its literals is true. The proof of Theorem 2 shows the converse, by keeping every other piece off those diagonals.
The regions have to cover the whole board. All the cells not used by a variable, a clause or a one-cell region go into one more region, the filler. It needs to be connected, and it needs a cell where its piece can always go.
A gadget is a variable with its two bars, a clause region, or a one-cell region, and its group is the set of up-diagonals its cells lie on. A variable’s group is three up-diagonals, 2U to 2U + 2; a clause’s group is 2T − 2 to 2T, and it includes the two one-cell regions that rule out the clause’s staircase; each one-cell region that rules out a bar’s middle cell has a group of one up-diagonal.
Two neighbouring up-diagonals that no gadget uses form a staircase going left and down from one edge of the board to another, so their cells are connected. The cells within two of the edge are all free and connected to each other, and every such staircase reaches them, so all of these staircases are connected together.
It remains to connect the free cells on the up-diagonals of a group. A free cell on the first or last up-diagonal of a group is orthogonally next to a cell of the unused up-diagonal beside the group. A group of three up-diagonals also has a middle one, and a free cell there has two neighbours on each of the other two; at least one of these four is free. For a variable, the middle up-diagonal 2U + 1 is next to only the four bar ends, and since the bars are at least three rows apart, a free cell touches at most one of them. For a clause, a free cell on the middle up-diagonal 2T − 1 lies beyond the end of the staircase, so neither of its two neighbours on 2T is in the staircase, and at most one of them is the one-cell region there.
Take a formula in which every clause has at most three literals and every literal occurs at most twice, and let N be its number of variables plus its number of clauses. Choose the following, all on a board of side n = O(N):
A cell with up-diagonal u and down-diagonal d is on the board when |d| ≤ u ≤ 2n − 2 − |d|. The choices above use O(N) up-diagonals and O(N) down-diagonals, so they fit with all up-diagonals near n and all down-diagonals near 0 once n is a large enough multiple of N. Finally every remaining cell goes into the filler, which is connected by Lemma 19.
Bishops is in NP, and the board above is built in polynomial time. Its regions are bars, clause regions (connected by Lemma 18), one-cell regions, and the filler (connected by Lemma 19).
Suppose the formula has a satisfying assignment. Place each variable’s bars according to its value, each one-cell region on its cell, and each clause on the literal cell of a true literal. For the filler, take a dark cell on an unused up-diagonal whose down-diagonal carries no other piece and which is not next to a light one-cell region; there are far more diagonals than pieces, so such a cell exists. Now check the pairs. The dark pieces are the bar ends, the literal cells used by clauses, the dark one-cell regions, and the filler. They are on different up-diagonals, because different gadgets have different groups and the two bars of a variable use different up-diagonals. They are on different down-diagonals: a clause’s piece is on a diagonal that shows a true literal, which carries no piece of that literal’s variable (Lemma 17) and, by the choices above, no piece of anything else. The light pieces are one-cell regions on different diagonals. A dark piece and a light piece conflict only if they are orthogonally next to each other, and the choices above keep the light one-cell regions away from every cell a dark piece uses. So there are no conflicts.
Conversely, take a placement without conflicts. By Lemma 17 each variable’s bars give it a value. By Lemma 18 each clause’s piece is on a literal cell, on a down-diagonal that shows one of its literals. No other piece is on that diagonal, in particular no piece of the literal’s variable, so by Lemma 17 the literal is true. Every clause has a true literal, so the formula is satisfied.
In Knights a piece only affects cells within two steps of it. A bit cannot be passed between small regions over any distance, so each variable is one long region, and the work in the proof is making sure that region has only a few cells where its piece can go: the lattice of one-cell regions rules out everything except small crosses at chosen points.
In Bishops a piece affects its entire diagonals, so a variable’s value can be read anywhere along a diagonal at no cost. The limit is instead the number of regions, at most 2n − 1. Joining far-apart cells into one region without giving it many usable cells is done with staircases, which two pieces rule out completely.