1

I have some doubts about a question that was asked before (Lights out game algorithm). I cannot ask there because it's saying you need to have 50 points to add comments that's why I am adding it as a new question.

Can any one give me the example of the algorithm that was explained here?
I don't want backtracking I want Gaussian elimination method to solve lights out.

For example I have 2*2 matrix and it's initial state is as below.

 1  0  
 0  1

How to solve above lights out grid using Gaussian elimination?

Can any one explain what this line is doing in the above given link ?

std::swap_ranges(toggle.row_begin(pivotRow), toggle.row_end(pivotRow),
                       toggle.row_begin(nextFreeRow));

std::swap(puzzle[pivotRow], puzzle[nextFreeRow]);

I also don't understand the below line 

puzzle[row] ^= puzzle[nextFreeRow];

And how to run this code. Is the Function: SolveLightsOut(const Matrix& puzzle);is the main function ?

Community
  • 1
  • 1
eswaat
  • 733
  • 1
  • 13
  • 31
  • [This other question](http://stackoverflow.com/questions/14169450/converting-a-binary-matrix-to-0s-by-toggling-rows-and-columns/14169591#14169591) might help explain how the Gaussian elimination approach works. By the way - I wrote the code that you linked, and I'd be happy to clarify anything about how it works. – templatetypedef Jan 28 '14 at 18:50
  • @templatetypedef I have understand your algorithm, but I am still not able to solve the matrix. Can you please tell me how to solve above example through equation like I have make it simple it's just a 2*2 matrix it will not take your time lot. – eswaat Jan 28 '14 at 19:17
  • 1
    @user3167839: You first need to come clear about how your equation system would look like. For each grid point you have 1 variable and 1 equation, so you end up with a 4x4 linear system over GF(2). Did you follow up to this point? If no, what is it that you are having trouble with? – Niklas B. Jan 28 '14 at 20:03
  • @NiklasB. variable is button that I have press or toggled one right ? So what I have understand is for the above matrix the equation will look like b_11 * T_11 + b_12 * T_12 + b_21 * T_21 + b_22 * T_22 = A. Where T_ is toggle and we have to find b vector right ? – eswaat Jan 28 '14 at 20:17
  • 1
    I don't think that is really getting you anywhere. Think about it like this: Suppose `T_ij` is a variable that says whether button `(i,j)` is toggled (0 or 1). What would be the resulting state of the light (1,1)? And what *should* it be? – Niklas B. Jan 28 '14 at 20:21
  • @NiklasB. for light(1,1) it will be T_11+T_12+T_21. Is it correct ? – eswaat Jan 28 '14 at 20:24
  • 1
    Yes, so the equation would look like `T_11 + T_12 + T_21 + 1 = 0` or equivalently, in standard form: `T_11 + T_12 + T_21 = 1` because `-1 = 1 (mod 2)` – Niklas B. Jan 28 '14 at 20:28
  • @NiklasB. but where the b as mention in the Tb = A and we need to solve b right ? So how to get b ? – eswaat Jan 28 '14 at 20:34
  • 1
    @user3167839: I don't know what you mean by `Tb = A`. The general form of a linear system is `Ax = b`, where `A` is a matrix, `b` is a vector and `x` is the vector that you want to "solve for". I just used `T` because that is what you used as variables that represent the toggle state of buttons, but really in the general form, the toggle vector would be `x`, which is what we are solving for. So your equation system would look like `(1) x_11 + x_12 + x_21 = 1 (2) ...` etc. – Niklas B. Jan 28 '14 at 20:40
  • Now you just write the coefficients on the left side into a matrix `A` and the right sides into a vector `b` and use Gauss to solve it. You can read more about solving linear equation systems on [Wikipedia](http://en.wikipedia.org/wiki/System_of_linear_equations) – Niklas B. Jan 28 '14 at 20:40
  • @NiklasB. Thanks now it's getting little cleared. So can you tell what is 1 in x_11 + x_12 + x_21 = 1 . As you said "you have 1 variable and 1 equation, so you end up with a 4x4 linear system over GF(2)" but we have only equation for (1,1) (1,2) (2,1) (2,2) so how it will be 4x4 ? – eswaat Jan 28 '14 at 20:45
  • Well it's actually `1 * x_11 + 1 * x_12 + 1 * x_21 + 0 * x_22 = 1` You use 1 as a coefficient if the button influences the light in the current cell and multiply by 0 otherwise because the variable does *not* influence the state of the current cell. The right side basically says what you *want* the total number of togglings of the cell to be (modulo 2). You want it to be 1 so that the light is toggled. If the light were off initially, you'd want it to be 0 – Niklas B. Jan 28 '14 at 20:48
  • By 4x4 I mean 4 equations over 4 variables. 4x4 are the also the dimensions of the resulting coefficient matrix `A` – Niklas B. Jan 28 '14 at 20:49
  • @NiklasB. Sorry I am still not getting I am dumb. how to select 1 or 0 for the right side position in equation" 1 * x_11 + 1 * x_12 + 1 * x_21 + 0 * x_22 = 1". So for example in Ax=b if my b=[1 0 0 1] then the following equation are correct ? (1,1) :-> 1*x_11 + 1*x_12 + 1*x_21 + 0*x_22 = 1(b[1]) (1,2) :-> 1*x_11 + 1*x_12 + 0*x_21 + 1*x_22 = 0(b[2]) (2,1) :-> 1*x_11 + 0*x_12 + 1*x_21 + 1*x_22 = 0(b[3]) (2,2) :-> 0*x_11 + 1*x_12 + 1*x_21 + 1*x_22 = 1(b[4]) – eswaat Jan 28 '14 at 22:42
  • @user3167839: Yep, that's correct. – Niklas B. Jan 28 '14 at 22:53
  • @NiklasB. Awesome. I must say you have great patience to answer. I really appreciate your inputs. Thanks – eswaat Jan 28 '14 at 22:55
  • I am flagging this as a duplicate now – Niklas B. Jan 28 '14 at 22:56
  • possible duplicate of [Lights out game algorithm](http://stackoverflow.com/questions/19795973/lights-out-game-algorithm) – Niklas B. Jan 28 '14 at 22:56
  • @templatetypedef I have added some question for understanding the code you have return. Can you please have a look and tell me what they are doing ? – eswaat Feb 03 '14 at 01:38

0 Answers0