or anyone explain how to solve this problem
Think about winnnig and loosing positions.
A winning position is any position where the next move leads to win the game.
A loosing position is any position where the next move leads to a winning position for the opponent.
And again, a winning position is one who leads to a loosing position for the opponent.
Put the rules of the game into a recursive function of the above scheme.
If that solution is to slow, add memoization.