Dear Ed,

that's my first time to write to you... Keep up the good
work, I like your page and column very much!

Some weeks ago, I looked at the Doppleganger maze under
"Material added 29 Sep 04". I wrote a simple program in
Tcl/Tk, by which you can try out solutions or just play
around. maze.tcl is quite rudimentary, though. I attach it here.
On Unix systems "./maze.tcl" should do it, on Windows you
probably have to state "wish maze.tcl". In any case you need
Tcl/Tk (tested with version 8.4).

I also did an encoding of this maze for the disjunctive
datalog engine DLV (http://www.dlvsystem.com ), which I was
co-developing. There, you specify the knowledge about a
problem using a logic-based formalism, and then compute
solutions for it. This is declarative, i.e. you do not write
how to compute the solutions (you do not specify an
algorithm).

I have two files:

dpmaze.dl has the layout of the maze, using two binary
relations/predicates hedge and vedge (the names contain edge
because I usually view these as planar graphs, where fields
are vertices and adjacent ones are connected by an edge) for
defining the grid, two other binary relations hwall and
vwall for defining the location of horizontal and vertical
walls. And two unary relations start and finish, indicating
the fields S and F. Note that this is basically a relational
database.

maze.dl contains a description of what a solution would be.
It uses bounded non-negative integers for the number of
moves. This is then set on the command line upon invocation
(-N=n asking for solutions with n moves). I won't describe
this encoding in detail here. If you are interested, I will
be happy to give you explanations, though. Anyhow, using
this, you can determine for any odd n<20 in less than one
second that no solution exists. For even numbers < 20 it
took longer.

For n=20, computing the first solution took about 5.5
minutes on my Powerbook:
cage:~/experiments/doppelgangermaze/dlv> \time DLV dpmaze.dl
maze.dl -N=20 -pfilter=up,left,right,down -n=1 DLV [build
BEN/Sep 28 2004 gcc 3.3.4 (Debian 1:3.3.4-11)]

{right(0), right(1), right(2), down(3), down(4), up(5),
left(6), left(7), left(8), up(9), right(10), right(11),
right(12), right(13), left(14), down(15), down(16),
down(17), up(18), right(19)} 318.08user 1.21system
5:29.55elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+431minor)pagefaults 0swaps
cage:~/experiments/doppelgangermaze/dlv>

One can also compute all of the solutions of length 20
(there are 46). Determining these and the fact that no other
solutions exist, took around 17 minutes on the same machine.

One can also use these encodings to check solutions by
storing them as facts right(0). right(1). left(2). etc. and
setting the integer bound accordingly. I attach a zip file
of the solutions
encoded in this way.

I could not get Ronnie Henarie's solution to work (it seems
that these are Doppleganger moves without me always being
physically able to do the reciprocal move, as Claudio
Baiocchi writes), and I also could not get Michael Dufour's
solution to work (move 24 seems to be impossible). In
Christopher Duane Brown's solution, there are four
consecutive downs, these should obviously be only three
(works then). Bryce Herdt and Chris Lusby Taylor (and of
course Claudio Baiocchi) have found one of the minimal
solutions.

I will probably put all this material on my own website in a
while.

I think this type of maze would make a nice computer game
(rules are simple and intuitive, and you can "experiment").
Would Brian Smith (and you) authorize this?

best regards Wolfgang -- <http://www.wfaber.com >

---------------------------------------------------------------------------------

Hi Ed.

Concerning the DP's problem, I noticed that the answers you have collected are
somewhat incomplete. Let me try to present a more complete analysis.

We use compass-letters (n, e, s and w) to denote the direction of our moves. We
call half-move the move we choose; and full-move the couple "our move plus the
DP's move". One easely checks that the 19 full-moves corresponding to
"seeeewwsnwneeewsssn" bring DP on the F square, and us on the square left of it;
thus, if we want to end with a DP's move, we can conclude with three further
full-moves, say "nes"; but we can also conclude with the single half-move "e".

