Escape Level : "Double Lights Out" by bpotetz

« back Browsing Levels: #1081 "Double Lights Out"


prev: #1080 "Lights Out (on a Torus)"	next: #1082 "Don't Go Plastic"

"Double Lights Out" by bpotetz

added 10 Mar 2006 17:13

Solved 6/6

Cooked 0/6

Difficulty 6.83

Style 7.50

Rigidity 4.50

Shortest Solution
Name Optimal

Length 322 moves

By noname

On 26 Jul 2018 11:25

Comments (turn spoilers off)

20282 Double Lights Out noname (559) Thu 26 Jul 2018 11:25 SPOILER

Added speedrun: 322 moves (old: 324).
Optimal

14005 Double Lights Out radiant (1469) Sun 28 Mar 2010 22:29 SPOILER

Added speedrun: 324 moves (old: 326).

5599 Double Lights Out Tom 7 (1) Wed 15 Mar 2006 10:11 SPOILER

I'm impressed that you guys are daring enough to compose such long messages in the comment box, which has no cut/paste and can easily lose your comment for good!

5598 Double Lights Out bpotetz (144) Wed 15 Mar 2006 04:24 SPOILER

Thanks for posting your perl script, bje. I'm happy that you were interested enough in the level to write a brute force solver. To encourage more analysis & thinking, I will post some basic deductions about the game that I used in selecting the start-state & other parameters.

ANOTHER EXTREME SPOILER:

First, John is right - pressing a button & its 4 nearest neighbors will toggle the central button. That is enough to completely solve the simpler level (1080). Similar theorems exist for all lights-out puzzles played on a regular closed surface (torus, klein bottle, of any size). On the other hand, if the game has hard boundaries, you can solve it easily using a technique that I recently discovered already has a name: "light chasing" (google for more info). Maybe if the game was played on a less regular graph, harder techniques would be needed.

Anyway, this means that you can determine the set of buttons that must be pressed by just summing up all the red panels & their 4 nearest neighbors in mod 2 arithmetic. For this level, that set should contain 9 buttons (I won't list them here - that is *too* spoiling). Unfortunately, because the transports also toggle on & off, there is no way to press those buttons & only those buttons, which we can prove.

Note that pressing a button toggles the same set of red/green lights as it does the transports. I considered using a different pattern for the transports, but I did not like how most other simple patterns lie on a checkerboard - that makes it too easy to construct parity arguments to solve the puzzle.

Anyway, using the same pattern for lights & transports means that at any given time, the state of the lights & the state of the transports only differs by a constant set. In this case, that is just 4 squares: the three that are already out (green) in the start state, plus the one that has a transport in the start state. Since the game is finished when all the lights are green, the end game must have all but those 4 transports "open". Note that in your final move, you must walk into an open transporter, which will turn that transporter off. So the final move must be made at one of those 4 squares that has no transporter in the final state. Only one of those 4 squares is in the set of buttons that MUST get pressed. And that is the one that MUST be pressed in your first move (it is like a joke at your expense). So at least one of those 4 differing squares must be pressed twice.

Knowing all this makes solving the puzzle by hand much easier.

5596 Double Lights Out bje (262) Wed 15 Mar 2006 01:06 SPOILER

EXTREME SPOILER!

For those interested, the perl script I used to do all the thinking for me can be downloaded from:

http://users.bigpond.net.au/dhask/lightsout.pl.txt
I numbered the teleporters from left to right, top to bottom, 1 to 16. The final output is the state (0 = all green), a bitmask for which teleporters are visible, and then a list of teleporters to walk through in order.

It's not a fastest solution finder, though the final output is in the set of "fewest teleports" solutions.

5533 Double Lights Out John Lewis (411) Sat 11 Mar 2006 18:10 SPOILER

Finally solved this. Even though it's tough to do it on this level, it's helpful to remember that to turn a single red light to green, "push" it and all other reds around it.

5510 Double Lights Out bpotetz (144) Fri 10 Mar 2006 17:13

'Double Lights Out' uploaded by bpotetz:
This version is supposed to be harder, but it's still not too difficult.

Comments (turn spoilers off)

20282	Double Lights Out	noname (559)	Thu 26 Jul 2018 11:25	SPOILER
	Added speedrun: 322 moves (old: 324). Optimal

14005	Double Lights Out	radiant (1469)	Sun 28 Mar 2010 22:29	SPOILER
	Added speedrun: 324 moves (old: 326).

5599	Double Lights Out	Tom 7 (1)	Wed 15 Mar 2006 10:11	SPOILER
	I'm impressed that you guys are daring enough to compose such long messages in the comment box, which has no cut/paste and can easily lose your comment for good!

5598	Double Lights Out	bpotetz (144)	Wed 15 Mar 2006 04:24	SPOILER
	Thanks for posting your perl script, bje. I'm happy that you were interested enough in the level to write a brute force solver. To encourage more analysis & thinking, I will post some basic deductions about the game that I used in selecting the start-state & other parameters. ANOTHER EXTREME SPOILER: First, John is right - pressing a button & its 4 nearest neighbors will toggle the central button. That is enough to completely solve the simpler level (1080). Similar theorems exist for all lights-out puzzles played on a regular closed surface (torus, klein bottle, of any size). On the other hand, if the game has hard boundaries, you can solve it easily using a technique that I recently discovered already has a name: "light chasing" (google for more info). Maybe if the game was played on a less regular graph, harder techniques would be needed. Anyway, this means that you can determine the set of buttons that must be pressed by just summing up all the red panels & their 4 nearest neighbors in mod 2 arithmetic. For this level, that set should contain 9 buttons (I won't list them here - that is too spoiling). Unfortunately, because the transports also toggle on & off, there is no way to press those buttons & only those buttons, which we can prove. Note that pressing a button toggles the same set of red/green lights as it does the transports. I considered using a different pattern for the transports, but I did not like how most other simple patterns lie on a checkerboard - that makes it too easy to construct parity arguments to solve the puzzle. Anyway, using the same pattern for lights & transports means that at any given time, the state of the lights & the state of the transports only differs by a constant set. In this case, that is just 4 squares: the three that are already out (green) in the start state, plus the one that has a transport in the start state. Since the game is finished when all the lights are green, the end game must have all but those 4 transports "open". Note that in your final move, you must walk into an open transporter, which will turn that transporter off. So the final move must be made at one of those 4 squares that has no transporter in the final state. Only one of those 4 squares is in the set of buttons that MUST get pressed. And that is the one that MUST be pressed in your first move (it is like a joke at your expense). So at least one of those 4 differing squares must be pressed twice. Knowing all this makes solving the puzzle by hand much easier.

5596	Double Lights Out	bje (262)	Wed 15 Mar 2006 01:06	SPOILER
	EXTREME SPOILER! For those interested, the perl script I used to do all the thinking for me can be downloaded from: http://users.bigpond.net.au/dhask/lightsout.pl.txt I numbered the teleporters from left to right, top to bottom, 1 to 16. The final output is the state (0 = all green), a bitmask for which teleporters are visible, and then a list of teleporters to walk through in order. It's not a fastest solution finder, though the final output is in the set of "fewest teleports" solutions.

5533	Double Lights Out	John Lewis (411)	Sat 11 Mar 2006 18:10	SPOILER
	Finally solved this. Even though it's tough to do it on this level, it's helpful to remember that to turn a single red light to green, "push" it and all other reds around it.

5510	Double Lights Out	bpotetz (144)	Fri 10 Mar 2006 17:13
	'Double Lights Out' uploaded by bpotetz: This version is supposed to be harder, but it's still not too difficult.