Complete Solutions for a Combinatorial Puzzle in Linear Time
Lei Wang, Xiaodong Wang, Yingjie Wu, Daxin Zhu · arXiv (Cornell University) · 2013
In this paper we study a single player game consisting of $n$ black checkers and $m$ white checkers, called shifting the checkers. We have proved that the minimum number of steps needed to play the game for general $n$ and $m$ is $nm + n + m$. We have also presented an optimal algorithm to generate an optimal move sequence of the game consisting of $n$ black checkers and $m$ white checkers, and finally, we present an explicit solution for the general game.