graphs in the three-dimensional grid. Here the non-collinearity condition means that a vertex should not lie on a non-adjacent edge, but it is normal to work with the stronger requirement that no two edges cross. In much higher dimensions, sets of grid points with no three in line, obtained by choosing points near a hypersphere, have been used for finding large Salem–Spencer sets, sets of integers with no three forming an arithmetic progression. However, it does not work well to use this same idea of choosing points near a circle in two dimensions: this method finds points forming convex polygons, which satisfy the requirement of having no three in line, but are too small. The largest convex polygons with vertices in an grid have only vertices. The cap set problem concerns a similar problem to the no-three-in-line problem in spaces that are both high-dimensional, and based as vector spaces over finite fields rather than over the integers. Another generalization to higher dimensions is to find as many points as possible in a three dimensional grid such that no four of them are in the same plane. This sequence begins 5, 8, 10, 13, 16, ... for , etc. Torus Another variation on the problem involves converting the grid into a discrete torus by using periodic boundary conditions in which the left side of the torus is connected to the right side, and the top side is connected to the bottom side. This has the effect, on slanted lines through the grid, of connecting them up into longer lines through more points, and therefore making it more difficult to select points with at most two from each line. These extended lines can also be interpreted as normal lines through an infinite grid in the Euclidean plane, taken modulo the dimensions of the torus. For a torus based on an grid, the maximum number of points that can be chosen with no three in line is at most When both dimensions are equal, and prime, it is not possible to place exactly one point in each row and column without forming a linear number of collinear triples. Higher-dimensional torus versions of the problem have also been studied. See also Eight queens puzzle, on placing points on a grid with no two on the same row, column, or diagonal Notes References Solution, p. 222. Originally published in the London Tribune, November 7, 1906.