Longest Pathology Puzzles By Size

This wiki page documents the longest known PP1 and PP2 puzzles which fit within small $M \times N$ rectangles.

Outside of trivial cases, these numbers should be considered lower bounds for the longest possible puzzles of various sizes.

To preview and play any of these levels, just copy the level data into the Pathology Level Creator

PP1

In PP1, all boxes can be pushed from all sides and there are no holes.

We have the following results for small PP1 puzzles:

	2	3	4	5	6	7	8	N
1	1	2	3	4	5	6	7	$N - 1$
2	2	4	5	7	9	10	12	$\lfloor\frac{3N}{2}\rfloor$
3		8	11	14	17	20	23	$3 N - 1$
4			14	18	26	30	34	$4 (N + \lfloor\frac{N}{3}\rfloor) - 6$
5				34	40	46	54	?
6					49	57	65	?
7						66	76	?
8							90	?

The results for rectangular boards with at most 25 spaces have been confirmed optimal by mathmasterzach by exhaustive computer search.

$1 \times N$

Trivial construction of the form: 40...03

$2 \times 2$

40
03

$2 \times 3$

413
000

$2 \times 4$

4113
0000

$2 \times N$

For odd $N \geq 5$, the optimal is a zig-zag pattern.

41000
00013

For even $N > 5$, the optimal is a zig-zag pattern with a delaying block at the start.

041000
020003

$3 \times N$

A lock with a long handle.

00...020
41...123
00...020

$4 \times 4$

Two very different solutions, found by Flashback and dgriff24 respectively.

$4 \times 5$

Expanded version of dgriff24's $4 \times 4$

3 More designs by davidspencer6174

$4 \times 6$

By davidspencer6174

$4 \times 7$

Expanded version of davidspencer6174's $4 \times 6$

$4 \times 8$

Expanded version of davidspencer6174's $4 \times 6$

$4 \times N$

The best we know so far is a continuation of the above pattern with "wiggles": Ex.

000000100000130
011110001110422
010001110001200
000100000100201

$5 \times 5$

Hem's hemlock

$5 \times 6$

By davidspencer6174

$5 \times 7$

By davidspencer6174

$5 \times 8$

By davidspencer6174

$6 \times 6$

By Hem

$6 \times 7$

By Hem

$6 \times 8$

By Hem

$7 \times 7$

By davidspencer6174

$7 \times 8$

By davidspencer6174

$8 \times 8$

Hem's Boundary Unstable

PP2/Pathology

We have the following results for small PP2 puzzles:

	2	3	4	5	6	7	8	N
1	1	2	3	4	5	6	7	$N - 1$
2	2	4	6	10	16	19	24	$\Theta(N^2)$
3		10	16	32	46	56	70	$N^2 + 3N - 17$
4			30	58	104	110	133	?
5				118	149	173	197	?
6					168	250	274	?
7						262	366?	?
8							504?	?

$2 \times N$

The longest $2 \times 2$ and $2 \times 3$ match the results for PP1.

The longest $2 \times 4$, 5, and 6, were found by LifereaperX: LifereaperX's 2x4, LifereaperX's 2x5, LifereaperX's 2x6

sspenst provides a general construction for an $2 \times N$ with $N > 5$.

if $N = 0 \mod 3$ then we can achieve $\frac{N^2 + 2N}{3}$ steps

For $N = 6$ we have:

310000
552024

To scale this puzzle, insert $3 \times 2$ segments of the form:

000
520

Between the last hole and the first box, ex.

310000 -> 310000000 -> 310000000000
552024 -> 555202024 -> 555520202024

if $N = 1 \mod 3$ then we can achieve $\frac{N^2 + 2N - 6}{3}$

For $N = 7$ we have:

3100000
5502024

The construction is similar to that of $N = 0 \mod 3$, but now there is a space between the boxes and the holes

