A260090 Maximum number of kings on an n X n chessboard such that no king attacks more than one other king.

1, 2, 4, 8, 12, 16, 21, 26, 33, 40, 48, 56, 65, 74, 85

Offset

1,2

Comments

Suggested by a problem involving parking cars in Marx (2015). The Marx problem is slightly different, however, since a solution in her book shows one car that is adjacent to two of its eight neighbors.

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 king's move apart. Let binary variable x[i] = 1 if a king 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. - Rob Pratt, Jul 16 2015

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

References

Dale Gerdemann et al., Discussions on Sequence Fans Mailing List, July 15 2015.

Patricia Marx, Let's Be Less Stupid, Hachette, 2015.

Links

Table of n, a(n) for n=1..15.

Manfred Scheucher, Python Script

Formula

Conjecture: For n != 3, a(n) = n(n+2)/3 + [n mod 3 = 2]/3 - [n mod 6 = 2]

Equivalent conjecture for n >= 5: a(n) = a(n-1) + n - A103469(n-2). - Bob Selcoe, Jul 17 2015

Example

a(8) = 26:
XX_XX_XX
________
XX_XX_XX
________
XX_XX_X_
_______X
X_X_X___
X_X_X_XX
a(15) = 85:
XX_XX_XX_XX_X_X
____________X_X
XX_X_X_X_XX____
___X_X_X____X_X
XX_______XX_X_X
___XX_XX_______
XX_______X_X_XX
___X_X_X_X_X___
XX_X_X_______XX
_______XX_XX___
X_X_XX_______XX
X_X____X_X_X___
____XX_X_X_X_XX
X_X____________
X_X_XX_XX_XX_XX

Crossrefs

A103139(n) and A181018(n) are upper bounds.

A260113 is the corresponding sequence for queens.

Cf. A103469.

Sequence in context: A256409 A256403 A308013 * A351873 A256941 A324174

Adjacent sequences: A260087 A260088 A260089 * A260091 A260092 A260093

Keyword

nonn,more

Author

Rob Pratt, Jul 15 2015

Status

approved