cp's OEIS Frontend

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

%I A260090 #48 Mar 26 2025 22:18:25
%S A260090 1,2,4,8,12,16,21,26,33,40,48,56,65,74,85,96,108,120,133,146,161,176,
%T A260090 192,208,225,242,261,280,300,320,341,362,385,408,432,456,481,506,533,
%U A260090 560,588,616,645,674,705,736,768,800,833,866,901,936,972,1008,1045
%N A260090 Maximum number of kings on an n X n chessboard such that no king attacks more than one other king.
%C A260090 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.
%C A260090 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
%C A260090 An alternative formulation uses constraints x[i] + x[j] + x[k] <= 2 for each forbidden triple of nodes.
%D A260090 Dale Gerdemann et al., Discussions on Sequence Fans Mailing List, July 15 2015.
%D A260090 Patricia Marx, Let's Be Less Stupid, Hachette, 2015.
%H A260090 Yifan Xie, <a href="/A260090/b260090.txt">Table of n, a(n) for n = 1..10000</a>
%H A260090 Manfred Scheucher, <a href="/A260090/a260090.py.txt">Python Script</a>
%F A260090 Conjecture: For n != 3, a(n) = n(n+2)/3 + [n mod 3 = 2]/3 - [n mod 6 = 2]
%F A260090 Equivalent conjecture for n >= 5: a(n) = a(n-1) + n - A103469(n-2). - _Bob Selcoe_, Jul 17 2015
%F A260090 See A381749 for proofs of the conjectures. - _Yifan Xie_, Mar 22 2025
%e A260090 a(8) = 26:
%e A260090   XX_XX_XX
%e A260090   ________
%e A260090   XX_XX_XX
%e A260090   ________
%e A260090   XX_XX_X_
%e A260090   _______X
%e A260090   X_X_X___
%e A260090   X_X_X_XX
%e A260090 a(15) = 85:
%e A260090   XX_XX_XX_XX_X_X
%e A260090   ____________X_X
%e A260090   XX_X_X_X_XX____
%e A260090   ___X_X_X____X_X
%e A260090   XX_______XX_X_X
%e A260090   ___XX_XX_______
%e A260090   XX_______X_X_XX
%e A260090   ___X_X_X_X_X___
%e A260090   XX_X_X_______XX
%e A260090   _______XX_XX___
%e A260090   X_X_XX_______XX
%e A260090   X_X____X_X_X___
%e A260090   ____XX_X_X_X_XX
%e A260090   X_X____________
%e A260090   X_X_XX_XX_XX_XX
%o A260090 (PARI) a(n)=if(n==3, 4, (n*(n+2) + if(n%3 == 2, 1, 0) - 3*if(n%6 == 2, 1, 0))/3); \\ _Yifan Xie_, Mar 22 2025
%Y A260090 A103139(n) and A181018(n) are upper bounds.
%Y A260090 A260113 is the corresponding sequence for queens.
%Y A260090 Cf. A103469, A381749.
%K A260090 nonn,easy
%O A260090 1,2
%A A260090 _Rob Pratt_, Jul 15 2015
%E A260090 More terms from _Yifan Xie_, Mar 22 2025