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	59	65	?
7						67	78	?
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 created by hand by davidspencer6174

$4 \times 6$

Created by hand 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 (by hand)

$5 \times 6$

Created by hand by davidspencer6174

$5 \times 7$

Created by hand by davidspencer6174

$5 \times 8$

Created by hand by davidspencer6174

$6 \times 6$

Created by hand by Hem

$6 \times 7$

Created by hand by Hem

$6 \times 8$

Created by hand by Hem

$7 \times 7$

Created by hand by Hem

$7 \times 8$

Created by hand by Hem

$8 \times 8$

Hem's Boundary Unstable (by hand)

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	49	67	91	$\geq N^2 + 3N - 17$
4			32	70	152	210	?	?
5				132	206	?	?	?
6					300	?	?	?
7						?	386	?
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 by hand: 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 (by hand)

060
370
140

$3 \times 4$

LifereaperX's 3x4 (by hand)

0413
0210
0255

$3 \times 5$

Created by hand by davidspencer6174 and mathmasterzach

08555
0BH29
04535

$3 \times 6$

Found by davidspencer6174 via computer search

000085
0CBA01
004153

$3 \times 7$

Found by davidspencer6174 via computer search

5604153
0272D01
0080005

$3 \times 8$

davidspencer6174's Insular Gigantism (via computer search)

00C00005
022F0A0C
004G1053

$4 \times 4$

RisingStar111's 4x4 (by hand)

$4 \times 5$

davidspencer6174's Beyond Measure (via computer search)

52020
0F4E3
CG625
585B5

$4 \times 6$

davidspencer6174's Break Infinity (via computer search)

$4 \times 7$

mathmasterzach's Cassette Rewind (via computer search)

$5 \times 5$

davidspencer6174's Leap Year (via computer search)

$5 \times 6$

mathmasterzach's Car Battery (via computer search)

$6 \times 6$

kjs0722's R8

$7 \times 8$

By qqwref

$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 8$

$4 \times 4$

$4 \times 5$

$4 \times 6$

$4 \times 7$

$5 \times 5$

$5 \times 6$

$6 \times 6$

$7 \times 8$

$8 \times 8$

Asymptotics

Clone this wiki locally