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.
Zhu, Daxin; Wu, Yingjie; Wang, Lei; and Wang, Xiaodong
"Complete Solutions for a Combinatorial Puzzle in Linear Time and Its Computer Implementation,"
Applied Mathematics & Information Sciences: Vol. 09
, Article 34.
Available at: https://dc.naturalspublishing.com/amis/vol09/iss2/34