if $N = 2 \mod 3$ then we can achieve $\frac{N^2 + 2N - 14}{3}$

For $N = 8$ we have:

31020050
55042020

For $N = 11$ we have:

31020005000
55540202020

The construction following $N = 11$ is similar to those above.

$3 \times 3$

LifereaperX's 3x3

060
370
140

$3 \times 4$

LifereaperX's 3x4

0413
0210
0255

$3 \times 5$

By davidspencer6174 and mathmasterzach

08555
0BH29
04535

$3 \times 6$

By davidspencer6174 and mathmasterzach

008555
01BH29
004535

$3 \times 7$

By sspenst (based on the $3 \times 6$)

0008555
011BH29
0004535

$3 \times N > 8$

By sspenst

14000000
05979760
30600000

This pattern can be extended with additional alternating 7 and 9 columns to for a solution of length N^2 + 3N - 17

$4 \times 4$

LifereaperX's 4x4 (attributed to ybbun)

An alternative by davidspencer6174

$4 \times 5$

mathmasterzach's starting position for part of kjs0722's R2

$4 \times 6$

sspenst's starting position for part of kjs0722's R2

$4 \times 7$

sspenst's modification of mathmasterzach's 4x7-106

$4 \times 8$

hi19hi19's Pipe Wrench

$5 \times 5$

kjs0722's R3

$5 \times 6$

Deleted level, modified by mathmasterzach

$5 \times 7$

Extended version of the $5 \times 6$ found by qqwref

$5 \times 8$

Extended version of the $5 \times 6$ found by qqwref

$6 \times 6$

By qqwref

$6 \times 7$

By qqwref (with slight modification by mathmasterzach)

$6 \times 8$

By qqwref

$7 \times 7$

By qqwref

$7 \times 8$

By qqwref (possibly not fully optimized for step count)

$8 \times 8$

qqwref's Tiny Torment (possibly not fully optimized for step count)

Asymptotics

The best known asymptotic growth for PP1 levels on an $n \times n$ grid is $\Omega(n^4)$. In the top half of the grid, one can create $\Theta(n^2)$ directional locks in alternating directions in the style of the level Forgive Me. In the lower half of the grid, one can make a winding path of length $\Theta(n^2)$ that must be traversed once per directional lock.

The best known asymptotic growth for PP2 levels is exponential. One exponential construction is known: a modified version of Sokoban's exponential Fibo construction showcased by qqwref in Fibo.

Longest Pathology Puzzles By Size

Longest Pathology Puzzles By Size

PP1

$1 \times N$

$2 \times 2$

$2 \times 3$

$2 \times 4$

$2 \times N$

$3 \times N$

$4 \times 4$

$4 \times 5$

$4 \times 6$

$4 \times 7$

$4 \times 8$

$4 \times N$

$5 \times 5$

$5 \times 6$

$5 \times 7$

$5 \times 8$

$6 \times 6$

$6 \times 7$

$6 \times 8$

$7 \times 7$

$7 \times 8$

$8 \times 8$

PP2/Pathology

$2 \times N$

if $N = 0 \mod 3$ then we can achieve $\frac{N^2 + 2N}{3}$ steps

if $N = 1 \mod 3$ then we can achieve $\frac{N^2 + 2N - 6}{3}$

if $N = 2 \mod 3$ then we can achieve $\frac{N^2 + 2N - 14}{3}$

$3 \times 3$

$3 \times 4$

$3 \times 5$

$3 \times 6$

$3 \times 7$

$3 \times N &gt; 8$

$4 \times 4$

$4 \times 5$

$4 \times 6$

$4 \times 7$

$4 \times 8$

$5 \times 5$

$5 \times 6$

$5 \times 7$

$5 \times 8$

$6 \times 6$

$6 \times 7$

$6 \times 8$

$7 \times 7$

$7 \times 8$

$8 \times 8$

Asymptotics

Clone this wiki locally

$3 \times N > 8$