|
|
A219760
|
|
Martin Gardner's minimal no-3-in-a-line problem.
|
|
5
|
|
|
1, 4, 4, 4, 6, 6, 8, 9, 10, 10, 12, 12, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25, 26, 26, 28, 29, 30
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(n) is the minimal number of counters that can be placed on an n X n chessboard, no three in a line, such that adding one more counter on any vacant square will produce three in a line.
Can be computed by using integer linear programming (ILP) as follows.
The ILP formulation uses two sets of binary decision variables:
x[i,j] = 1 if a queen appears in square (i,j), 0 otherwise
y[k] = 1 if line k contains exactly two queens, 0 otherwise
Let SQUARES[k] be the set of squares that appear in line k, and let LINES[i,j] be the set of lines that contain square (i,j), so that (i,j) is in SQUARES[k] iff k is in LINES[i,j]. Then we have the following constraints:
2 y[k] <= sum {(i,j) in SQUARES[k]} x[i,j] <= 1 + y[k] for all lines k [no 3-in-a-line, and if y[k] = 1 then exactly two queens appear in line k]
x[i,j] + sum {k in LINES[i,j]} y[k] >= 1 for all squares (i,j) [either a queen appears in square (i,j) or some line that contains square (i,j) contains exactly two queens]
The objective is to minimize the sum of all x[i,j].
(End)
a(26)=26: there is a solution in which every queen appears in an odd-numbered row and an odd-numbered column, and furthermore cell (i,j) is occupied if and only if cell (j,i) is occupied. Such solutions exist when n=10, 18, 26. Conversely it's known that a(n)>=n when n is even.
There are many ways to place n+1 queens that satisfy the conditions, with queens occupying only "white" squares (if the top left corner square is white), at least for n<=30.
(End)
This is for the "queens" version of the problem, where "lines" are vertical, horizontal and diagonal only. The version where lines can have any slope is A277433. - Robert Israel, Oct 26 2016
|
|
LINKS
|
Alec S. Cooper, Oleg Pikhurko, John R. Schmitt, and Gregory S. Warrington, Martin Gardner's minimum no-3-in-a-line problem, Amer. Math. Monthly, 121 (2014), 213-221 (on JSTOR), DOI: 10.4169/amer.math.monthly.121.03.213. Also on arXiv, arXiv:1206.5350 [math.CO], 2012-2014.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Terms a(13)-a(18) from Rob Pratt, Mar 29 2014
Terms a(19)-a(27) from Rob Pratt, Sep 05 2014
|
|
STATUS
|
approved
|
|
|
|