[poulson]

Thanks for the link! There is even a nice discussion of the explicit solutions for Inverter up to 7x7's on the page: http://mathworld.wolfram.com/LightsOutPuzzle.html

Almost nothing about the solver would need to change in order to support computation over GF(p), which suggests that someone should create a version of Lights Out / Inverter which cycles through a prime number of colors rather than just off/on.

[chaoxu]

I think it would work for all finite fields. One of the solutions to this IOI problem was solved that way, and it's not of the form GF(p) but it's GF(p^2). http://olympiads.win.tue.nl/ioi/ioi94/contest/day2prb1/probl... see solution 2: http://olympiads.win.tue.nl/ioi/ioi94/contest/day2prb1/solut...

[poulson]

Good point. So it would seem to be hard to find solutions for 6, 10, 12, etc. colors. Have you given any thought to how to solve those cases?

[chaoxu]

Wikipedia has an article on this, http://en.wikipedia.org/wiki/Linear_equation_over_a_ring it would take a long time to read up the background to understand it, and I don't have the background to distill it to the exact result we want.

Note the wiki article references this book: Ideals, Varieties, and Algorithms by Cox, Little and O'Shea. This is a standard and approachable reference on this kind of topics.

Although this topic is interesting, I think it's best to treating it as a technology. Knowing it's existence and know when to apply them is good enough. Understanding how it works would be a big time sink and sadly doesn't give much useful insights.