Skip to main content
4 of 7
added 7 characters in body

How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional grid of m x m points?

I'm seeking the definition of some function $f(n,m)$ which evaluates to the number of distinct sets of $n$ collinear points which are selected from an evenly-spaced two-dimensional grid of $m \times m$ points?

Collinear in this case means that the points in the set fall exactly on some line with arbitrary slope, that is, it is not limited to horizontal, or vertical, or 45° diagonal lines.


To make sure I'm asking the correct question, I'm attempting to code a solution to a variation of the n-queens problem which adds the constraint that no three queens may fall along the same line of arbitrary slope (inspired by the "no three in a line" problem). I'm attempting to encode the problem as constraints to a theorem prover, and to check that I'm not creating redundant constraint expressions, I'd like to calculate the expected number of clauses for this constraint. At present I'm adding one constraint per unique triple of collinear spaces on the board.

I ask the question for the general case as I'm curious to quantify how many fewer clauses I'd need if the constraint were lessened to "no 4 in a line" or "no 5 in a line" and so on.