Locked room mazes

Notes on possible new logic puzzles

Locked room mazes

Postby dyitto » Fri Sep 03, 2010 10:41 pm

We have a building that consists of 6 by 6 rooms, separated by walls or doors.

Image

A number in the middle of a room is supposed to be a key. You can collect keys as you walk through the rooms.
A number between two rooms is supposed to be a door: you'll need a key of the same number in order to pass that door.

Of course, this will force you to find your path through different rooms before you reach the target room.

In this maze:
Find the shortest path from R1C1 to R6C6.
Also, find the shortest path from R6C6 to R6C1.
Last edited by dyitto on Sun Aug 12, 2012 9:14 am, edited 2 times in total.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Locked room mazes

Postby dyitto » Sat Sep 04, 2010 8:03 pm

Maybe more callenging; find a path from R5C5 to R1C1 and preferably the shortest one:

Image
Last edited by dyitto on Sun Aug 12, 2012 9:15 am, edited 1 time in total.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Locked room mazes

Postby 999_Springs » Tue Sep 07, 2010 1:46 pm

Top one: 25-15-25-30-1-14-18-21-35-10-8-4
and 4-21-4-8-10-8-15-1-18-14-30-20-29-9-15-25.

Bottom one: 75-54-74-60-74-68-33-68-74-54-75-42-26-42-75-80-49-80-75-54-22-63-r1c1.

There seem to be a lot of random keys in odd places that don't do anything.

Locked room mazes.png
Recreated in a 2-D flash game about a ninja.
Locked room mazes.png (64.01 KiB) Viewed 1042 times
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Locked room mazes

Postby dyitto » Thu Sep 09, 2010 9:00 pm

999_Springs wrote:There seem to be a lot of random keys in odd places that don't do anything.


Yep. The computer made some random choices here.

But anyway I rearranged some key/doornumbers.
Now I have essentially the same LRM but without some superfluous keys.

Image

I also made a bigger one:

Image

In this one you're asked to find the path from R5C5 to R7C3.

Your ninja view is great! :) :)

Now for some programming stuff:

My program computes the shortest path between two rooms.
Mind that the distances are not symmetrical: the path from A to B may be different from the path from B to A or one of them doesn't even exist.
Anyway it takes 2 minutes to find the answer to the 9x9 LRM and task manager says he has used about 86K memory :!: .

For generating the LRMs I've used some variant of the Kruskal algorithm.
For 9x9 it takes lots of time and up to 250K :shock: memory for some reason.
For 11x11 and beyond I get an out of memory message.

So I did something wrong - or maybe not; I'll see if I can improve this in future. :?
Last edited by dyitto on Sun Aug 12, 2012 9:16 am, edited 1 time in total.
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Locked room mazes

Postby dyitto » Fri Sep 10, 2010 11:36 pm

dyitto wrote:For generating the LRMs I've used some variant of the Kruskal algorithm.
For 9x9 it takes lots of time and up to 250K :shock: memory for some reason.
For 11x11 and beyond I get an out of memory message.

Solved this one.

So in the following 12x12 LRM:
Find a path from R10C3 to R1C7.

Image

Textformat of this LRM:
Code: Select all
    ;w   ;    ;w   ;    ;w   ;k013;w   ;    ;w015;    ;w   ;    ;w   ;    ;w002;    ;w015;    ;w   ;    ;w007;    ;
w001;    ;    ;    ;    ;    ;w001;    ;    ;    ;w002;    ;w005;    ;w   ;    ;w014;    ;w   ;    ;w004;    ;w   ;
    ;    ;k001;    ;k016;w   ;k014;w001;    ;w   ;k018;w010;    ;w   ;    ;w002;    ;w006;k004;w015;    ;w   ;    ;
w001;    ;w   ;    ;    ;    ;    ;    ;w001;    ;    ;    ;w   ;    ;w013;    ;w015;    ;w   ;    ;w   ;    ;    ;
    ;w   ;    ;w013;    ;    ;k002;w   ;    ;w001;k007;w   ;    ;w   ;k005;w014;k015;w014;    ;    ;k014;    ;    ;
w007;    ;w   ;    ;w018;    ;w002;    ;w   ;    ;    ;    ;w001;    ;w002;    ;    ;    ;w   ;    ;    ;    ;w   ;
k017;w   ;    ;w018;    ;w   ;    ;w018;    ;w018;k002;    ;    ;w   ;    ;w   ;    ;w   ;    ;w014;k006;w016;    ;
    ;    ;w   ;    ;    ;    ;w001;    ;w   ;    ;    ;    ;w   ;    ;    ;    ;w   ;    ;    ;    ;    ;    ;w   ;
    ;w009;    ;w   ;    ;w   ;    ;w   ;    ;w007;    ;    ;    ;    ;    ;w006;    ;w014;    ;w   ;    ;w002;    ;
w007;    ;w   ;    ;w   ;    ;w   ;    ;    ;    ;w015;    ;    ;    ;w018;    ;w   ;    ;w   ;    ;    ;    ;w021;
    ;w   ;    ;w   ;    ;w   ;    ;    ;    ;w   ;    ;w   ;    ;w017;k006;w   ;    ;w   ;    ;w007;    ;w   ;    ;
w   ;    ;    ;    ;    ;    ;    ;    ;w   ;    ;    ;    ;    ;    ;w021;    ;w012;    ;w   ;    ;w   ;    ;w   ;
    ;    ;    ;w010;    ;    ;    ;w018;    ;w001;k012;w021;    ;    ;    ;    ;    ;w001;    ;    ;    ;w   ;    ;
w012;    ;w   ;    ;w   ;    ;w020;    ;    ;    ;w005;    ;w   ;    ;    ;    ;w016;    ;w   ;    ;w   ;    ;    ;
    ;w   ;    ;w019;    ;w   ;k011;    ;    ;w019;    ;w019;    ;w   ;    ;w010;    ;w   ;    ;w   ;    ;    ;    ;
    ;    ;w005;    ;w   ;    ;    ;    ;w019;    ;w   ;    ;    ;    ;    ;    ;w021;    ;w014;    ;w001;    ;w   ;
    ;w   ;k020;w020;    ;w019;    ;w019;    ;    ;    ;w   ;    ;w017;k021;w   ;k009;    ;    ;w   ;    ;w016;    ;
    ;    ;w019;    ;w   ;    ;w   ;    ;w   ;    ;    ;    ;w017;    ;    ;    ;w   ;    ;w   ;    ;w010;    ;w   ;
    ;    ;    ;    ;    ;w008;k015;w   ;    ;w   ;    ;w   ;k003;    ;    ;w010;    ;w   ;    ;    ;    ;w017;    ;
    ;    ;    ;    ;    ;    ;w   ;    ;w013;    ;w   ;    ;    ;    ;w   ;    ;w017;    ;    ;    ;w   ;    ;    ;
k019;w   ;    ;w   ;    ;w   ;k008;w   ;    ;w011;    ;w   ;    ;w002;    ;    ;    ;w017;k010;    ;k017;w   ;    ;
w   ;    ;    ;    ;w   ;    ;w005;    ;    ;    ;w   ;    ;    ;    ;w   ;    ;w003;    ;    ;    ;w010;    ;    ;
    ;w020;    ;w019;k005;    ;k013;w020;    ;    ;    ;w   ;    ;w005;    ;w   ;    ;w   ;    ;w   ;    ;w   ;    ;
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam


Return to Inventors' studio