Locks and 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 N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles

Note 1: Can be done in O(N^2) time and O(1) space.
Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)

Update (Dec 20, 2010):
Complete solution posted jointly by Siddhant Agarwal (EE, Final year student, IITB) and Gaurav Sinha (IITK 1996 CSE Alumnus, IRS Officer). Thanks a lot

Comments

  1. Switch on =1
    off=0
    Toggling operation is commutative i.e toggling wrt entry (m1,n1) and then toggling wrt entry (m2,n2) is equivalent to toggling wrt entry (m2,n2) and then toggling wrt (m1,n1). Also, toggling wrt same element twice gives the original matrix back again.Associativity also holds. Hence, a simple algo would be to take the configuration and toggle wrt every element and see if you get the matrix with all entries as 1.

    However, this requires space O(n2).

    ReplyDelete
  2. If we toggle wrt each entry, wouldn't it require O(n3) time.(O(n) for toggling each entry of respective row and column and another O(n2) for checking whether we have arrived at our final matrix(with all entries 1)).

    ReplyDelete
  3. for N even, we dont need to do anything. There always exists a sequence of switch toggles which will unlock the lock.

    Proof: U hav a N by N grid (or matrix). If a switch is on put 1, off put 0. So now u have a N by N matrix with entries 0 and 1.

    number the switches 1 to N^2 serially. (i.e the top left gets number 1, top right gets number N,.. bottom right gets number N^2). As said in the above post, toggling operation is commutative. Also toggling twice is same as not toggling. So toggling is same as doing algebra in the finite field GF2. (i.e 1+1=0;1.1=1 etc ). So let x(1),x(2),..,x(N^2) be the variables denoting whether the respective switch is toggled or not. x(1)=1 if switch 1 is toggled.. otherwise it is 0.

    Now toggling switch 1, inverts switches 1,2,..,N,N+1,2N+1,..,N(N-1)+1. So construct a (N^2)*(N^2) matrix with the first row having ones at the above positions and 0 elsewhere. Do this for every switch. Let this matrix be called A. Now the vector x=(x(1),x(2),..,x(N^2)) denotes which switches have been toggled. So the vector Ax denotes, finally which switches have been inverted. Now if A was invertible then we can reach any possible state.. which is the same thing as saying that there always exists a soln.

    Now its not difficult to see that A*A=I (note that we are working in GF2). Hence A is invertible and hence proved

    For N odd, the matrix A is not invertible and hence something different needs to be done

    ReplyDelete
  4. worked out a solution. hope its correct.
    there are two cases:
    case 1 : n is even. in this case all the configurations can be unlocked.Proof is by showing that all configurations are reachable by sequence of toggles.

    case 2: n is odd. In this case it requires just one step. toggle all the switches that are currently off, and also the switches in the corresponding rows and columns.In the resulting grid,if it is possible to unlock, all switches would be on and the grid will be unlocked in just one step. Proof is by induction.

    Analysis:

    translate to an equivalent problem in terms of binary matrices:

    consider the space of nxn binary matrices. each such matrix can be thought of as a configuration for lock where 0 and 1 will mean on and off respectively.The addition of matrices is defined as addition of corresponding elements via xor, i.e. 1+1=0,1+0=1,0+0=0,0+1=1.the idea is that addition by 1 means toggle of the switch corresponding to matrix element.

    suppose Rij is a binary matrix consisting of 1 in every entry of ith row or jth cloumn [thus there will be a total of 2n-1 1's]. the matrix Rij corresponds to an operation when we toggle the (i,j) switch and other switches in row i and column j. set of all such matrices Rij generates a vector space V over field F of binary numbers. In the field F, addition operation is same as XOR i.e. 1+1=0,1+0=1,0+0=0,0+1=1.Multiplication is as usual i.e. 1x0=0x1=0x0=0; and 1x1=1.

    Given an arbitrary binary matrix A, The question is whether there exists a set of matrices Rij such that their sum is A.

    If n is even then it can be shown that the matrices Rij are linearly independent.There are n^2 such matrices. So, the vector space formed by linear combination of these matrices has 2^(n^2) elements, and hence will contain all possible nxn binary matrices.

    If n is odd, and A= sum of k matrices of form Rij, then it can be shown by induction on k, that the algorithm will work.

    ReplyDelete
  5. Awesome! hats off to u man

    ReplyDelete
  6. @Gautam, gg: Toggle with respect to each entry will take O(2^(n^2)) time

    @sid. chera: respect! Thanks a ton! :) I could not have thought of this in a million years!

    ReplyDelete
  7. let me know if this works.
    On = 1, Off = 0
    Operation RXOR:
    For each row, do an XOR. Keep a count of the # rows with XOR = 0.
    Operation CXOR:
    For each column, do an XOR. Keep a count of the # cols with XOR = 0.
    Memory = 2 counters. Time O(n^2).
    If both counters are identical, Yes
    else No

    ReplyDelete
  8. shantanu,

    your method will work.with one slight addition i.e.the counters should be both 0 or both n. in other words operation RXOR and CXOR should yield same value for all rows and columns.

    pl. correct me if i m wrong.

    ReplyDelete
  9. I've a solution for general N * M matrix :

    Case 1 : Both N & M even : all configurations are solvable.

    Case 2 : Exactly one of N & M is odd. Say N is odd. Then grid is solvable iff all rows have same parity

    Case 3 : Both N & M are odd. Grid is solvable iff all rows and columns have same parity.

    ReplyDelete
  10. @shantanu..
    I think your solution gives a necessary condition but not a sufficient condition.
    Pls comment!

    ReplyDelete

Post a Comment