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. ... curtain is at or which direction the motor should move. ...
    (sci.electronics.design)