443,694 Members | 1,882 Online
Need help? Post your question and get tips & solutions from a community of 443,694 IT Pros & Developers. It's quick & easy.

# N -ROOM LIGHTS PROBLEM

 P: n/a 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 if center room gets clicked ) 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. Apr 1 '06 #1