why it doesn't work? thanks!

Code: Select all

**Moderator:** Board moderators

can anybody give a test case where this code fails,or give me a hint

why it doesn't work? thanks!

why it doesn't work? thanks!

Code: Select all

Last edited by broderic on Sat Aug 24, 2002 3:39 pm, edited 1 time in total.

my algorithm:

go from the top-row,

- for each one in top-row, you can switch or not switch

for the rest of the rows,

- the upper row would determine whether you can switch or not. ie. if the upper row is off, you cannot switch; otherwise you must switch.

I like your idea, but there also is an algorithm (10x10)^3 precalc, O(10x10) solution, using Gauss-Jordan reduction mod 2. (XOR)

You can create a system of linear equations mod 2. The matrix would be 100x100. Every line coresponds to an i,j in the configuration. For line 0, (the upper-left corner), there would be three 1s corresponding to the (0,0)position and the two neighbours (0,1), (1,0). Solving the system actually yelds the switches needed to change the state of one light without changing anything else. The solution is also based on the fact that there is only one solution that doesn't repeat switches.

You can create a system of linear equations mod 2. The matrix would be 100x100. Every line coresponds to an i,j in the configuration. For line 0, (the upper-left corner), there would be three 1s corresponding to the (0,0)position and the two neighbours (0,1), (1,0). Solving the system actually yelds the switches needed to change the state of one light without changing anything else. The solution is also based on the fact that there is only one solution that doesn't repeat switches.

Hellowyvmak wrote:i used recursion. though i guess there're better methods than mine. (i heard somebody use looping)

my algorithm:

go from the top-row,

- for each one in top-row, you can switch or not switch

for the rest of the rows,

- the upper row would determine whether you can switch or not. ie. if the upper row is off, you cannot switch; otherwise you must switch.

I can't understand your method.

Could you give me an example?

Think carefully,

once you decided how to press the switched of first row (1024 ways). Then you will also know how to press the buttons in remaining rows.

Let define the top left corner is (1,1), the light below it is (2, 1).........

Once you decided how to press the first row. Then You can only switch the light (1, 1) by the switch (2 ,1). If light(1 ,1) is off after pressing the first row, then you can't touch the switch (2,1). Otherwsie you must press it. Following the logic, you will know how to press the 2nd row, and then 3rd row........10th row

So, what you need is just testing all the 1024 combinations of the first row

once you decided how to press the switched of first row (1024 ways). Then you will also know how to press the buttons in remaining rows.

Let define the top left corner is (1,1), the light below it is (2, 1).........

Once you decided how to press the first row. Then You can only switch the light (1, 1) by the switch (2 ,1). If light(1 ,1) is off after pressing the first row, then you can't touch the switch (2,1). Otherwsie you must press it. Following the logic, you will know how to press the 2nd row, and then 3rd row........10th row

So, what you need is just testing all the 1024 combinations of the first row

My signature:

- Please make discussion about the algorithm BRFORE posting source code.

We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.

I thought that I might point out some funny thing while I was solving 5x5 puzzles, but I think they might be universal to such a problem of any size even though I don't how to prove it right or wrong.

Assuming NxN is a size of a puzzle.

Must check that out.

Assuming NxN is a size of a puzzle.

- First I found out that all solutions are equal to solutions that change only bulbs from the left or right in the first row.
Code: Select all

`SOLUTION_NUMBER=roundup( log2 N )`

- Then I found out that there indeed are only SOLUTION_NUMBER eventual last rows, which correspond to the just-left and just-right solutions above.

Must check that out.