7
4
(This code golf task is related to Code-Golf: Lights Off!. The same puzzle is used, but the task is different.)
Introduction
"Lights Out" is a puzzle in which you should switch off all lights in a 5x5 grid. However, when you swap a light from on to off, or from off to on, the four adjacent lights will swap as well!
For example, consider the following grid, in which 1
stands for a light switched on and 0
stands for a light switched off:
00000
00000
00110
01000
00101
Now, if you try to turn the light at row 4, column 2 off, the resulting map will be:
00000
00000
01110
10100
01101
The goal of this game is to turn all lights off. You are allowed to switch certain lights on if that helps you to find the solution, as the adjacent ones will swap as well, which makes it possible to switch others off. This is almost always required to find the solution in fact!
Description
Your task is to find out, given an input grid, which lights should be swapped to switch all lights off. Which ones to swap is enough information to solve the puzzle, because due to the swapping the amount does not matter (you can always do mod 2
so it will be 0
(effectively, don't swap) or 1
(effectively, do swap)), and the order of swapping does not matter either obviously.
Input
Input is a two dimensional array of lengths 5 (5x5
) which represents the grid, in which:
0
stands for a light switched off1
stands for a light switched on
Output
Output is another two dimensional array of lengths 5 (5x5
) which represents which lights to swap to switch all lights off in the grid, in which:
0
stands for 'this light should not be swapped'1
stands for 'this light should be swapped'
Winning condition
Shortest code wins.
Hints
There are several algorithms to find the solution. There are mathematical articles about this game available on the Internet.
Important notice
Sometimes multiple solutions are possible. It depends on the algorithm what solution you'll end up with. If you have different but correct solutions to the examples below, your entry obviously is correct as well.
Examples
Example 1 (video to illustrate):
Input: Output:
00000 00000
00000 00000
00110 00000
01000 00110
00101 00001
Example 2 (video to illustrate):
Input: Output:
11111 11000
11111 11011
11111 00111
11111 01110
11111 01101
isn't that nearly the same anyway? there's no difference between lights out and going from one set to another (xor the from and to boards) – ratchet freak – 2011-08-13T16:49:12.040
@ratcet freak: I'm not sure if I understand you. Solving the puzzle is not as trivial as
xor
ing. – pimvdb – 2011-08-13T17:19:59.827going from the other puzzle to the this one is – ratchet freak – 2011-08-13T19:49:55.447
@ratchet freak: The other question is just about pressing certain lights while this one is about switching all lights off. You might want to try solving one at http://www.ebaumsworld.com/games/play/1111/.
– pimvdb – 2011-08-13T19:53:24.873think about what the diff is (lights remaining the same color/lights needing to switch) – ratchet freak – 2011-08-13T19:59:28.580