

A240443


Maximal number of points that can be placed on an n X n square grid so that no four of them are vertices of a square with any orientation.


6




OFFSET

1,2


COMMENTS

The first 9 elements of this sequence match other sequences in the OEIS, but so far it is not known whether this sequence is identical to any of them.
a(10) >= 50, a(11) >= 58.  Robert Israel, Apr 08 2016
a(12) >= 67.  Robert Israel, Apr 12 2016
a(13) >= 76, a(14) >= 86, a(15) >= 95, a(16) >= 106.  Peter Karpov, Jun 04 2016


LINKS

Table of n, a(n) for n=1..10.
Robert Israel, Illustration showing a(10) >= 50
Robert Israel, Illustration showing a(11) >= 58
Robert Israel, Illustration showing a(12) >= 67
Peter Karpov, Maximal density subsquarefree arrangements / #Optimization #OpenProblem / 2016.02.22, giving lower bounds for a(1)a(16).
Peter Karpov, Best configurations known for n = 13 .. 16
Giovanni Resta, Illustration of a(8) and a(9)
Dominik Stadlthanner, Python program
Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.


EXAMPLE

On a 9 X 9 grid a maximum of 42 points (x) can be placed so that no four of them are vertices of an (arbitrarily oriented) square. An example:
x x . . x . x . x
. x . . x x x x .
x x x . . x . . x
x . x x x . . x x
. . . . x x . . .
. x . x x . . . x
x x x . x . . . x
x . x . . . . x x
x . . x x x x x .


CROSSREFS

Cf. A227133 (where we are concerned only with subsquares oriented parallel to the sides of the grid), A240114, A227308, A240444.
Sequence in context: A231676 A056150 A310081 * A033439 A194082 A061786
Adjacent sequences: A240440 A240441 A240442 * A240444 A240445 A240446


KEYWORD

nonn,hard,more,nice


AUTHOR

Heinrich Ludwig, May 07 2014


EXTENSIONS

a(10) from Dominik Stadlthanner using integer programming, Apr 08 2020


STATUS

approved



