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

Author

Rob Pratt, Jul 16 2015

Keywords

• nonn

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.

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

Examples

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

Links

• IBM, Ponder This Challenge, August 2008 (a(30) = 40 and upper bound a(n) <= 4n / 3).
• Géza Makay, Proof that a(n) = floor(4*n/3) for large n (in Hungarian).
• Giovanni Resta, Illustration of a(6)-a(30)
• Manfred Scheucher, Python Script

Crossrefs

A260090 is the corresponding sequence for kings.

Cf. A004773 (after Resta).

Formula

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

Extensions

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