cp's OEIS Frontend

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

%I A260113 #28 Dec 15 2024 07:22:33
%S A260113 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 A260113 34,36,37,38,40
%N A260113 Maximum number of queens on an n X n chessboard such that no queen attacks more than one other queen.
%C A260113 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 A260113 An alternative formulation uses constraints x[i] + x[j] + x[k] <= 2 for each forbidden triple of nodes.
%C A260113 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.
%C A260113 a(n) = floor(4*n/3) for large n. - _Géza Makay_, Dec 13 2024
%H A260113 IBM, <a href="http://www.research.ibm.com/haifa/ponderthis/challenges/August2008.html">Ponder This Challenge, August 2008</a> (a(30) = 40 and upper bound a(n) <= 4n / 3).
%H A260113 Géza Makay, <a href="https://ematlap.hu/hettusa-2024-10/1448-kiralynok-a-tablan">Proof that a(n) = floor(4*n/3) for large n</a> (in Hungarian).
%H A260113 Giovanni Resta, <a href="/A260113/a260113.pdf">Illustration of a(6)-a(30)</a>
%H A260113 Manfred Scheucher, <a href="/A260113/a260113.py.txt">Python Script</a>
%F A260113 Ponder This solution page shows a(6n) = 8n.
%e A260113 a(8) = 10:
%e A260113   X-------
%e A260113   ----XX--
%e A260113   -X------
%e A260113   -X------
%e A260113   ------X-
%e A260113   ------X-
%e A260113   --XX----
%e A260113   X-------
%Y A260113 A260090 is the corresponding sequence for kings.
%Y A260113 Cf. A004773 (after Resta).
%K A260113 nonn
%O A260113 1,2
%A A260113 _Rob Pratt_, Jul 16 2015
%E A260113 a(16)-a(30) from _Giovanni Resta_, Aug 07 2015