Grundy Number For a Matrix

Question

How to calculate the Grundy number for states of a 4*4 matrix. A valid move consists of transforming the 1s into 0s of a submatrix having all 1s.

Example:

Grundy Number = 2

I checked for smaller cases and calculated the Grundy number for that, but couldn't extend it for any binary 4*4 matrix. So, please help me to calculate this.

Note: Can convert 1 to 0 only in submatrix.

I want to write code for that, so I want help in that. I know Grundy Number calculation but can't transform into a code for this problem. — Deepak, Mar 04 '17 at 12:32
first you have to state the problem; as far as I can see, you are given a *matrix*, not *graph* (Grundy number is about *graphs' nodes coloring*). What is the graph which corresponds to the matrix? — Dmitry Bychenko, Mar 04 '17 at 12:35
Grundy number is not only for graph. I want grundy number for a state( to later transform into Nim game), thus for a state of 4*4 binary matrix, I want to have grundy number for that state( Transform 1 to 0 in submatrix having all 1s )? — Deepak, Mar 04 '17 at 12:40
Can u explain how algorithm proposed by you works for the above case and gives grundy state as 2? — Deepak, Mar 04 '17 at 12:41
https://discuss.codechef.com/questions/26237/caos3-editorial — Dmitry Bychenko, Mar 04 '17 at 12:48
Yes, I saw that earlier but how can I use it to here, it is a different problem. If u have a idea, can you share that? — Deepak, Mar 04 '17 at 12:50
I could just think of brute force which also is petty difficult to implement. I just want the idea, I'll try to code myself. — Deepak, Mar 04 '17 at 12:54
Stack Overflow is not a code writing service, it's expected that you attempt to code this yourself. I would suggest you do some research on your issue (maybe try the search box at the top of the page) and make an attempt at writing some code yourself. If/when you come across any issues with your code ask again and explain what you have tried, and why it did not work for you. See [How to Ask](http://stackoverflow.com/help/how-to-ask) for help with asking a great question as well as [Minimum, complete, verifiable example](http://stackoverflow.com/help/mcve). — Renats Stozkovs, Mar 04 '17 at 18:51
I am never asking for the code, I am just asking for the idea. I have used bruteforce idea where I try all the cases but it is quite slow, therefore I was asking just for an idea, maybe these grundy number form a pattern or so which I am unable to find. I am just asking that. — Deepak, Mar 04 '17 at 19:33
This was also asked on MSE: http://math.stackexchange.com/questions/2171470/grundy-number-for-a-matrix — Mark S., Mar 06 '17 at 18:22

maraca · Answer 1 · 2017-03-05T17:50:59.800

The Grundy number is calculated recursively through the reachable positions:

Start with the final position (all zeros) which is a loss (0).
```
0 0 0 0
0 0 0 0   =   0
0 0 0 0
0 0 0 0
```

Proceed to add ones to the matrix to get the values for the other configurations. Some examples with exactly one 1.

1 0 0 0       0 0 1 0       0 0 0 0       0 0 0 0
0 0 0 0   =   0 0 0 0   =   0 0 1 0   =   0 0 0 1   =   1
0 0 0 0       0 0 0 0       0 0 0 0       0 0 0 0
0 0 0 0       0 0 0 0       0 0 0 0       0 0 0 0

For two 1s we have to distinguish if the 1s are adjacent and can be removed in one move or not.

1 0 1 0       1 0 0 0       1 0 0 0*      0 0 1 0
0 0 0 0   =   0 0 1 0   =   0 0 0 1   =   0 0 0 1   =   0
0 0 0 0       0 0 0 0       0 0 0 0       0 0 0 0
0 0 0 0       0 0 0 0       0 0 0 0       0 0 0 0

0 0 1 0       0 0 0 0
0 0 1 0   =   0 0 1 1   =   2
0 0 0 0       0 0 0 0
0 0 0 0       0 0 0 0

The same for three and more 1s.

1 0 1 0*
0 0 0 1   =   1
0 0 0 0
0 0 0 0

1 0 1 0*      1 0 0 0*      0 0 1 0*
0 0 1 0   =   0 0 1 1   =   0 0 1 1   =   3
0 0 0 0       0 0 0 0       0 0 0 0
0 0 0 0       0 0 0 0       0 0 0 0

Finally we can evaluate the given matrix. Reachable positions from the example are marked with a star *. So we can easily see that the number we are looking for is mex(0, 1, 3) = 2.
```
1 0 1 0
0 0 1 1   =   2
0 0 0 0
0 0 0 0
```

A pseudo program could look as simple as this (the grundy function has to support scalar state and arrays or vectors of states for this to work):

grundy(0) = 0
grundy(state) = mex(grundy(reachableStates(state)))

Thank you for ur help, but how to think of this recurrence in terms of code? I want to know how should I approach this to get the reference for any 4*4 binary matrix where I can choose only a rectangle? — Deepak, Mar 05 '17 at 17:24
Yes, but question still remains how to calculate reachableStates(state)? — Deepak, Mar 05 '17 at 17:57
It's just all possible moves from a position, so you get a bunch of new states for which you have to know the grundy numbers, but becaue you probably don't you have to get the states that can be reached from there and so on that's where the recursion comes in. — maraca, Mar 05 '17 at 17:58
The question has recently changed from 4x4 matrices to nxn matrices. Luckily, your answer is still good. — Mark S., Mar 08 '17 at 03:42

Grundy Number For a Matrix

1 Answers1