I am trying to implement a solver for the game lights out. You have a grid of lights, when you click on one of them the light you clicked and its four neighbours change colour, with the light starting over when it runs out of colours. The aim is to get all the lights to a particular colour.
Because the way the colours change is cyclic, I thought I could implement it as a system of equations and do all calculations mod n (n being the number of available colours).
This method worked for some puzzles but I got stuck in others.
I am representing the game as a system of equations in an augmented matrix and reducing it to reduced row echelon form using gaussian elimination. As I said in some cases this worked well. However there are some cases (example to follow) where I end up with a line which I cannot reduce completely, reason being that, since I'm using modular arithmetic, some values don't have a multiplicative inverse so I get stuck.
Here is an example: The game shown here represents a 4x4 grid with 4 colours available. Here is the matrix as it started out:
1100100000000000 3 1110010000000000 3 0111001000000000 2 0011000100000000 3 1000110010000000 3 0100111001000000 3 0010011100100000 0 0001001100010000 0 0000100011001000 0 0000010011100100 0 0000001001110010 2 0000000100110001 1 0000000010001100 3 0000000001001110 1 0000000000100111 0 0000000000010011 0
and this is as far as I've managed to reduce it:
1000000000000333 2 0100000000003323 3 0010000000003233 0 0001000000003330 0 0000100000001232 2 0000010000002003 2 0000001000003002 3 0000000100002321 3 0000000010001320 1 0000000001003332 1 0000000000102333 0 0000000000010231 2 0000000000000220 2 0000000000002222 0 0000000000002222 0 0000000000000220 2
In this case the last line, for example, is
...220 2 and I cannot figure out how I can reduce it since I cannot simply divide by 2 (2 has no multiplicative inverse in z4). Whatever I tried, I always ended up with a leading 2 in a row. I am absolutely certain a solution exists for the game (I did solve it correctly myself) but I'm not sure if I'm doing missing something here, or just that the method simply does not work for all cases.
Edit: Fixed the matrices in the example. There were inconsistencies at the end. I've figured out that any inconsistencies there mean there is no solution. In the updated example a solution does exist for sure, and this results in no inconsistencies at the end. However I still cannot solve it