User:25Punkte/16 Punkte en

Challenge

4 by 4 dot grid

On a grid of 4 by 4 dots, i.e. 16 dots, a polyline consisting of 6 lines should be laid out in such a way that each dot is touched by a line at least once. The challenge is an extension of the nine-point problem, which is not easy to solve even with the knowledge that the polyline has to be extended beyond the dot grid. The solutions outside Euclidean geometry are discussed in the Nine-Dot problem.

History

The nine-point problem was already described in in Sam Loyd's 1914 Cyclopedia of Puzzles. and extending it to larger grids or more dimensions is close-by.

1985 in the book Creative Puzzles of the World the extension from 9 to 16 dots was described with one solution.

The 16-dot challenge was described in Psychology Today in 2009. 2013 Marco Ripà presented that the puzzle can be solved, starting from any dot.

The challenge was set in May 2019 as Rätsel der Woche (puzzle of the week) in the online edition of Der Spiegel and was solved there in the discussion of the article and subsequently in the Matheplanet forum.

Symmetry

Additional solutions can be created by rotating a solution by 90°, 180°, 270° and mirroring and reversing the direction of the solution or combinations thereof. These are not considered independent solutions here and are therefore not listed in the table. Similarly, additional solutions created by extending the start or end line are not counted separately. Because of the last condition, all polylines listed here start and end at dots that are touched by only one line. All solutions of the 4 by 4 problem start at one of the three dots A1 (solutions 1–26), A2 (solutions 27–39) or B3 (solutions 40–42), because all other grid points can be mapped to these three dots by rotation or mirroring.

Notation and Sequence

Notation of the dots

To name the dots, the rows are marked from top to bottom with the letters A–D, the columns with numbers 1–4 from left to right. The point A1 is the corner dot at the top left. A solution consists of a sequence of at least 16 dots. The lines within the polyline are separated by a comma. A vertex is listed twice, as the end point of the incoming line and as the starting point of the outgoing line. The picture shows a corresponding notation for the nine-dot problem.

Alternative notations:

• Numbers can also be used for the rows, so that the notation corresponds to that of points in Analytic Geometry. The dot A1 can be written as (0,0) or (1,1).
• Notation of the 16 dots with hexadecimal digits 0...9,a...f
• Specification of exactly two points, first and last point, for each line, each solution is thus given by 12 points. Vertex dots are given twice, as end point of the previous line and start point of the next line. This notation has the advantage that all solutions are of equal length.

The solutions are sorted here by the columns and rows of the touched dots. So at first the solutions that start at dot A1 and since there are several, then those that continue at dot A2 and so on.

Solutions that can be derived from a previous solution by a symmetry operation (see above) are not listed in the table.

Categories

Solution categories

To group similar solutions, the lines can be extended to form straight lines. Solutions with the same set of straight lines can be assigned to a common category. According to this definition, there are 12 categories, each with 6 straight lines. They are marked in the table with K1...K12. For the sequence of the categories, the order of the categories in the discussion of the Spiegel article is maintained here.

A grouping of the results is also possible according to other criteria. Some of them are listed in columns in the solution table below. In addition, the furthest leaving of the dot grid was also discussed. and similarly, which maximum value for denominator or numerator occurs if the slopes are written as integer fractions.

Remarkable Solutions

• Solutions 19 and 36, category K4 are both closeable, each dot is only touched once, without a vertex at a dot, and they have two mirror symmetries along the horizontal and vertical central axes and can be mapped to themselves by a 180° rotation. They are considered by many to be particularly elegant.
• The solutions for category K1 are often the first to be found. This category also includes the shortest solutions and solution 14, which includes the smallest area outside the grid.

Other Grid Sizes

Starting from 3 by 3 dots the required number of lines is given by the formula $2(n-1)$ if $n$ represents the number of dots along one side.

This is one line less than a simple solution "circle inwards" or the parallel striking of all rows and connecting these lines .

For the 3 by 3 challenge there is exactly one solution with the above mentioned limitations, which is shown in the table below. With the symmetry conditions selected here, there are 42 solutions for the 4 by 4 problem. For larger grids the number of solutions increases rapidly.

