A260113 -id:A260113 - 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.

1, 2, 4, 8, 12, 16, 21, 26, 33, 40, 48, 56, 65, 74, 85, 96, 108, 120, 133, 146, 161, 176, 192, 208, 225, 242, 261, 280, 300, 320, 341, 362, 385, 408, 432, 456, 481, 506, 533, 560, 588, 616, 645, 674, 705, 736, 768, 800, 833, 866, 901, 936, 972, 1008, 1045

Offset: 1

Rob Pratt, Jul 15 2015

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.
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
An alternative formulation uses constraints x[i] + x[j] + x[k] <= 2 for each forbidden triple of nodes.

			a(8) = 26:
  XX_XX_XX
  ________
  XX_XX_XX
  ________
  XX_XX_X_
  _______X
  X_X_X___
  X_X_X_XX
a(15) = 85:
  XX_XX_XX_XX_X_X
  ____________X_X
  XX_X_X_X_XX____
  ___X_X_X____X_X
  XX_______XX_X_X
  ___XX_XX_______
  XX_______X_X_XX
  ___X_X_X_X_X___
  XX_X_X_______XX
  _______XX_XX___
  X_X_XX_______XX
  X_X____X_X_X___
  ____XX_X_X_X_XX
  X_X____________
  X_X_XX_XX_XX_XX

Dale Gerdemann et al., Discussions on Sequence Fans Mailing List, July 15 2015.
Patricia Marx, Let's Be Less Stupid, Hachette, 2015.

Yifan Xie, Table of n, a(n) for n = 1..10000
Manfred Scheucher, Python Script

A103139(n) and A181018(n) are upper bounds.
A260113 is the corresponding sequence for queens.
Cf. A103469, A381749.

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

Conjecture: For n != 3, a(n) = n(n+2)/3 + [n mod 3 = 2]/3 - [n mod 6 = 2]
Equivalent conjecture for n >= 5: a(n) = a(n-1) + n - A103469(n-2). - Bob Selcoe, Jul 17 2015
See A381749 for proofs of the conjectures. - Yifan Xie, Mar 22 2025

More terms from Yifan Xie, Mar 22 2025

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions