Avoiding Colinear Points

[David Wasserman]

Good point.  Also, a single n-queens solution can already have 3 or more collinear points.

-*--------
---*------
-----*----
-------*--
---------*
*---------
--*-------
----*-----
------*---
--------*-

>There is no solution to the n-queens problem for n=2 or n=3.
>Besides, superimposing two n-queens solutions does not always yield 2n points.
>For example, here are two 8-queens solutions and their superposition, which only has 13 distinct points.
>
>--*-----
>-----*--
>-*------
>------*-
>*-------
>---*----
>-------*
>----*---
>
>
>--*-----
>-----*--
>-------*
>-*------
>---*----
>*-------
>------*-
>----*---
>
>Superimposed (13 points):
>
>--*-----
>-----*--
>-*-----*
>-*----*-
>*--*----
>*--*----
>------**
>----*---
>
>----- Original Message ----- From: "Jud McCranie" <j.mccranie at adelphia.net>
>To: "Leroy Quet" <qq-quet at mindspring.com>
>Cc: "Leroy Quet" <qq-quet at mindspring.com>; <seqfan at ext.jussieu.fr>
>Sent: Thursday, October 21, 2004 3:54 PM
>Subject: Re: Avoiding Colinear Points
>
>
>>At 04:44 PM 10/21/2004, Leroy Quet wrote:
>>
>>>I describe a sequence and game based on the following idea.
>>>
>>>If we have a rectangular grid of n lattice-points by n lattice-points,
>>>how many dots can we place at the lattice-points, at most one dot per
>>>lattice-point, so that no 3 or more dots are colinear (in any direction)?
>>>
>>>I get the sequence:
>>>1, 4, 6, 8, 10,..
>>>And Richard Mathar has extended it:
>>>12, 14, (15 or 16),...
>>>
>>>The upper bound on each term is obviously 2n, since we can have at most 2
>>>dots in each row  and column.
>>
>>There is an easy approach to this for nxn.  If you superimpose any two different n-queens solutions, you get a solution with no three colinear points.  Therefore 2n is always possible (for n > 1).