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