Author |
Topic: Neighboring Lights (Read 1318 times) |
|
Aravis
Junior Member
Posts: 56
|
 |
Neighboring Lights
« on: Aug 3rd, 2006, 9:03am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
Duct tape is like the force. It has a light side, a dark side, and it holds the universe together. -Carl Zwanzig
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: Neighboring Lights
« Reply #1 on: Aug 3rd, 2006, 10:00am » |
Quote Modify
|
See this thread 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
|
| « Last Edit: Aug 3rd, 2006, 10:27am by SMQ » |
IP Logged |
--SMQ
|
|
|
Aravis
Junior Member
Posts: 56
|
|
Re: Neighboring Lights
« Reply #2 on: Aug 3rd, 2006, 10:58am » |
Quote Modify
|
Thanks.
|
|
IP Logged |
Duct tape is like the force. It has a light side, a dark side, and it holds the universe together. -Carl Zwanzig
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Neighboring Lights
« Reply #3 on: Aug 4th, 2006, 8:21am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Aravis
Junior Member
Posts: 56
|
|
Re: Neighboring Lights
« Reply #4 on: Aug 4th, 2006, 9:27am » |
Quote Modify
|
Thank you for the correction. That is an important distinction that would otherwise make the problem much easier.
|
|
IP Logged |
Duct tape is like the force. It has a light side, a dark side, and it holds the universe together. -Carl Zwanzig
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print