A260113 - OEIS

%I #17 Aug 07 2015 11:28:29

%S 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,

%T 34,36,37,38,40

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

%C 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.

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

%C 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

%H a(30) = 40 and upper bound a(n) <= 4n / 3 from <a href="http://www.research.ibm.com/haifa/ponderthis/challenges/August2008.html">IBM Ponder This Challenge, August 2008</a>

%H Giovanni Resta, <a href="/A260113/a260113.pdf">Illustration of a(6)-a(30)</a>

%H Manfred Scheucher, <a href="/A260113/a260113.py.txt">Python Script</a>

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

%e a(8) = 10:

%e X-------

%e ----XX--

%e -X------

%e -X------

%e ------X-

%e ------X-

%e --XX----

%e X-------

%Y A260090 is the corresponding sequence for kings.

%Y Cf. A004773 (after Resta)

%K nonn

%O 1,2

%A _Rob Pratt_, Jul 16 2015

%E a(16)-a(30) from _Giovanni Resta_, Aug 07 2015