How to implement undo function without violating encapsulation?

Lets image a simple board game:

• Every turn you can place one figure.
• You must not remove a figure.
• When a certain condition is met, the game is over.

Now I want to implement an undo function. I have to following classes:

Game {
  (...)
  + placeFigure(int,int): void
  + isGameOver(): bool
}

Move {
  (...)
  + Move(Game,int,int)
  + execute(): void
  + undo(): void
}

History {
  - moves: List<Move>
  (...)
  + add(Move): void
  + undo(): void
}

My problem is, in order for a move to be undone, I have to add a function removeFigure. But, calling this function improperly would result in an invalid state. The other idea I hade was to make Move a nested class of Game. This however, will bloat the Game class and make it tedious to add other possible moves in the future.

Should I implement one of those ideas? Perhaps there is a simpler solution to this problem?