wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Neighboring Lights
        
(Message started by: Aravis on Aug 3^rd, 2006, 9:03am)

Title: Neighboring Lights
Post by Aravis on Aug 3^rd, 2006, 9:03am

There is a not to uncommon game with the following rules:

Start with an NxN board.

At the beginning, each square contains a 'light' in the off position. You can 'turn on' any light in any square, but whenever you 'turn on' a light, you also 'turn on' its neighbors -- diagonals are not neighbors. If you 'turn off' a light, you also 'turn off' it neighbors.

The goal is to turn all of the lights on.

Examples:

for a two by two board,

start with

00
00

to solve, hit each light in turn clockwise from top left

11 00 01 11
10 11 00 11

Therefore you hit all of the lights to turn them all on.

The solution to the two by two case is
11
11

showing 1's for the lights you flip.

A solution for the 3x3 case is
101
010
101

and for the 4x4

0100
0001
1000
0010

Verify these yourself if you want.

First part of problem: find a solution for the 5x5 case.

Second (and harder) part: find a general method for finding a solution to an NxN case.

Some notes:
there may be multiple solutions for each case, we just want to find one of them.

For the general part: My solution to this works, but it is incredibly inefficient. Hopefully somebody can find a better way.

Title: Re: Neighboring Lights
Post by SMQ on Aug 3^rd, 2006, 10:00am

See this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1115012125) for a previous discussion, including an algorithm and source code for a general solver capable of handling boards several thousand lights on a side (not to toot my own horn, or anything ;)).

[edit]To be fair, the algorithm was described first by eigenray and in more detail by Grimbal; I primarily supplied the speedy implementation.[/edit]

--SMQ

Title: Re: Neighboring Lights
Post by Aravis on Aug 3^rd, 2006, 10:58am

Thanks.

Title: Re: Neighboring Lights
Post by rmsgrey on Aug 4^th, 2006, 8:21am

Ummmm, the rules described and the examples given don't match up.

The rules given say: "whenever you 'turn on' a light, you also 'turn on' its neighbors" (and similarly for turning off)

The example flips each neighbour regardless of whether the target light is being turned on or turned off, and regardless of whether the neighbouring light started on or off...

I would phrase it as: Whenever you turn a light on or off, you also light any unlit neighbouring lights, and extinguish any lit neighbours

Title: Re: Neighboring Lights
Post by Aravis on Aug 4^th, 2006, 9:27am

Thank you for the correction. That is an important distinction that would otherwise make the problem much easier.