My solution is the same as the one of James Williams, except I do all my calculations in modulo 2 arithmetic, so I don't need complex data types. (I knew James was doing a Gaussian elimination, but I didn't know the details, so I found this simpler method :-) .)
When I do the Gauss elimination, I simply xor two lines, and to the end I get the same result as if I did like James, but it's simpler and faster :-).
Now, I get two free variables too. They can get 0 or 1 as a value, thus leading to four possible solutions. What James didn't tell you is that you can know if there is a solution or not. The two lines with the free variables must be all 0 (especially the last column). If it's not the case, you will get 0 = something (where something = 1 in modulo 2 arithmetic), which tells you there is no possible solution.
Read the source, solve_sed.c. All the details are explained
there.
The problem with this method is that you need to do lots of calculation to check if there is a solution. Chupcko's solution goes one step forward. With some more analysis, you come to a very pretty algorithm to get the solution. This is my prefered, so this is the default solver you will get when running XLightOff. And he found a caracterization to know if a game can be solved or not which requires no move at all, which is nice !
And his file is the shortest one too !
Last edited : Mon Jan 14 21:16:36 CET 2002