[EMAIL PROTECTED] wrote: > 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 > IN ME NEXT EMAIL
You had said that if a room is toggled, its neighbors are toggled. That can be interpreted as an unending sequence (the neighbors are rooms and are toggled, therefor their neighbors should get toggled). However this is not what you meant (as shown by your program). When a room is manually toggled, the neighboring rooms get automatically toggled, but the process stops there. You can see that the "order" of toggles does not matter. Manual Toggle (click) room 1,1, followed by manual toggle 2,2, gives the same results if you reverse the order. Manual toggle a room an even number of times, and it is as-if you never clicked the room. I wanted to distinguish between a manual toggle (click on a room in your application), and an automatic toggle (a room's light changes its state because of a click in that room or a neighbor). By my definition, the switch in a room is in the Up state if you have clicked on the room an odd number of times, otherwise the switch in the room is in the Down state. The light in a room can "see" the switches from that room and its horiz/vert neighbors. The light will be On iff it sees an odd number of switches in the Up state. AFAICT this description is consistent with the way your application behaves, except that you can't see the switches. This puts an upper limit on the size of your problem. If you find a solution, there will be some rooms toggled an odd number of times, and perhaps some rooms toggled an even number. So the switch in a room can be in one of two states, and there are N^2 rooms, so there are 2^(N^2) possible answers. However, we can speed things up a bit. For examples I'll use the N=3 problem, but the techniques work for larger values of N. Suppose we start with all rooms dark, and then pick some arbitrary switch positions for the first column. There are 2^N possible arbitrary choices. I'll make an arbitrary choice: UDD UDD DDD and the light states are (*=on, .=off) .*. .*. *.. We've now made our choices for the first column, and we aren't going to change our mind (for now). A valid solution must light the entire first column. For the given choice (UUD) in the first column, there is only one choice of the second column that will leave the first column lit. That choice for the second column is (UUD) giving UUD *** UUD *** DDD **. so we used the second column to "repair" the first column. We can continue, (using the 3rd column to "repair" the second column and so on (for larger grids), until all but the last column have been repaired In this case the second column needs no "repair." My initial guess was no good. It left us with a "residual" of "**." in the last column (we wanted ***). It took me N^2 time to find this residual. I could try all 2^N possible arbitrary choices for the first column and then work out the residual of each, and my total cost has been reduced to (2^N)*(N^2), a big improvement, but we can still do better. You can create a system of linear equations looking at how the residual changes when you change a single switch of my arbitrary guess. You can create the system of equations in O(N^3) time, and then solve it (or fail if there is no solution) to change the residual to all-lights-on. For the 3x3 grid, the system is non-singular. For the 4x4 and 5x5 grids, the systems are singular, and have multiple solutions. Solving the systems takes O(N^3) time. For N<=5, N^3 is not much of an improvement on (2^N)*(N^2). However as N grows, the 2^N is a killer. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
