# Lights Out - Find the solution

(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 off
• `1` 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 Aug 13 '11 at 16:49 @ratcet freak: I'm not sure if I understand you. Solving the puzzle is not as trivial as `xor`ing. – pimvdb Aug 13 '11 at 17:19 going from the other puzzle to the this one is – ratchet freak Aug 13 '11 at 19:49 @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 ebaumsworld.com/games/play/1111. – pimvdb Aug 13 '11 at 19:53 think about what the diff is (lights remaining the same color/lights needing to switch) – ratchet freak Aug 13 '11 at 19:59

## Ruby (130)(121)(113) (102)

EDIT: Saved 9 characters, thanks to Howard.

EDIT 2: Another 8 characters, courtesy of Howard.

EDIT 3: Saved 11 more characters after learning how to use Ruby's % operator for sprintf.

``````b=(0..4).map{gets.to_i 2}
32.times{|x|z=0;k=b.map{|i|x=z^i^31&(x<<1^x>>1)^z=x;'%05b'%z}
puts k if x<1}
``````

Accepts 5 lines of input from stdin. Outputs all solutions as 5x5 grids as specified, though there are no extra line breaks between solutions (or between the input and the solutions).

Solutions are found by iterating through all 32 possibilities for the top row, since the top row determines the switches that must be flipped in the following rows.

Input:

``````00000
00000
00110
01000
00101
``````

Output:

``````00000
00000
00000
00110
00001
01110
10101
11011
10011
01111
10101
10101
00000
10011
10100
11011
00000
11011
00110
11010
``````
-
 You don't need brackets around `0..4` - 2 characters. Also the `0b`-prefix is not neccessary - 7 characters. – Howard Aug 14 '11 at 14:03 Nice. It's also fast and does not hang if there is no solution. – pimvdb Aug 14 '11 at 14:16 @Howard Thanks for the tips! I'm still learning my way around Ruby :) – migimaru Aug 14 '11 at 14:17 Some others: `x==0` is equivalent to `x<1` in your case - 1 character. You don't have to take the `i`-loop and can use `b.map{}` directly - 3 characters. But this means you can get rid of `r` completely - 2 characters. Also formatting of output can be done a bit more efficiently: `(z+32).to_s(2)[1,5]` - 2 characters. – Howard Aug 14 '11 at 15:35 @Howard Thanks again! I'm definitely learning to appreciate the trickiness of golfing in Ruby :) – migimaru Aug 14 '11 at 16:14

### Ruby, 133 characters

``````t=->z,v,s{v<0?z&33814345664<1&&s :t[z,v-1,s+?0]||t[z^4321<<(v+v/5),v-1,s+?1]}
``````

This is a brute-force search through all possible on/off combinations. The input must be specified on stdin with exactly five lines of five 0/1 characters each and a newline after each one, e.g.:

``````> ruby lights.rb
11111
11111
11011
11111
11111
^Z
00000
11111
10001
11111
00000
``````
-

## F#

brute-force, will golf later

``````open System;
let a = Array2D.create 5 5 false
let b = Array2D.create 5 5 false

for i = 0 to 4 do
for j = 0 to 4 do
a.[i, j] <- if Console.Read() = 49 then true else false

let r = Random()
while Seq.cast a |> Seq.exists id do
let x, y = r.Next(5), r.Next(5)
b.[x, y] <- not b.[x, y]
for u, v in [ x, y;
x - 1, y;
x + 1, y;
x, y - 1;
x, y + 1 ] do
try
a.[u, v] <- not a.[u, v]
with
| _ -> ()

printfn "%s" (let mutable z = ""
for i = 0 to 4 do
for j = 0 to 4 do
z <- z + (if b.[i, j] then "1" else "0")
z <- z + "\n"
z)
``````
-