An easy computer program shows that we can not do better; more generally,
starting from S, some squares are out of reach, while some other can be reached
only after "some full-moves and half"; the complete description is given in the
enclosed picture "NoCoop.gif". Remark in particular that the choice of F as
final square does not correspnd to the longest path: among the reachable
squares, to reach the North-East corner we need 22 and half moves
("seeeewwsnwneeewseswnn" and half of "e").

A simpler task comes out with a slight modification of the rules, used in
particular in the solution proposed by Ronnie Henarie. In fact the DP could
"cooperate" by choosing a direction whose opposite is forbidden for us; in other
words, we could force DP to move according to our "will" instead of our
movement. E.g. our first move could be choosen as follows:

"I want to choose the direction North; I can not move in that direction, thus I
will remain here, but you can (and you must) go South"

Using capital letters for our will, the square F can now be reached through the
16 full-moves "NWWNNWseeeeNsswn"; or better by 13 and half moves:
"seeesWWWsnWsn" plus half of "e". Starting from S, the complete description is
given in the enclosed picture "Cooperating.gif".

Regards, Claudio Baiocchi

--------------------------------------------------------
Right, Right, Right, Down, Right, Left, Up, Left, Left, Left, Down, Right, Up,
Right, Right, Right, Left, Left, Down, Down, Down, Up, Up, Right, Right, Down.
Iani Penev
---------------------------------------------------------------

The solution is (I Think) :
1 L
2 L
3 L
4 U
5 L
6 U
7 U
8 D
9 R
10 R
11 R
12 R
13 U
14 D
15 D
16 L
17 U - At F
Ronnie Henarie
---------------------------------------------------
Hi Ed,
First time I tried, I transcribed the maze wrongly - put F in the
bottom right corner. Turns out that's impossible. With the correct F
square, a solution is (Up/Down/Left/Right):
RRRDDULLLURRRRLDDDUR.

Best wishes

Chris Lusby Taylor
----------------------------------------------------
Number of moves
29 (to finish on your move) or 31 (to finish on his move.)

From the starting point, you move

Right, Right, Right, Right, Left, Left Down, Down, Down, Down, Up Left, Left,
Down, Up Right, Right, Up, Up Left, Down, Right, Right, Right Left, Down, Down,
Up

There are two possibilities here...one to end up on F after one of your moves,
one to end up on F after one of his. To finish on your move: Right (Finish)

To finish on his move:
Up
Right
Down
Christopher Duane Brown
----------------------------------------------------
Hello!

I'm guessing plenty of people have sent you an answer by now, but, oh well, here
goes.

You move as follows: 4r,4l,1d,1r,1u,1l,1d,1r,1u,2r,1d,1l,2d,1r,1u,1r,1l, and
finally 1r gets you both there. I don't know if there's a shorter solution?

Anyway, Great website, keep it up,

Cheers,

Dafydd Parsons
---------------------------------------------------------
This is my first time to this site and I saw the current puzzle. I don't know if
there is a format for answering, but here is mine for the puzzle in the subject

My answer is of the form, (square I occupy/square DP occupies). If have divided
the grid into columns(left to right) marked A - E, and rows(top to bottom)
marked 1 - 4. So, the start square is A1 and the finish square is E3.

Here is my answer to how we both get to the finish(32 moves): A1/A1, B1/A1,
C1/A1, D1/A1, D2/A1, E2/A1, D2/B1, D3/B1, D4/B1, C4/C1, B4/D1, B3/D2, A3/E2,
A4/E2, A3/E3, B3/D3, C3/D3, C2/D4, C1/D4, C2/D3, B2/E3, B1/E4, C1/E4, D1/E4,
D2/E3, D3/E2, D4/E2, C4/E2, C3/E3, C2/E4, D2/E4, E2/E4, E3/E3.

If there is a format for the puzzle answers, just let me know and all
my future

