Gauss is a good start, of course, but what you have to remember is to apply it to the context of this puzzle. We have huge matrices of 0's and 1's, but only a tiny fraction of it is actually a '1', which is what you are interested in. Most of the time you spend iterating through the matrix does not advance you towards a solution. So ask yourself, how can you make it such that you only read/write your matrix when it is actually serves a purpose?

This puzzle has a ton of small optimization you can make, I started with about 15 minutes for a level around 220 and it took me 15 minutes for lvl 643. Benchmarking the different steps your solver takes is quite important to know what takes time. I still have a few optimizations that could speed the thing up by about 4x but my solver already finished the game before I could implement them