4

I have a 4x4 matrix. Say

0 1 1 0
0 0 1 0
0 1 1 0
0 1 1 1

My task is to transform the matrix to either

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

or

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Single operation is defined as pick any element of the matrix and then replace the element and elements to its left, right, up and down with their xor with 1.

Example

0 1 1 0
0 0 1 0 
0 1 1 0
0 1 1 1

operation on marked element will transform the matrix to

0 1 0 0
0 1 0 1 
0 1 0 0
0 1 1 1

My objective is to calculate the minimum number of operations needed to get the final result.

I don't even understand under what category this problem lies? Is this branch and bound, bactracking or something else.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
cryptomanic
  • 5,986
  • 3
  • 18
  • 30
  • I beleive this can be solved by backtracking; let `Switch(i,j)` be th operation described performed on the `i`-th row and `j`-th column; the recursion ends when all elements are either `1` or `0`. For a given configuration, the minimum number of operations needed is the minimum over `1` plus the the minimum number of operations after performing `Switch(i,j)` for all `i` and `j`. However, some cycle detection has to be implemented - a branch has to be tracked back if the configuration has occured before. – Codor Jun 01 '16 at 07:09
  • Possible duplicate of [this](http://stackoverflow.com/questions/1310590/how-to-do-matrix-conversions-by-row-and-columns-toggles) question. – Codor Jun 01 '16 at 07:21

1 Answers1

3

What you've described is called lights out puzzle. There's relevant OEIS that gives you the minimal number of nontrivial switch flippings needed to solve the all-ones lights out problem on an n X n square.

Wikipedia describes a general sketch of algorithm how to solve it. You might be also interested in this answer here on SO, which includes a link to example implementation. Citing the answer:

The idea is to set up a matrix representing the button presses a column vector representing the lights and then to use standard matrix simplification techniques to determine which buttons to press. It runs in polynomial time and does not require any backtracking.

Community
  • 1
  • 1
rr-
  • 14,303
  • 6
  • 45
  • 67