Thanks,
Eric
-----------------------------------------------------------
If you record only your movements using U(p), D(own), L(eft), R(ight) and put a
number before the direction for multiples moves then I think that you moving
4R3LDULDU4RL3D2URD ends up with you both at the F.

Steve Kay
-------------------------------------------------------------
Here we go:
L=left
R=right
U=up
D=down
0=nomove/static

Move,Smove,Dresponse
1,R,0
2,R,0
3,R,0
4,R,0
5,L,R
6,L,R
7,D,0
8,D,0
9,D,0
10,U,D
11,U,D
12,U,D
13,L,R
14,D,U
15,L,R
16,U,D
17,R,0
18,R,0
19,R,0
20,D,U
21,R,L
22,D,0
23,U,D
24,U,D
25,R,0
26,D,U
Should be at F

Michael Dufour
------------------------------------------------------
Doppelganger maze:
RRRR (DP stays put)
L (DP moves R)
D (DP stays)
U (DP moves D)
LLL (DP moves RRR)
D (DP stays)
U (DP moves D)
RRR (DP moves L then stops)
L (DP moves R)
DDD (DP moves U then stops)
UU (DP moves DD)
RR (DP stays)
D (DP moves U and the goal is met)
------------------------------------------------------
Hi, Ed.
Here's my solution to the Doppelganger Maze, with rows lettered and columns
numbered.
First, move to C5 with DP staying put. (6 spaces)
Then go to A2 with DP going to C4. (5 spaces)
Next, move to A5 with DP not moving. (3 spaces)
Then go to D4 with DP getting stuck at B5. (4 spaces)
Finally, go to F, where you will meet DP on your move. (2 spaces)
Total: 20 spaces. I'd like to know whether there's a shorter answer.

Bryce Herdt
-----------------------------------------------------------
The solution I got is: Down Right Right Right Right Left Left Up Left Left Down
Right Right Up Right Down Down Down Left Up Left Down Left Up Right Right Up
Right Right Down
Ric Wilburn
---------------------------------------------------------
Here is my solution. ( My moves)

If correct, I solved it in 30 seconds in my head, but it took a little longer to
write the e-mail. Interesting puzzle!!

down 1
all the way right
down 1
left 1
down 1
left 1
all the way up
left 1
down 1
all the way right
down 1
left 1
down 1
up 1
right 1

ANTHONY CHMIEL
------------------------------------------------------------------

Right, Right, Right, Down, Right, Left, Up, Left, Left, Left, Down, Right, Up, Right, Right, Right, Left, Left, Down, Down, Down, Up, Up, Right, Right, Down.
Iani Penev

The solution is (I Think) :
1          L
2          L
3          L
4          U
5          L
6          U
7          U
8          D
9          R
10         R
11         R
12         R
13         U
14         D
15         D
16         L
17         U  -  At F
Ronnie Henarie
----------------------------------------------------
Hi Ed,
First time I tried, I transcribed the maze wrongly - put F in the
bottom right corner. Turns out that's impossible. With the correct F
square, a solution is (Up/Down/Left/Right):
RRRDDULLLURRRRLDDDUR.

Best wishes

Chris Lusby Taylor
-----------------------------------------------------
Number of moves
29 (to finish on your move) or 31 (to finish on his move.)

From the starting point, you move

Right, Right, Right, Right, Left, Left Down, Down, Down, Down, Up Left, Left, Down, Up Right, Right, Up, Up Left, Down, Right, Right, Right Left, Down, Down, Up

There are two possibilities here...one to end up on F after one of your moves, one to end up on F after one of his. To finish on your move: Right (Finish)

To finish on his move:
Up
Right
Down
Christopher Duane Brown
-----------------------------------------------------
Hello!

I'm guessing plenty of people have sent you an answer by now, but, oh well, here goes.

You move as follows: 4r,4l,1d,1r,1u,1l,1d,1r,1u,2r,1d,1l,2d,1r,1u,1r,1l, and finally 1r gets you both there. I don't know if there's a shorter solution?

