I'm doing some challenges to learn new and interesting concepts, this one is about a Lights out variant, instead of toggling only the adjacent tiles, it toggles the whole row and col.

It must be solved in pure python, so no numpy or other libraries that might help are allowed here.

I adapted the algorithm of this excellent ressource. Using a n2*n2 toggle matrix and a flattened puzzle P we can use a linear algebra to calculate T*x = P mod 2, where x is the matrix of buttons we need to push to solve the puzzle.

Since 1 < n < 16, this algorithm may need to solve matrices up to 225x225, which takes ~420ms on my machine. The exact time constraints aren't given, but I get a timeout error after submitting.

I pasted a running example here, this generates a random 15x15 puzzle and prints out a few timings and the solution to that particular puzzle.

The method performGaussianElimination(toggle, puzzle) takes by far the longest and seems to be the only bottleneck, but I don't see a place where I could use memoization or other shortcuts to save time. I've looked for other pure python linear algebra solvers, but there are only a few (numpy is so much easier) and don't seem to be a lot different.

def performGaussianElimination(toggle, puzzle):
    nextFreeRow = 0
    n = len(puzzle)
    for col in xrange(n):
        pivotRow = findPivot(toggle, nextFreeRow, col)
        if pivotRow is None:

        swap(toggle, nextFreeRow, pivotRow)
        swap(puzzle, nextFreeRow, pivotRow)

        for row in xrange(pivotRow + 1, n):
            if toggle[row][col]:
                for i in xrange(len(toggle[row])):
                    toggle[row][i] ^= toggle[nextFreeRow][i]
                puzzle[row] ^= puzzle[nextFreeRow]

        nextFreeRow += 1

    return toggle, puzzle

Can I speed this up? Might this traditionally fast algorithm not be the fastest for this variant?

  • \$\begingroup\$ FIY: I just tried using bool instead of int, but it is (not unexpectedly) just as slow/fast as before. \$\endgroup\$
    – Sven
    Dec 7, 2014 at 15:39
  • \$\begingroup\$ but it's a 4'th of the memory used. \$\endgroup\$
    – sebix
    Dec 7, 2014 at 19:04

1 Answer 1


You have a matrix of bits. You could represent each row by a single integer. (Remember that in Python the size of int is unlimited, so working with 255 bits is not a problem.) Then you would be able to avoid the inner loop here

for row in xrange(pivotRow + 1, n):
    if toggle[row][col]:
        for i in xrange(len(toggle[row])):
            toggle[row][i] ^= toggle[nextFreeRow][i]

and do this instead

col_mask = 1 << col
for row in xrange(pivotRow + 1, n):
    if toggle[row] & col_mask:
        toggle[row] ^= toggle[nextFreeRow]
  • \$\begingroup\$ Memory is not the issue, speed is. Bitarray is a third-party library and int seem to be pretty optimized already. I'm not sure if that would my performance. \$\endgroup\$
    – Sven
    Dec 7, 2014 at 19:33
  • 1
    \$\begingroup\$ @Sven You don't need a third-party library to manipulate bits, see edited answer. \$\endgroup\$ Dec 8, 2014 at 6:35
  • \$\begingroup\$ Good answer. I said the same thing on Reddit, here. \$\endgroup\$
    – Veedrac
    Dec 8, 2014 at 13:53
  • \$\begingroup\$ @KevinKim I suppose your comment was intended to the question, not my answer. \$\endgroup\$ Jun 27, 2016 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.