The Lamplighter's Manor: Light All 9 Rooms

[Werg22]

The Lamplighter's manor is 9 room house, which can be represented as 3x3 grid. Each room has a single lamp.

When a lamp is lit, the lamps in each of the adjacent rooms light up if they are unlit, and darken if they are lit. Likewise, when a lamp is extinguished, the lamps in each of the adjacent rooms darken if they are lit, and light up if they are unlit. This does not include the rooms in diagonal, only those directly to the North, South, West and East, where it applies.

We are allowed to light or darken any room, at any given time. Suppose the manor starts with all of its lights off, expect for the one in the very middle, in the second row and second column. What sequence(s) of action gets us to a fully lit manor? Here an action is to be understood as either lighting or darkening a room.

 

[davee123]

Not sure if it's the shortest path, but I got it in 10 steps:

Spoiler

M, NW, SE, NE, SW, M, N, W, S, E

DaveE

 

[Werg22]

Hi davee123,

Spoiler

Correct! There is a shorter path though, reexamine your solution and you may find it.

 

[davee123]

Ahh, yes. I had just done that one by hand, sort of guessing. Just wrote a program to figure out the shortest path-- one of the shortest is:

Spoiler

S, SE, NW, W, E, SW, N, NE

What surprised me was that no matter the starting orientation, no other orientation is more than 9 moves away-- and there's always only ONE that's 9 moves away. In the case of starting with everything off except the middle, the furthest away is having everything off except the 4 corners.

DaveE

 

[Werg22]

In fact,

Spoiler

It's the shortest path.

 

[Werg22]

Although your solution is correct, I don't think you've figured out the trick.

The Lamplighter's mansion is made up of 36 rooms, representable by a 6x6 grid. The same rules apply. The lights in the NW and NE corners are lit, and all others are off. How do you get to a fully lit mansion?

Don't try this by hand!

 

[physics girl phd]

the three-by-three version of this used to be on the Merlin:

http://en.wikipedia.org/wiki/Image:Parker_Brothers_Merlin.jpg

Except it would start with a random configuration of lights. Just random trivia.

 

[davee123]

In fact,

Spoiler

It's the shortest path.

Well, I said one of the shortest since technically, there are 16 variants with rotation and reflection on the path I gave. Admittedly, I didn't know if there were other paths to the solution that weren't variants on what I said, but I knew that there were at least 15 more I could've stated.

Although your solution is correct, I don't think you've figured out the trick.

I guess not? I'm assuming there's effectively an algorithm for doing this that's applicable at any scale. My quickie program can fully map up to a 4x4 set, and a 5x5 takes a long time (an hour maybe?). As is it can't take a 6x6, but I could probably make a lot of efficiencies-- possibly enough to explore the whole 6x6 grid. I'll have to examine some solutions for the 4x4 and 5x5 grids and see what the "trick" might be.

DaveE

 

[Werg22]

Spoiler

There are more than 16 variants to your solution. Far more.

Good luck with your approach.


The trick I'm referring to though has more to do with the analysis at the outset rather than any particular algorithm. It's really neat and easy (not computationally easy though). What I said in spoilers is a hint.

 

[davee123]

Spoiler

There are more than 16 variants to your solution. Far more.

More than 16? I can't seem to find any more than 16 variants of the solution I posted, unless you're talking about solutions that don't involve solely reflection or rotation of the one I posted, which there could very well be tons of. From what I can see, for the solution I posted, there are 4 general rotations, and 2 points along the way where a layout is symmetrical along a given axis and can be reflected. Hence, the variants on my solution would be 4*2*2 = 16:

Spoiler

S, SE, NW, W, E, SW, N, NE
S, SE, NW, W, N, SW, E, NE
S, SW, NE, E, N, SE, W, NW
S, SW, NE, E, W, SE, N, NW
W, SW, NE, N, S, NW, E, SE
W, SW, NE, N, E, NW, S, SE
W, NW, SE, S, E, SW, N, NE
W, NW, SE, S, N, SW, E, NE
N, NW, SE, E, W, NE, S, SW
N, NW, SE, E, S, NE, W, SW
N, NE, SW, W, S, NW, E, SE
N, NE, SW, W, E, NW, S, SE
E, NE, SW, S, N, SE, W, NW
E, NE, SW, S, W, SE, N, NW
E, SE, NW, N, W, NE, S, SW
E, SE, NW, N, S, NE, W, SW

Did I miss a rotation/reflection point?

DaveE

 

[Werg22]

Spoiler

S, NW, NE, E, N, W, SE, SW also works.

 

[davee123]

Spoiler

S, NW, NE, E, N, W, SE, SW also works.

I'm not sure I follow-- how is that a rotation or reflection of the method I presented? It looks like a totally different solution. And, if so, I'm also not sure I understand why you very expressly emphasized the word "the" to imply that the solution was unique?

DaveE

 

[Werg22]

Does it not work though? Try it.

I reemphasize "the". All the solutions are really essentially the same.

 

[Werg22]

Maybe I've made this too difficult. Here's a helpful hint:

Spoiler

Any rearrangement of the moves in your solution works. This why all solutions are essentially the same, they are all permutations of a same set of moves. There are in fact 8! possible solutions if you take order into account. What if you represent a lit lamp with a 1, and an unlit one with a 0? How can you represent the effect of an action with respect to the 0's and 1's, mathematically what is it equivalent to?

 

[Werg22]

No progress?

No other takers?

 

[Caracrist]

Ahh, yes. I had just done that one by hand, sort of guessing. Just wrote a program to figure out the shortest path-- one of the shortest is:

Spoiler

S, SE, NW, W, E, SW, N, NE

What surprised me was that no matter the starting orientation, no other orientation is more than 9 moves away-- and there's always only ONE that's 9 moves away. In the case of starting with everything off except the middle, the furthest away is having everything off except the 4 corners.

DaveE

You have 9 lamps total. There is no reason to use one lamp more than once. The question is, which lamps to use, and which not. So there are some 9 variants in using 8 lamps, 9*8/2 = 36 variants of using 7 lamps, and so on. And of course, there is only one variant of using 9 lamps.
And the answer should be described as:

Spoiler

Using all lamps except the middle one

 

[davee123]

No progress?

Sorry-- I haven't been back since my last post. Yeah, I'm not sure why I didn't think about it in those terms. I think the terminology used probably got me stuck-- you started off asking for a sequence, which isn't necessarily applicable, but I think it immediately triggered me thinking that order was important.

DaveE