> not the most elegant solution but far better than brute force

Actually, brute force works just fine for such a small matrix:

https://gist.github.com/aexaey/3657fa39cc35c861f6d6