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.

1, 3, 6, 10, 15, 21, 27, 34, 42, 50

Offset

1,2

Comments

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 subsquare-free 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: A056150 A310081 A357779 * 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