3 ms·
A particular generalization of Pac-Man is NP-Hard with respect to the size of the board. The actual arcade game, on the other hand, can't be NP-Hard because it
by Strilanc 14y ago
A particular generalization of Pac-Man is NP-Hard with respect to the size of the board.
The actual arcade game, on the other hand, can't be NP-Hard because it has a fixed board. It can be solved in constant time.
Article titles like this are a major reason people end up with muddled ideas about technical concepts.
- gpcz 14y agoAlso, since the game is deterministic, there are known patterns that let a player win every possible board with maximum points: http://www.math.montana.edu/~hyde/pacman/ http://www.math.montana.edu/~hyde/pacman/ .