Anyway, Great website, keep it up,

Cheers,

Dafydd Parsons
----------------------------------------------------------
This is my first time to this site and I saw the current puzzle.  I don't know if there is a format for answering, but here is mine for the puzzle in the subject heading.

My answer is of the form, (square I occupy/square DP occupies).  If have divided the grid into columns(left to right) marked A - E, and rows(top to bottom) marked 1 - 4.  So, the start square is A1 and the finish square is E3.

Here is my answer to how we both get to the finish(32 moves):  A1/A1, B1/A1, C1/A1, D1/A1, D2/A1, E2/A1, D2/B1, D3/B1, D4/B1, C4/C1, B4/D1, B3/D2, A3/E2, A4/E2, A3/E3, B3/D3, C3/D3, C2/D4, C1/D4, C2/D3, B2/E3, B1/E4, C1/E4, D1/E4, D2/E3, D3/E2, D4/E2, C4/E2, C3/E3, C2/E4, D2/E4, E2/E4, E3/E3.

If there is a format for the puzzle answers, just let me know and all
my future

Thanks,
Eric
------------------------------------------------------------
If you record only your movements using U(p), D(own), L(eft), R(ight) and put a number before the direction for multiples moves then I think that you moving 4R3LDULDU4RL3D2URD ends up with you both at the F.

Steve Kay
--------------------------------------------------------------
Here we go:
L=left
R=right
U=up
D=down
0=nomove/static

Move,Smove,Dresponse
1,R,0
2,R,0
3,R,0
4,R,0
5,L,R
6,L,R
7,D,0
8,D,0
9,D,0
10,U,D
11,U,D
12,U,D
13,L,R
14,D,U
15,L,R
16,U,D
17,R,0
18,R,0
19,R,0
20,D,U
21,R,L
22,D,0
23,U,D
24,U,D
25,R,0
26,D,U
Should be at F

Michael Dufour
-------------------------------------------------------
Doppelganger maze:
RRRR (DP stays put)
L (DP moves R)
D (DP stays)
U (DP moves D)
LLL (DP moves RRR)
D (DP stays)
U (DP moves D)
RRR (DP moves L then stops)
L (DP moves R)
DDD (DP moves U then stops)
UU (DP moves DD)
RR (DP stays)
D (DP moves U and the goal is met)
-------------------------------------------------------
Hi, Ed.
Here's my solution to the Doppelganger Maze, with rows lettered and columns numbered.
First, move to C5 with DP staying put. (6 spaces)
Then go to A2 with DP going to C4. (5 spaces)
Next, move to A5 with DP not moving. (3 spaces)
Then go to D4 with DP getting stuck at B5. (4 spaces)
Finally, go to F, where you will meet DP on your move. (2 spaces)
Total: 20 spaces. I'd like to know whether there's a shorter answer.

Bryce Herdt
------------------------------------------------------------
The solution I got is: Down Right Right Right Right Left Left Up Left Left Down Right Right Up Right Down Down Down Left Up Left Down Left Up Right Right Up Right Right Down
Ric Wilburn
----------------------------------------------------------
Here is my solution. ( My moves)

If correct, I solved it in 30 seconds in my head, but it took a little longer to write the e-mail.
Interesting puzzle!!

down 1
all the way right
down 1
left 1
down 1
left 1
all the way up
left 1
down 1
all the way right
down 1
left 1
down 1
up 1
right 1

ANTHONY CHMIEL
-------------------------------------------------------------------
Doppelganger maze:
RRRR (DP stays put)
L (DP moves R)
D (DP stays)
U (DP moves D)
LLL (DP moves RRR)
D (DP stays)
U (DP moves D)
RRR (DP moves L then stops)
L (DP moves R)
DDD (DP moves U then stops)
UU (DP moves DD)
RR (DP stays)
D (DP moves U and the goal is met)
Joseph Devincentis