The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A260090 Maximum number of kings on an n X n chessboard such that no king attacks more than one other king. 2
 1, 2, 4, 8, 12, 16, 21, 26, 33, 40, 48, 56, 65, 74, 85 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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. REFERENCES Dale Gerdemann et al., Discussions on Sequence Fans Mailing List, July 15 2015. Patricia Marx, Let's Be Less Stupid, Hachette, 2015. LINKS Manfred Scheucher, Python Script FORMULA 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 EXAMPLE 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 CROSSREFS A103139(n) and A181018(n) are upper bounds. A260113 is the corresponding sequence for queens. Cf. A103469. Sequence in context: A256409 A256403 A308013 * A256941 A324174 A047836 Adjacent sequences:  A260087 A260088 A260089 * A260091 A260092 A260093 KEYWORD nonn,more AUTHOR Rob Pratt, Jul 15 2015 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 30 05:35 EDT 2020. Contains 334712 sequences. (Running on oeis4.)