Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!hellgate.utah.edu!csn!ub!ajay
From: ajay@cs.Buffalo.EDU (Ajay Shekhawat)
Newsgroups: comp.theory
Subject: RFI : Placement problems
Message-ID: <64094@eerie.acsu.Buffalo.EDU>
Date: 8 Mar 91 21:05:26 GMT
Sender: news@acsu.Buffalo.EDU
Reply-To: ajay@cs.Buffalo.EDU ( Ajay Shekhawat )
Organization: University at Buffalo, Dept. of Computer Science
Lines: 20
Nntp-Posting-Host: sybil.cs.buffalo.edu
Originator: ajay@sybil.cs.Buffalo.EDU



I'd like some info on the N-queens problem (how to place N 
queens on a N x N chessboard, so that they don't attack each 
other  ; N >= 4 ).
Is it possible to do better than a brute-force search? 

On a related note : I'd like references to the following
problem: I'd like to pick N integer points (points with 
integer coordinates) so that no three of them are collinear.
What is the size of the smallest square grid that is necessary?
Clearly the grid must be atleast N/2  x  N/2 .

Any help would be appreciated. If there's sufficient interest,
I'll post a summary of responses.

Ajay..

Ajay Shekhawat           <Dept. of Comp. Sci., SUNY@Buffalo, Amherst, NY 14260>
ajay@cs.Buffalo.EDU || ajay@sunybcs.BITNET || ajay@sunybcs.UUCP || 716.636.3180