A260113 Maximum number of queens on an n X n chessboard such that no queen attacks more than one other queen.

1, 2, 3, 4, 5, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 28, 29, 30, 32, 33, 34, 36, 37, 38, 40

Offset

1,2

Comments

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

Links

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

a(30) = 40 and upper bound a(n) <= 4n / 3 from IBM Ponder This Challenge, August 2008

Giovanni Resta, Illustration of a(6)-a(30)

Manfred Scheucher, Python Script

Formula

Ponder This solution page shows a(6n) = 8n.

Example

a(8) = 10:
X-------
----XX--
-X------
-X------
------X-
------X-
--XX----
X-------

Crossrefs

A260090 is the corresponding sequence for kings.

Cf. A004773 (after Resta)

Sequence in context: A031999 A023760 A032901 * A005792 A270430 A318932

Adjacent sequences: A260110 A260111 A260112 * A260114 A260115 A260116

Keyword

nonn

Author

Rob Pratt, Jul 16 2015

Extensions

a(16)-a(30) from Giovanni Resta, Aug 07 2015

Status

approved