cp's OEIS Frontend

Can be formulated as an integer linear programming problem as follows. Define a graph with a node for each cell and an edge for each pair of cells that are a queen's move apart. Let binary variable x[i] = 1 if a queen appears at node i, and 0 otherwise. The objective is to maximize sum x[i]. Let N[i] be the set of neighbors of node i. To enforce the rule that x[i] = 1 implies sum {j in N[i]} x[j] <= 1, impose the linear constraint sum {j in N[i]} x[j] - 1 <= (|N[i]| - 1) * (1 - x[i]) for each i.

An alternative formulation uses constraints x[i] + x[j] + x[k] <= 2 for each forbidden triple of nodes.

Taking into account known values, it is reasonable to conjecture that a(n) = floor(4*n/3) for n > 5. - Giovanni Resta, Aug 07 2015.

a(n) = floor(4*n/3) for large n. - Géza Makay, Dec 13 2024

Two kings attack each other if their corresponding cells have a common point.

Define a graph G = (V,E), where V is the set of kings and E includes all pairs of attacking kings. Then the constraint is equivalent to all connected components of G having 1 or 2 kings. Denote the connected components of G by blocks.

Extend the board P to P' by adding a row at the bottom and a column at the right. Define the neighborhood of a block B as the union of the 2 X 2 squares whose upper-left corner is a cell in B.

The neighborhoods of permitted blocks are shown, with B marked by 'X' and the remaining part of B's neighborhood by '-':

X- XX- X- X-- X-

--; ---; X- -X- X--

--; ---; -- .

Suppose that a cell C is in the neighborhoods of two distinct blocks B1 and B2. Then B1 and B2 both have a cell in the 2 X 2 square whose lower-right corner is C, but these two cells must be neighbor to each other, a contradiction.

Therefore, the neighborhoods of all blocks in P are non-overlapping in P'. Note that the size of a block's neighborhood is at least three times the size of the block. That is, T(n,k) <= (n+1)*(k+1)/3.

Also, note that 2 X 6 and 3 X 6 boards can be tiled with 6-sized neighborhoods, so m X 6 boards, where m > 1, can also be tiled with 6-sized neighborhoods. Therefore, the remaining details are not tedious to work with since a n X k board can generally be reduced to a (n mod 6) X (k mod 6) board.

Two cells are edge-adjacent if they have a common edge.

T(n,1) and the upper bound are shown by blackening the left two cells in each three consecutive cells (refer to T(8,1) example).

If both n and k are even, T(n,k) is reached by checkerboard coloring. The upper bound follows from T(2,2) = 2.

Suppose that k is odd. T(n,k) can be constructed by applying the T(n,1) construction on each odd-numbered row, and the coloring of even-numbered rows opposite to odd-numbered ones (refer to T(7,7) example). If n is even, the upper bound follows from T(n,k) <= T(n,k-1) + T(n,1).

If n is odd, we choose an up-and-right path visiting cells a_1, a_2, ..., a_(n+k-1) in that order. Set a_1 as the lower-left corner and a_(n+k-1) as the upper-right corner. The edge a_(2i) - a_(2i+1) continues the previous direction. If a_(2i+1) is not on the upper edge or on the right edge, choose a_(2i+2) such that a_(2i+1) and a_(2i+2) are not both black; Suppose the contrary, and then a_(2i+1) and its upper and right neighbors are all black, a contradiction.

Therefore we divide the grid into the upper-left and lower-right parts, each of which can be divided into 2 X 2 grids, so there are at most (n-1)*(k-1)/2 black cells. As for the path, the part not on the upper edge or on the right edge has no more than half black cells, while the edge part contains at most n cells, hence T(n,k) <= (n-1)*(k-1)/2 + (k-1)/2 + T(n,1) = n*(k-1)/2 + ceiling(2*n/3).

The following example illustrates the colored grid and the corresponding path:

XX_XX_XX_ ......XX_

_X__X__X ........

X_XX_XX ....X_X..

X_X__X__X ...._....

X_X_X_XX_ X_X_X....

__X_X__X ........

XX_X_X_X_ X........