Friday, March 25, 2011

A puzzle with switches

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too

Give an algorithm which, given a starting configuration, will tell you whether the lock can be unlocked by a sequence of switch toggles

No comments:

Post a Comment