No-Three-in-a-Line Problem

Author

Eric W. Weisstein
July 21, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/PointLattices/No-Three-in-a-LineProblem.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/No-Three-in-a-LineProblem.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

Code

(* Verify no-three-in-line configurations from point lists or arrays. *)

NoThreeInLinePoints[input_SparseArray] :=
	Cases[Most[ArrayRules[input]], (pos_ -> value_) /; value =!= 0 :> pos]

NoThreeInLinePoints[input_List] /; VectorQ[input, MatchQ[#, {_Integer, _Integer}] &] :=
	input

NoThreeInLinePoints[input_?MatrixQ] :=
	Position[input, Except[0]]

NoThreeInLinePoints[_] :=
	$Failed

NoThreeLineKey[{x1_Integer, y1_Integer}, {x2_Integer, y2_Integer}] := Module[
	{a = y2 - y1, b = x1 - x2, c = x2 y1 - x1 y2, g, key},
	g = GCD[a, b, c];
	key = {a, b, c}/g;
	If[key[[1]] < 0 || (key[[1]] === 0 && key[[2]] < 0),
		-key,
		key
	]
]

NoThreeSquareTransformations[n_Integer?Positive] := <|
	"Identity" -> (# &),
	"Rot90" -> ({n + 1 - #[[2]], #[[1]]} &),
	"Rot180" -> ({n + 1 - #[[1]], n + 1 - #[[2]]} &),
	"Rot270" -> ({#[[2]], n + 1 - #[[1]]} &),
	"VerticalReflection" -> ({n + 1 - #[[1]], #[[2]]} &),
	"HorizontalReflection" -> ({#[[1]], n + 1 - #[[2]]} &),
	"MainDiagonalReflection" -> ({#[[2]], #[[1]]} &),
	"AntiDiagonalReflection" -> ({n + 1 - #[[2]], n + 1 - #[[1]]} &)
|>

NoThreeInvariantQ[points_, transform_] :=
	Sort[transform /@ points] === Sort[points]

NoThreeSymmetryReport[points_, n_:Automatic] := Module[
	{
		gridSize = n, transformations, invariantTransformations, rot90Q, rot180Q,
		rot270Q, reflectionAxes, rotationSymmetry, pointGroup, flammenkampRotationClass
	},
	If[points === {},
		Return[<|
			"GridSize" -> gridSize,
			"RotationSymmetry" -> "C1",
			"RotationOrder" -> 1,
			"PointGroup" -> "C1",
			"ReflectionAxes" -> {},
			"InvariantTransformations" -> {},
			"FlammenkampRotationClass" -> "identity"
		|>, Module]
	];
	If[gridSize === Automatic,
		gridSize = Max[points]
	];
	If[!IntegerQ[gridSize] || gridSize <= 0,
		Return[$Failed, Module]
	];
	transformations = NoThreeSquareTransformations[gridSize];
	invariantTransformations = Keys[Select[transformations, NoThreeInvariantQ[points, #] &]];
	rot90Q = MemberQ[invariantTransformations, "Rot90"];
	rot180Q = MemberQ[invariantTransformations, "Rot180"];
	rot270Q = MemberQ[invariantTransformations, "Rot270"];
	reflectionAxes = Intersection[
		invariantTransformations,
		{"VerticalReflection", "HorizontalReflection", "MainDiagonalReflection", "AntiDiagonalReflection"}
	];
	rotationSymmetry = Which[
		rot90Q && rot270Q, "C4",
		rot180Q, "C2",
		True, "C1"
	];
	pointGroup = Which[
		rotationSymmetry === "C4" && reflectionAxes =!= {}, "D4",
		rotationSymmetry === "C4", "C4",
		rotationSymmetry === "C2" && reflectionAxes =!= {}, "D2",
		rotationSymmetry === "C2", "C2",
		reflectionAxes =!= {}, "Cs",
		True, "C1"
	];
	flammenkampRotationClass = Which[
		rotationSymmetry === "C4", "rot4",
		rotationSymmetry === "C2", "rot2",
		True, "identity"
	];
	<|
		"GridSize" -> gridSize,
		"RotationSymmetry" -> rotationSymmetry,
		"RotationOrder" -> Switch[rotationSymmetry, "C4", 4, "C2", 2, _, 1],
		"PointGroup" -> pointGroup,
		"ReflectionAxes" -> reflectionAxes,
		"InvariantTransformations" -> invariantTransformations,
		"FlammenkampRotationClass" -> flammenkampRotationClass
	|>
]

NoThreeInLineReport[input_, n_:Automatic] := Module[
	{
		points = NoThreeInLinePoints[input],
		uniquePoints, duplicatePoints, outOfBoundsPoints, rowCounts, columnCounts,
		maxRowCount, maxColumnCount, pairs, badPairClass, collinearTriple,
		expectedPointCount, countOK, boundsOK, symmetryReport
	},
	If[points === $Failed,
		Return[$Failed, Module]
	];
	uniquePoints = DeleteDuplicates[points];
	duplicatePoints = Keys[Select[Counts[points], # > 1 &]];
	outOfBoundsPoints = If[n === Automatic,
		{},
		Select[points, !AllTrue[#, 1 <= # <= n &] &]
	];
	rowCounts = Counts[If[points === {}, {}, points[[All, 1]]]];
	columnCounts = Counts[If[points === {}, {}, points[[All, 2]]]];
	maxRowCount = Max[Join[Values[rowCounts], {0}]];
	maxColumnCount = Max[Join[Values[columnCounts], {0}]];
	pairs = Subsets[Range[Length[uniquePoints]], {2}];
	badPairClass = SelectFirst[
		GatherBy[pairs, NoThreeLineKey[uniquePoints[[#[[1]]]], uniquePoints[[#[[2]]]]] &],
		Length[#] >= 3 &,
		{}
	];
	collinearTriple = If[badPairClass === {},
		{},
		uniquePoints[[Take[Union[Flatten[badPairClass]], UpTo[3]]]]
	];
	expectedPointCount = If[n === Automatic, Automatic, 2 n];
	countOK = expectedPointCount === Automatic || Length[points] === expectedPointCount;
	boundsOK = outOfBoundsPoints === {};
	symmetryReport = NoThreeSymmetryReport[uniquePoints, n];
	<|
		"Valid" -> (countOK && boundsOK && duplicatePoints === {} && maxRowCount <= 2 &&
			maxColumnCount <= 2 && collinearTriple === {}),
		"PointCount" -> Length[points],
		"ExpectedPointCount" -> expectedPointCount,
		"DuplicatePoints" -> duplicatePoints,
		"OutOfBoundsPoints" -> outOfBoundsPoints,
		"MaxRowCount" -> maxRowCount,
		"MaxColumnCount" -> maxColumnCount,
		"CollinearTriple" -> collinearTriple,
		"Symmetry" -> symmetryReport
	|>
]

NoThreeInLineQ[input_, n_:Automatic] := Module[
	{report = NoThreeInLineReport[input, n]},
	If[AssociationQ[report],
		report["Valid"],
		False
	]
]

NoThreeInARowPlot[data_,n_]:=Module[
{lab=StringRiffle[Table[ToString[Length[data]/2],2]," × "]},
If[n>0,lab=lab<>" #"<>ToString[n]];
ArrayPlot[SparseArray[data-> 1], Mesh -> True,PlotLabel->lab,BaseStyle->Directive[14,"FontFamily"->"Times"]]
]

NoThreeInARowPlot[data_]:=NoThreeInARowPlot[data,0]

Solutions

52×52

NoThreeInARowArray[52]={{1,27},{1,29},{2,17},{2,40},{3,40},{3,43},{4,11},{4,22},{5,27},{5,34},{6,7},{6,36},{7,23},{7,47},{8,12},{8,44},{9,8},{9,34},{10,3},{10,30},{11,37},{11,49},{12,39},{12,45},{13,2},{13,3},{14,12},{14,20},{15,20},{15,32},{16,11},{16,35},{17,6},{17,51},{18,16},{18,22},{19,5},{19,9},{20,38},{20,39},{21,15},{21,29},{22,35},{22,49},{23,10},{23,46},{24,1},{24,21},{25,25},{25,28},{26,1},{26,5},{27,48},{27,52},{28,25},{28,28},{29,32},{29,52},{30,7},{30,43},{31,4},{31,18},{32,24},{32,38},{33,14},{33,15},{34,44},{34,48},{35,31},{35,37},{36,2},{36,47},{37,18},{37,42},{38,21},{38,33},{39,33},{39,41},{40,50},{40,51},{41,8},{41,14},{42,4},{42,16},{43,23},{43,50},{44,19},{44,45},{45,9},{45,41},{46,6},{46,30},{47,17},{47,46},{48,19},{48,26},{49,31},{49,42},{50,10},{50,13},{51,13},{51,36},{52,24},{52,26}};

65×65

https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html

On Jun. 18, 2026, Marijn Heule used his SAT solver to find the first known solution for n=65 in Flammenkamp's rct4 symmetry class.

NoThreeInARowArray[65]={{1,43},{1,53},{2,27},{2,49},{3,10},{3,12},{4,32},{4,35},{5,21},{5,51},{6,22},{6,30},{7,7},{7,18},{8,32},{8,43},{9,40},{9,52},{10,55},{10,63},{11,10},{11,18},{12,21},{12,63},{13,1},{13,31},{14,9},{14,49},{15,5},{15,19},{16,37},{16,39},{17,2},{17,14},{18,55},{18,59},{19,33},{19,51},{20,26},{20,38},{21,54},{21,61},{22,24},{22,60},{23,1},{23,8},{24,41},{24,44},{25,24},{25,29},{26,9},{26,46},{27,16},{27,64},{28,20},{28,30},{29,16},{29,41},{30,38},{30,60},{31,4},{31,53},{32,58},{32,62},{33,19},{33,47},{34,4},{34,8},{35,13},{35,62},{36,6},{36,28},{37,25},{37,50},{38,36},{38,46},{39,2},{39,50},{40,20},{40,57},{41,37},{41,42},{42,22},{42,25},{43,58},{43,65},{44,6},{44,42},{45,5},{45,12},{46,28},{46,40},{47,15},{47,33},{48,7},{48,11},{49,52},{49,64},{50,27},{50,29},{51,47},{51,61},{52,17},{52,57},{53,35},{53,65},{54,3},{54,45},{55,48},{55,56},{56,3},{56,11},{57,14},{57,26},{58,23},{58,34},{59,48},{59,59},{60,36},{60,44},{61,15},{61,45},{62,31},{62,34},{63,54},{63,56},{64,17},{64,39},{65,13},{65,23}};

67×67

https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html

On Jun. 21, 2026, Marijn Heule found the first known solution for n=67 in Flammenkamp's rct4 symmetry class.

NoThreeInARowArray[67]={{1,38},{1,44},{2,32},{2,44},{3,36},{3,47},{4,11},{4,12},{5,16},{5,25},{6,19},{6,53},{7,19},{7,33},{8,8},{8,43},{9,45},{9,54},{10,17},{10,42},{11,12},{11,64},{12,57},{12,64},{13,16},{13,34},{14,9},{14,28},{15,6},{15,30},{16,55},{16,63},{17,50},{17,58},{18,17},{18,23},{19,61},{19,62},{20,31},{20,39},{21,3},{21,31},{22,40},{22,42},{23,9},{23,50},{24,1},{24,2},{25,8},{25,63},{26,10},{26,22},{27,29},{27,33},{28,22},{28,54},{29,20},{29,41},{30,1},{30,53},{31,47},{31,48},{32,3},{32,66},{33,41},{33,61},{34,13},{34,55},{35,7},{35,27},{36,2},{36,65},{37,20},{37,21},{38,15},{38,67},{39,27},{39,48},{40,14},{40,46},{41,35},{41,39},{42,46},{42,58},{43,5},{43,60},{44,66},{44,67},{45,18},{45,59},{46,26},{46,28},{47,37},{47,65},{48,29},{48,37},{49,6},{49,7},{50,45},{50,51},{51,10},{51,18},{52,5},{52,13},{53,38},{53,62},{54,40},{54,59},{55,34},{55,52},{56,4},{56,11},{57,4},{57,56},{58,26},{58,51},{59,14},{59,23},{60,25},{60,60},{61,35},{61,49},{62,15},{62,49},{63,43},{63,52},{64,56},{64,57},{65,21},{65,32},{66,24},{66,36},{67,24},{67,30}};

68×68

NoThreeInARowArray[68]=1+{{12,0},{14,0},{26,1},{38,1},{35,2},{46,2},{36,3},{38,3},{25,4},{33,4},{18,5},{48,5},{40,6},{44,6},{44,7},{54,7},{14,8},{32,8},{11,9},{19,9},{25,10},{39,10},{45,11},{58,11},{52,12},{67,12},{7,13},{52,13},{59,14},{67,14},{12,15},{13,15},{24,16},{31,16},{28,17},{33,17},{40,18},{62,18},{5,19},{58,19},{43,20},{46,20},{2,21},{20,21},{11,22},{26,22},{6,23},{7,23},{20,24},{51,24},{57,25},{63,25},{45,26},{66,26},{6,27},{18,27},{10,28},{50,28},{1,29},{3,29},{30,30},{37,30},{3,31},{51,31},{2,32},{59,32},{50,33},{63,33},{4,34},{17,34},{8,35},{65,35},{16,36},{64,36},{30,37},{37,37},{64,38},{66,38},{17,39},{57,39},{49,40},{61,40},{1,41},{22,41},{4,42},{10,42},{16,43},{47,43},{60,44},{61,44},{41,45},{56,45},{47,46},{65,46},{21,47},{24,47},{9,48},{62,48},{5,49},{27,49},{34,50},{39,50},{36,51},{43,51},{54,52},{55,52},{0,53},{8,53},{15,54},{60,54},{0,55},{15,55},{9,56},{22,56},{28,57},{42,57},{48,58},{56,58},{35,59},{53,59},{13,60},{23,60},{23,61},{27,61},{19,62},{49,62},{34,63},{42,63},{29,64},{31,64},{21,65},{32,65},{29,66},{41,66},{53,67},{55,67}};

69×69

https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html

On Jun. 21, 2026, Marijn Heule found two solutions for n=69; Flammenkamp's downloadable configuration file lists them in the rct4 symmetry class.

NoThreeInARowArray[{69,1}]={{1,24},{1,28},{2,37},{2,54},{3,33},{3,47},{4,26},{4,34},{5,15},{5,22},{6,43},{6,60},{7,29},{7,39},{8,8},{8,48},{9,46},{9,58},{10,6},{10,19},{11,26},{11,34},{12,9},{12,20},{13,39},{13,41},{14,23},{14,32},{15,19},{15,65},{16,2},{16,35},{17,18},{17,25},{18,25},{18,53},{19,55},{19,60},{20,30},{20,58},{21,38},{21,42},{22,8},{22,65},{23,3},{23,56},{24,9},{24,69},{25,52},{25,53},{26,59},{26,66},{27,6},{27,30},{28,21},{28,69},{29,13},{29,63},{30,43},{30,50},{31,7},{31,13},{32,21},{32,56},{33,2},{33,67},{34,59},{34,66},{35,16},{35,54},{36,4},{36,11},{37,3},{37,68},{38,14},{38,49},{39,57},{39,63},{40,20},{40,27},{41,7},{41,57},{42,1},{42,49},{43,40},{43,64},{44,4},{44,11},{45,17},{45,18},{46,1},{46,61},{47,14},{47,67},{48,5},{48,62},{49,28},{49,32},{50,12},{50,40},{51,10},{51,15},{52,17},{52,45},{53,45},{53,52},{54,35},{54,68},{55,5},{55,51},{56,38},{56,47},{57,29},{57,31},{58,50},{58,61},{59,36},{59,44},{60,51},{60,64},{61,12},{61,24},{62,22},{62,62},{63,31},{63,41},{64,10},{64,27},{65,48},{65,55},{66,36},{66,44},{67,23},{67,37},{68,16},{68,33},{69,42},{69,46}};

NoThreeInARowArray[{69,2}]={{1,40},{1,44},{2,21},{2,34},{3,47},{3,50},{4,27},{4,33},{5,57},{5,59},{6,28},{6,46},{7,7},{7,23},{8,11},{8,38},{9,50},{9,57},{10,12},{10,25},{11,5},{11,62},{12,14},{12,60},{13,5},{13,9},{14,36},{14,58},{15,18},{15,22},{16,44},{16,53},{17,16},{17,38},{18,27},{18,55},{19,28},{19,40},{20,3},{20,9},{21,39},{21,68},{22,35},{22,55},{23,3},{23,63},{24,6},{24,41},{25,39},{25,60},{26,1},{26,16},{27,52},{27,66},{28,51},{28,64},{29,24},{29,33},{30,1},{30,19},{31,21},{31,25},{32,8},{32,17},{33,41},{33,66},{34,14},{34,68},{35,22},{35,48},{36,2},{36,56},{37,4},{37,29},{38,53},{38,62},{39,45},{39,49},{40,51},{40,69},{41,37},{41,46},{42,6},{42,19},{43,4},{43,18},{44,54},{44,69},{45,10},{45,31},{46,29},{46,64},{47,7},{47,67},{48,15},{48,35},{49,2},{49,31},{50,61},{50,67},{51,30},{51,42},{52,15},{52,43},{53,32},{53,54},{54,17},{54,26},{55,48},{55,52},{56,12},{56,34},{57,61},{57,65},{58,10},{58,56},{59,8},{59,65},{60,45},{60,58},{61,13},{61,20},{62,32},{62,59},{63,47},{63,63},{64,24},{64,42},{65,11},{65,13},{66,37},{66,43},{67,20},{67,23},{68,36},{68,49},{69,26},{69,30}};

70×70

https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html

On 17th June 2026 Marijn Heule of Carnegie Mellon University (Pittsburgh, Pennsylvania, USA) used a newly developed SAT (Boolean satisfiability) solver to find a solution for n=70 in the rot4 symmetry class.

NoThreeInARowArray[70]=1+{{0,16},{0,34},{1,18},{1,48},{2,30},{2,31},{3,41},{3,43},{4,6},{4,23},{5,22},{5,56},{6,59},{6,65},{7,31},{7,43},{8,54},{8,60},{9,8},{9,48},{10,6},{10,37},{11,15},{11,32},{12,49},{12,52},{13,5},{13,34},{14,24},{14,25},{15,8},{15,58},{16,29},{16,69},{17,12},{17,19},{18,25},{18,68},{19,22},{19,52},{20,12},{20,29},{21,1},{21,9},{22,50},{22,64},{23,33},{23,65},{24,39},{24,55},{25,51},{25,55},{26,3},{26,7},{27,28},{27,33},{28,3},{28,42},{29,49},{29,53},{30,24},{30,67},{31,62},{31,67},{32,10},{32,58},{33,42},{33,46},{34,56},{34,69},{35,0},{35,13},{36,23},{36,27},{37,11},{37,59},{38,2},{38,7},{39,2},{39,45},{40,16},{40,20},{41,27},{41,66},{42,36},{42,41},{43,62},{43,66},{44,14},{44,18},{45,14},{45,30},{46,4},{46,36},{47,5},{47,19},{48,60},{48,68},{49,40},{49,57},{50,17},{50,47},{51,1},{51,44},{52,50},{52,57},{53,0},{53,40},{54,11},{54,61},{55,44},{55,45},{56,35},{56,64},{57,17},{57,20},{58,37},{58,54},{59,32},{59,63},{60,21},{60,61},{61,9},{61,15},{62,26},{62,38},{63,4},{63,10},{64,13},{64,47},{65,46},{65,63},{66,26},{66,28},{67,38},{67,39},{68,21},{68,51},{69,35},{69,53}};

72×72

NoThreeInARowArray[72]=1+{{32,71},{37,71},{29,70},{38,70},{43,69},{49,69},{24,68},{30,68},{27,67},{51,67},{9,66},{43,66},{51,65},{61,65},{55,64},{57,64},{23,63},{54,63},{19,62},{66,62},{6,61},{40,61},{30,60},{44,60},{23,59},{47,59},{55,58},{56,58},{7,57},{31,57},{13,56},{21,56},{7,55},{13,55},{8,54},{36,54},{42,53},{46,53},{34,52},{62,52},{4,51},{6,51},{38,50},{56,50},{2,49},{35,49},{59,48},{63,48},{12,47},{68,47},{18,46},{45,46},{25,45},{39,45},{11,44},{67,44},{2,43},{5,43},{18,42},{70,42},{60,41},{68,41},{10,40},{57,40},{26,39},{71,39},{1,38},{21,38},{0,37},{52,37},{17,36},{49,36},{22,35},{54,35},{19,34},{71,34},{50,33},{70,33},{0,32},{45,32},{14,31},{61,31},{3,30},{11,30},{1,29},{53,29},{66,28},{69,28},{4,27},{60,27},{32,26},{46,26},{26,25},{53,25},{3,24},{59,24},{8,23},{12,23},{36,22},{69,22},{15,21},{33,21},{65,20},{67,20},{9,19},{37,19},{25,18},{29,18},{35,17},{63,17},{58,16},{64,16},{50,15},{58,15},{40,14},{64,14},{15,13},{16,13},{24,12},{48,12},{27,11},{41,11},{31,10},{65,10},{5,9},{52,9},{17,8},{48,8},{14,7},{16,7},{10,6},{20,6},{28,5},{62,5},{20,4},{44,4},{41,3},{47,3},{22,2},{28,2},{33,1},{42,1},{34,0},{39,0}};

74×74

On July 20, 2026, Thomas Prellberg found a solution for n=74 in the rot4 symmetry class.

NoThreeInARowArray[74]=1+{{28,73},{48,73},{19,72},{29,72},{33,71},{51,71},{4,70},{58,70},{55,69},{70,69},{23,68},{43,68},{27,67},{37,67},{23,66},{33,66},{18,65},{54,65},{20,64},{62,64},{29,63},{36,63},{9,62},{41,62},{48,61},{52,61},{46,60},{59,60},{13,59},{22,59},{3,58},{31,58},{16,57},{57,57},{20,56},{34,56},{4,55},{65,55},{8,54},{72,54},{56,53},{64,53},{12,52},{28,52},{2,51},{59,51},{66,50},{68,50},{43,49},{47,49},{0,48},{12,48},{24,47},{39,47},{13,46},{67,46},{52,45},{73,45},{63,44},{72,44},{5,43},{24,43},{35,42},{58,42},{11,41},{38,41},{66,40},{71,40},{26,39},{56,39},{32,38},{42,38},{6,37},{63,37},{10,36},{67,36},{31,35},{41,35},{17,34},{47,34},{2,33},{7,33},{35,32},{62,32},{15,31},{38,31},{49,30},{68,30},{1,29},{10,29},{0,28},{21,28},{6,27},{60,27},{34,26},{49,26},{61,25},{73,25},{26,24},{30,24},{5,23},{7,23},{14,22},{71,22},{45,21},{61,21},{9,20},{17,20},{1,19},{65,19},{8,18},{69,18},{39,17},{53,17},{16,16},{57,16},{42,15},{70,15},{51,14},{60,14},{14,13},{27,13},{21,12},{25,12},{32,11},{64,11},{37,10},{44,10},{11,9},{53,9},{19,8},{55,8},{40,7},{50,7},{36,6},{46,6},{30,5},{50,5},{3,4},{18,4},{15,3},{69,3},{22,2},{40,2},{44,1},{54,1},{25,0},{45,0}};

Checks

Keys[arrays=DownValues[NoThreeInARowArray]]

TextGrid[{#,NoThreeInLineReport[#2]}&@@@arrays,Dividers->All]

Figure

GraphicsGrid[Partition[Function[downValue,With[{key=downValue[[1,1,1]]},NoThreeInARowPlot[downValue[[2]],If[ListQ[key],Last[key],0]]]]/@SortBy[arrays,First[Flatten[{#1[[1,1,1]]}]]&],UpTo[3]],ImageSize->800]