2

I have MATRIX(m*n) fill with bool (0 or 1)

When we position x,y near position and center will reverse (x,y),(x+1,y),(x-1,y),(x,y+1),(x,y-1)

And we have to press some position to make it transform to some matrix that we want to

11111                   1-111                   1-1-1                  1-1-1
11111   press(2,2)->    ---11    press(2,4)->   --1--   press(3,2)->   -11--
11111                   1-111                   1-1-1                  -1--1
11111                   11111                   11111                  1-111

This problem can use permutation but it's too slow O(2^(n*m)) we can make some condition to make it faster but it still slow for me.

Can you tell me what is this problem name and is it have algorithm better than permutation?

halfer
  • 19,824
  • 17
  • 99
  • 186
krist7599555
  • 25
  • 5

2 Answers2

1

This is called the Lights Out Puzzle.

In addition to the permutation algorithm you can also solve the problem using Gaussian elimination, as explained in the answer to this question and the Wolfram Alpha link above. The basic idea is to set up a matrix representing all the possible presses and a column vector representing the "lights" (the boolean values) and solve to get the set of presses to set all the booleans to false (lights out). You can adapt this to solve for an arbitrary state just by flipping the booleans in the column vector for the lights that you want to remain on.

Community
  • 1
  • 1
samgak
  • 23,944
  • 4
  • 60
  • 82
0

That's a simple form of finding nearest neighbours, and all you need is finding the neighbours indices.

For item A in coordinate (x,y) in matrix L(m*n) the neighbures indices should be calculate like following: 

(min(m, x+1),y)
(max(0, x-1),y)
(x,min(n, y+1))
(x,max(0, y-1))
Mazdak
  • 105,000
  • 18
  • 159
  • 188