login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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.

From Rob Pratt, Mar 29 2014: (Start)

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] <= 2 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)

From Don Knuth, Aug 26 2014: (Start)

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

Table of n, a(n) for n=1..27.

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 arXiv:1206.5350 [math.CO].

Gregory S. Warrington, Illustration for n=8

CROSSREFS

Cf. A000769, A277433.

Sequence in context: A116446 A102126 A277433 * A097918 A256416 A256417

Adjacent sequences:  A219757 A219758 A219759 * A219761 A219762 A219763

KEYWORD

nonn,hard,more

AUTHOR

N. J. A. Sloane, Nov 29 2012

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified June 26 16:32 EDT 2017. Contains 288766 sequences.