Complete solution sets can be calculated with computer assistance. One approach is to connect the grid dots and stop the try when the maximum number of lines in the polyline is exceeded and to changed the last dot unless all options are tried and then change the preceding dot (Backtracking). Another approach is to place the given number of lines in a way that all dots are touched and the lines can be connected to one polyline.

A proof was given by Marco Ripá on Vixra that there a no solutions with less lines possible for square dot grids.

With the rules to create a solution given below is is shown that its possible to solve a n by n grid with $2(n-1)$ lines.

In all solutions, each line touches at least two dots and at least one line touches n dots, which is the highest value possible. It is assumed that this also is true for larger grids.

General Solution for n by n Grids

General solution for n >= 5

The 3 by 3 solution ends with a horizontal line at one corner. Every solution of this kind can be extended by two lines from a n by n to a (n+1) by (n+1) solution. In the picture the extension to 4 by 4 is shown with dark blue dots right and top (#14 in the table of the 4 x 4 solutions), which can be extended by the same method left and bottom to 5 by 5, the additional dots shown in purple. Starting from this 5 by 5 solution there are no additional dots touched twice (marked orange) and the lines of the solution need not leave the grid, which is unique to the smaller grids and was the reason for the name "thinking outside the box". The 5 by 5 solution shown here can be extended by adding a polyline on the right and on top to a 6 by 6 solution and so on. For large n the shown solution is in the middle, surrounded by a spiral.

Solution for n by n Grids, without Multiple Touched Dots

Solution w/o multiple dots

There is a rule that creates a solution without multiple dots for many large $n$. To do this, two separate polylines are first created and then connected. (For naming: N is the letter belonging to n, e.g. for n=26, Z is to be used for N):

• Create first polyline:
  • At corner dot bottom right Nn (in picture F6, blue) starting upwards to the corner dot top right: An (in picture A6)
  • turning left the diagonal line to the bottom left to the corner dot at the bottom left: N1 (in the picture F1)
  • turning further left, every time before an occupied dot is reached, until only one dot (in the picture orange, E4) is left over

• Rotated by 180, the same for the remaining triangle in the upper left corner, as a second polyline:
  • Starting at A1 (green in the picture) down to dot (N-1)1 (E1 in the picture)
  • turning left the first upper secondary diagonal to the top right until A(n-1) (in figure A5)
  • turning further left, in each case before reaching an occupied dot, until only one dot (orange in the picture, B3) is left

• Connection of the two polylines
  • Connect the two remaining free dots and extend this line up to the extensions of the vertical starting lines right Nn An (in figure F6 A6) and left A1 (N-1)1 (in figure A1 E1).

If n is not divisible by 6 with the remainder 3, the connecting line is not touching other grid dots. The solution for the 4 by 4 grid created according to this rule is shown in the table as number 28. The rule does not provide a solution for the 3 by 3 grid: the remaining dots are vertically stacked so that the connecting line cannot be connected to the two start lines.

Table Columns

• The Length indicates the length of the polyline in the unit of the grid spacing. The connection A1 A2 has the length 1, the diagonal connection A1 B2 the length 1.41.
• The Rotation Symmetry indicates how many rotations the solution can be mapped to itself. The maximum value would be the value for the grid, i.e. 4 or symmetry for rotation by 90°. A symmetry is also given if its only visible after the end lines have been extended.
• The Mirror Symmetry indicates whether the solution can be mapped to itself by mirroring on the diagonal, vertical or horizontal center axes.
• Multi Dots indicates how many dots are touched by more than one line.
• A solution is marked as Closable if the extension of the start and end line intersect. These solutions have several similar solutions of the same category, because the polyline can be split at each corner that protrudes from the grid square.
• The column Left Turns shows how often the polyline changes turn direction while passing through. Coming from diagonal A1 B2 C3, the continuation C2 C1 would have turned left, the continuation B3 A3 would have turned right. Each polyline has 5 directional changes. A reflection or reversal of direction changes every left turn into a right turn and vice versa.
• Vertices are counted if a line does not pass a dot straight, but changes direction at the dot. In the sequence from the 3 by 3 solution: A1 B2 C3, C3 B3 A3, C3 is a vertex. In the sequence A2 B1, C1 C2 the dots are passed straight through, the vertex is not on the grid of dots but at C0, which is on the left side, outside of the grid.

Table of all Solutions to the 3 x 3 Challenge

Num­ber	Picture	Dot Sequence	Length	Rotation Sym­metry	Mirror Sym­metry	Multi Dots	Clos­able	Left Turns	Vertices
1		A1 B2 C3, C3 B3 A3, A2 B1, C1 C2	12.07	0	1	0	no	3	1

Table of all Solutions to the 4 x 4 Challenge

Num­ber	Picture	Dot Sequence	Cate­gory	Length	Rotation Sym­metry	Mirror Sym­metry	Multi Dots	Clos­able	Left Turns	Vertices
1		A1 A2 A3 A4, B3 C1, D1 D2 D3 D4, C4 B2, B1 C2, C3 B4	K8	30.07	0	1	0	no	4	0
2		A1 A2 A3 A4, A4 B3 C2 D1, D1 C1 B1, B2 C4, D4 D3 D2, D2 C3 B4	K2	22.16	0	0	0	no	0	3
3		A1 A2 A3 A4, A4 B3 C2 D1, D2 C4, B4 B3 B2 B1, C1 D3, D4 C3	K11	31.90	0	1	1	yes	4	1
4		A1 A2 A3 A4, A4 B3 C2 D1, D1 D2 D3 D4, C4 B2, B1 C1 D1, D2 C3 B4	K2	25.58	0	0	2	no	4	2
5		A1 A2 A3 A4, B4 C1, D1 D2 D3 D4, C4 B2, B1 C2 D3, D3 C3 B3	K10	36.44	0	0	1	no	4	1
6		A1 A2 A3 A4, B4 C3, C2 B1, B2 C4, D4 D3 D2 D1, C1 B3	K8	29.25	0	1	0	no	0	0
7		A1 A2 A3 A4, B4 C3 D2, D2 C2 B2 A2, A2 B3 C4, D4 D3 D2 D1, D1 C1 B1	K1	21.49	0	1	2	yes	0	3
8		A1 A2 A3 A4, B4 C3 D2, D1 C1 B1, B1 B2 B3 B4, B4 C4 D4, D3 C2	K1	21.49	0	1	1	yes	0	2
9		A1 A2 A3 A4, B4 C3 D2, D1 C1 B1, B2 C4, D4 D3 D2 D1, D1 C2 B3	K2	26.58	0	0	2	no	0	1
10		A1 A2 A3 A4, B4 C3 D2, D1 C1 B1, B1 C2 D3, D4 C4 B4, B4 B3 B2	K1	21.90	0	0	1	no	2	2
11		A1 A2 A3 A4, B4 C3 D2, D2 D3 D4, C4 B2, B1 C1 D1, D1 C2 B3	K2	23.16	0	0	0	no	4	2
12		A1 A2 A3 A4, A4 B4 C4 D4, D3 C2 B1, B1 B2 B3 B4, B4 C3 D2, D1 C1	K1	20.49	0	1	1	yes	0	3
13		A1 A2 A3 A4, A4 B4 C4 D4, D3 C2 B1, B1 C1 D1, D2 C3 B4, B4 B3 B2	K1	20.49	0	0	1	no	3	3
14		A1 A2 A3 A4, A4 B4 C4 D4, D4 D3 D2 D1, C1 B2 A3, A3 B3 C3 D3, D3 C2 B1	K1	20.07	0	1	2	yes	0	4
15		A1 A2 A3 A4, C4 D2, D1 C2, C3 D4, D3 C1, B1 B2 B3 B4	K11	34.72	0	0	0	no	0	0
16		A1 A2 A3, A3 B3 C3 D3, D3 D2 D1, C1 B2 A3, A4 B4 C4 D4, D3 C2 B1	K1	22.90	0	1	2	yes	0	2
17		A1 B2 C3 D4, C4 A3, A2 B1, C1 D2, D3 B4, A4 B3 C2 D1	K12	27.88	0	1	0	no	5	0
18		A1 B2 C3 D4, C4 A3, A2 B2 C2 D2, D3 B4, A4 B3 C2 D1, D1 C1 B1	K11	33.73	0	1	2	yes	4	1
19		A1 B2 C3 D4, C4 A3, A2 C1, D1 C2 B3 A4, B4 D3, D2 B1	K4	32.85	2	2	0	yes	5	0
20		A1 B2 C3 D4, D4 C4 B4 A4, A2 C1, D1 C2 B3 A4, A3 B1, D1 D2 D3	K5	42.20	0	1	2	no	5	1
21		A1 B2 C3 D4, D4 D3 D2 D1, D1 C2 B3 A4, A3 B1, C1 C2 C3 C4, B4 A2	K11	31.08	0	1	2	yes	2	2
22		A1 B3, C4 C3 C2 C1, B1 A2, A3 B4, D4 D3 D2 D1, B2 A4	K9	32.67	0	0	0	no	0	0
23		A1 B3, C4 C3 C2 C1, B1 A2, A4 B4 C4 D4, D4 D3 D2 D1, C1 B2 A3	K3	28.37	0	0	2	no	0	1
24		A1 B3, C4 C3 C2 C1, C1 B2 A3, A4 B4 C4 D4, D4 D3 D2 D1, B1 A2	K3	25.96	0	0	1	no	0	2
25		A1 B3, D4 D3 D2 D1, B1 A2, A4 B4 C4, C4 C3 C2 C1, C1 B2 A3	K3	31.61	0	0	0	no	0	2
26		A1 B3, D4 D3 D2 D1, C1 B2 A3, A4 B4 C4, C4 C3 C2 C1, B1 A2	K3	29.19	0	0	1	no	0	1
27		A2 A1, B1 C2 D3, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3, D3 C3 B3	K1	23.31	0	1	1	yes	5	1
28		A2 A3 A4, A4 B3 C2 D1, D1 C1 B1 A1, B2 D3, D4 C4 B4, B4 C3 D2	K2	23.78	0	0	0	no	2	3
29		A2 A3 A4, B4 C3 D2, D1 C1 B1 A1, B2 D3, D4 C4 B4 A4, A4 B3 C2	K2	28.19	0	0	2	no	2	1
30		A2 A3 A4, B4 C3 D2, D1 C1 B1 A1, B3 D4, D3 C2 B1, B2 C4	K6	36.14	0	0	1	no	0	0
31		A2 B2 C2 D2, D3 B4, A4 C3 B2 D1, D1 C1 B1 A1, A3 C4, D4 C3	K11	36.14	0	0	1	no	2	1
32		A2 B2 C2 D2, D3 B4, A4 C3 B2 D1, D1 C1 B1 A1, A1 B2 C3 D4, C4 A3	K11	30.49	0	1	2	yes	3	2
33		A2 B3, C3 D2, D1 C1 B1 A1, B2 D3, D4 C4 B4 A4, A3 C2	K8	28.84	0	1	0	no	3	0
34		A2 B3 C4, D4 D3 D2 D1, C1 B2 A3, A4 D3, D2 B1, A1 B4	K7	30.75	0	0	0	no	0	0
35		A2 B3 C4, D4 D3 D2 D1, D1 C1 B1 A1, A1 B2 C3 D4, D4 C4 B4 A1, A3 C2	K2	24.96	0	0	2	no	2	3
36		A2 C1, D1 C2 B3 A4, B4 D3, D2 B1, A1 B2 C3 D4, C4 A3	K4	34.27	2	2	0	yes	5	0
37		A2 C1, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3, D3 C2 B1, A1 B3	K9	28.26	0	0	0	no	4	1
38		A2 C3, D3 D2 D1, C1 B2 A3, A1 B4 C4 D4, D3 C2 B1, A1 B3	K9	29.05	0	0	1	no	0	0
39		A2 C3, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3 D4, B3 A1, B1 C2	K9	35.32	0	0	1	no	5	0
40		B2 C1, D1 D2 D3 D4, D4 C4 B4 A4, A4 A3 A2 A1, B1 C2 D3, D3 C3 B3	K1	20.07	0	1	1	yes	0	3
41		B2 C2 D2, D1 C3 B4, A4 A3 A2 A1, B2 C4, D4 D3 D2 D1, C1 B3	K10	35.20	0	0	1	no	3	1
42		B2 C3 D4, D4 C4 B4 A4, A4 A3 A2 A1, B1 C2 D3, D3 D2 D1, C1 B3	K2	22.54	0	0	0	no	3	3