In the spirit of Tetris, Sudoku, Minesweeper, and other games, we recently determined at the C&O open problem session that the game Polarium Advance is NP-complete. There is a pretty straightforaward reduction from “Hamiltonian path in induced subgraph of a grid graph” to Polarium Advance. That problem can be reduced from “Hamiltonian path in bipartite planar graph of maximum degree 3” as was shown in a 1982 paper by Itai, Papadimitriou and Szwarcfiter. While it would be nice to have developed a paper, it is somewhat encouraging to know that their paper used basically the same idea that we were developing, we were just a quarter of a century too late.
Here’s the formal statement of Polarium Advance.
Input: Integers m, n; an m-by-n grid graph; a (not necessarily proper) 2-colouring of the grid.
Question: Is there a simple path on the graph, such that after inverting the colours on that path, every row is monochromatic?
QED and NOM 