JP Ikäheimonen has created the Cooperation Maze. Despite the small size, it's surprisingly difficult.

The rules are as follows:
1. You've got two pointers, two pens maybe.
2. Both pens start at cell marked 'start', in this maze top left (number 3).
3. Goal is to have both pens arrive simultaneously to cell marked 'goal'
4. A pen can move horizontally or vertically, as many squares as the current number shows.
5. Both pens move at the same time, but one of the pens must move horizontally and the other vertically. Which pen moves which way is up to you.
6. Just to make things clear: after the first move, your pens should be on squares marked with '2' and '3', where one pen moved three squares to the right and the other moved three squares down. For the next move you will have twochoices. One possible move is to move the upper pen two squares downwards while the other pen moves three squares right, and the other choice is to move the upper pen two squares left while the other moves back up again. And so on.
7. This particular maze has no number under 'goal', so getting just one pointer in 'goal' is considered to be an illegal position,where you cannot continue further. A dead end, in maze terms.

JP's Cooperation maze proved to be the most amazingly difficult tiny maze I've ever seen. Many wrote to me to say it was impossible. It was solved by only by Koshi Arai, Yuval Gabay, Matt Elder, Carl Ginnow, Mike Fee, Erwin Eichner, Juha Saukkola, and Igor Krivokon.

A B C D
E F G H
I J K L
M N H P

AA,DM,LP,IL,AI, DA,BM,JP,BO,JN, LF,IN,AP,MO,AN, MP,AO,MN,PF,ON, NF,FH,NG,FF,HN, GF,CH,OG,NC,PO, LN,IF,AH,MG,AF, DN,BF,JH,BG,JF, BH,JG,LC,IO,KK

Claudio Baiocchi
I liked a lot the Cooperation Maze, as well as the construction of a Computer-program to solve it.
I would be interested to know if the autor inspected the possibility of using a slight modification of the third rule.
A pen can move horizontally or vertically, as many squares as the current number shows.
I would prefer the variant:
A pen can move horizontally or vertically, as many squares as the number UNDER THE OTHER PEN shows.
The reason for the change is twofold:
- it renders more difficult a "backward search";
- it allows a more general structure of the table, which could be choosen randomly. In fact the original rule imply
that no path can pass through an internal case containing the number 3...
Independently from the change of the rules, one could allow different choices for the starting square. Of course, in
order to avoid no-hope searches, in each non-goal square one should write the number of moves required to reach
the goal; see the enclosed picture "fig2.gif", where for the squares without a red number the problem is unsolvable.

Yuval Gabay
it was fun trying to solve this. As usual with puzzles of this kind, the backwards method proves a lot more efficient, as the tree of possible moves is lot less branching in that direction. In this case, the backward solution was quite straightforward.
Even so, it was simply confusing at times, and I had to recheck my steps every now and then to make sure I didn't miss something, or to find a move I must have missed.

Here's my 44-move solution.
Columns are labeled A-D, left to right, and rows are labeled 1-4, top to bottom:

A1 A1, A4 D1, D4 D3, D3 A3, A3 A1,
A1 D1, A4 B1, D4 B3, C4 B1. B4 B3,
B2 D3, B4 A3, D4 A1, C4 A4, B4 A1,
D4 A4, C4 A1, B4 A4, B2 D4, B4 C4,
B2 B4, D2 B2, C2 B4, B2 B2, D2 B4,
C2 B2, C1 D2, C4 C2, B4 C1, D4 C4,
D3 B4, A3 B2, A1 D2, A4 C2, A1 B2,
D1 B4, B1 B2, B3 D2, B1 C2, B3 B2,
B1 D2, B3 C2, D3 C1, A3 C4, C3 C3.

I have a rather firm belief that there is no shorter solution. Can you confirm or refute?

Erwin Eichner

it took several hours on several days, but I think I've got a short solution
(the shortest solution?) with 44 steps from start to goal.
As you said, small but surprisingly difficult.
Congratulations to JP Ikäheimonen, I think creating a nice game is much
more difficult than solving it.

Carl Ginnow

The "Cooperation Maze" _was_ surprisingly difficult for its size. My
solution required 44 moves.

Igor Krivokon

First of all, thank you for your wonderful mathpuzzle.com site!

Second, I've found the solution for the Cooperation Maze, but I used
computer and it may be considered cheating :)
Anyway, I spent first 30 minutes trying to find an elegant way to solve it,
no success, then in the next 30 minutes I wrote the simle Perl program to
help me :) It is not fully automated - I hardcoded the preprocessed input,
not a raw matrix 4x4. I decided that it will be faster for me (and for the
program) to translate it into the table that contains all the possible
moves. I'm not sure if it is of any interest for you, but anyway the program
is just one page long so I attached it here.
Again, thanks for the great puzzles!

my %maze = (
11 => [ [14], [41] ],
12 => [ [14], [32] ],
13 => [ [], [43] ],
14 => [ [12], [34] ],
21 => [ [22], [31] ],
22 => [ [24], [42] ],
23 => [ [22, 24], [13, 33] ],
24 => [ [23], [14, 34] ],
31 => [ [33], [11] ],
32 => [ [34], [12] ],
34 => [ [31], [] ],
41 => [ [44], [11] ],
42 => [ [44], [22] ],
43 => [ [42, 44], [33] ],
44 => [ [43], [34] ]
);

sub positions {
my @res;
my @an1 = map { \$maze{\$_[0]}->[\$_] } (0, 1);
my @an2 = map { \$maze{\$_[1]}->[\$_] } (1, 0);

for my \$i (0,1) {
for my \$n1 (@{\$an1[\$i]}) {
for my \$n2 (@{\$an2[\$i]}) {
push @res, [\$n1, \$n2];
}
}
}

return @res;
}

my @start = ( 11, 11, "Start: (11 11)\n" );
push @arr, \@start;

while(++\$n) {
# print "Step \$n\t arr size = ", scalar(@arr), "\n";
my \$try = shift @arr or last;

foreach my \$np (positions @\$try) {
my (\$np1, \$np2) = @\$np;
if (\$np1 == 33 and \$np2 == 33) {
print "\$try->[2]End: (33 33)\n\n";
}
next if (\$np1 == 33 or \$np2 == 33);

my (\$x1, \$x2) = (\$np1 > \$np2) ? (\$np1, \$np2) : (\$np2, \$np1);
my \$y = \$x1*100 + \$x2;
next if \$hash{\$y};
\$hash{\$y} = 1;

my \$path = "\$try->[2](\$np1 \$np2)\n";
my @newtry = (\$np1, \$np2, \$path);
push @arr, \@newtry;
}
}

print "Done\n";