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

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

answers will follow that format.

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

answers will follow that format.

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