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

Author

Heinrich Ludwig, May 07 2014

Keywords

• nonn
• hard
• more
• nice

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

Examples

			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 .
		

Links

• 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.

Crossrefs

Cf. A227133 (where we are concerned only with subsquares oriented parallel to the sides of the grid), A240114, A227308, A240444.

Extensions

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