A long time ago, I solved a 5 by 5 version of this with a genetic algorithm. Wasn’t the most efficient way.

As you say, Gaussian elimination can be used for a more systematic approach.