N ROOM LIGHTS PROBLEM
 From: "ALIABBAS J PETIWALA" <aliabbasjp@xxxxxxxxx>
 Date: 31 Mar 2006 22:17:34 0800
N ROOM LIGHTS PROBLEM
========================
THERE IS A BIG SQURE ROOM OF SIDE N WHICH CONSISTS OF N X N SMALLER
SQUARE ROOMS(ARRANGED LIKE CHESS BOARD)
EACH ROOM HAS A LIGHT.
WHEN the light of a smaller room k is toggled then all the
neighboring room's lights get toggled (max 5 lights get toggled
including the kth room )
THE PROBLEM IS to formulate an algorithm which will generate an order
in which the lights have to be toggled such that
all the n X n rooms get lit, initially no room is lit.
(toggle means that if the light is on then it is toggled of & if it is
off then it is switched on)
(question asked by Microsoft at IIT)
me>CAN a divide and conquer strategy work?
Me>I think that dynamic programming techniq can be used to solve this
problem?
Dear wade u got it wrong as u said " A light is On iff the number of
Up switches in the room and its horizontal/vertical (not diagonal)
neighbors is odd."
If u toggle a light near the wall of the room as shown:
if its possible I am attaching a sample program.
.
 FollowUps:
 Re: N ROOM LIGHTS PROBLEM
 From: Thad Smith
 Re: N ROOM LIGHTS PROBLEM
 From: Harris
 Re: N ROOM LIGHTS PROBLEM
 From: Googmeister
 Re: N ROOM LIGHTS PROBLEM
 From: Gerry Quinn
 Re: N ROOM LIGHTS PROBLEM
 Prev by Date: Re: Card dealing and random repetition
 Next by Date: Re: Cannot understand the following codes
 Previous by thread: Re: Card dealing and random repetition
 Next by thread: Re: N ROOM LIGHTS PROBLEM
 Index(es):
Relevant Pages
