The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points". At most points can be placed, because points in a grid would include a row of three or more points, by the pigeonhole principle. Although the problem can be solved with points for every up it is conjectured that fewer than points can be placed in grids of large size. Known methods can place linearly many points in grids of arbitrary size, but the best of these methods place slightly fewer than points, Several related problems of finding points with no three in line, among other sets of points than grids, have also been studied. Although originating in recreational mathematics, the no-three-in-line problem has applications in graph drawing and to the Heilbronn triangle problem. Small instances The problem was first posed by Henry Dudeney in 1900, as a puzzle in recreational mathematics, phrased in terms of placing the 16 pawns of a chessboard onto the board so that no three are in a line. This is exactly the no-three-in-line problem, for the In a later version of the puzzle, Dudeney modified the problem, making its solution unique, by asking for a solution in which two of the pawns are on squares d4 and e5, attacking each other in the center of the board. Many authors have published solutions to this problem for small values and by 1998 it was known that points could be placed on an grid with no three in a line for all up and some larger values. The numbers of solutions with points for small values of , starting are The numbers of equivalence classes of solutions with points under reflections and rotations are Upper and lower bounds The exact number of points that can be placed, as a function is not known. However, both proven and conjectured bounds limit this number to within a range proportional General placement methods A solution of Paul Erdős, published by , is based on the observation that when is a prime number, the set of grid points for contains no three collinear