# 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.

.

**Follow-Ups**:**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

- 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):