N -ROOM LIGHTS PROBLEM



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.

.



Relevant Pages

  • Re: N -ROOM LIGHTS PROBLEM
    ... all the n X n rooms get lit, ... Up switches in the room and its horizontal/vertical ... If u toggle a light near the wall of the room as shown: ... Does order matter? ...
    (comp.lang.c)
  • N -ROOM LIGHTS PROBLEM
    ... all the n X n rooms get lit, ... Me>I think that dynamic programming techniq can be used to solve this ... Up switches in the room and its horizontal/vertical ... If u toggle a light near the wall of the room as shown: ...
    (comp.theory)
  • N -ROOM LIGHTS PROBLEM
    ... all the n X n rooms get lit, ... Me>I think that dynamic programming techniq can be used to solve this ... Up switches in the room and its horizontal/vertical ... If u toggle a light near the wall of the room as shown: ...
    (comp.lang.c)
  • Re: N -ROOM LIGHTS PROBLEM
    ... all the n X n rooms get lit, ... (toggle means that if the light is on then it is toggled of & if it is ... I think you should have said that this problem belongs to linear algebra and can be solved by gaussian elimination. ... but the case n=1 is easy, n=2 too,(all switches must be toggled). ...
    (comp.theory)
  • Re: Toggling a latch
    ... >> STOP switches, one at each limit. ... you want two limit switches, one toggle, and one stop. ... >state similarly does not change state with TOGGLE on its RESET input. ... I had to use the Stop button to remove motor power. ...
    (sci.electronics.design)