An Algorithmic Solution for a Single Player Computer Game
Daxin Zhu, Lei Wang, Jun Tian, Xiaodong Wang · International Journal of Applied Mathematics & Statistics/International journal of applied mathematics and statistics · 2014
In this paper we study a single player game called moving checkers. The initial state of the game are n black checkers followed by n white checkers put on a table from left to right in a row. The final state of the game are the 2n checkers put from left to right in a row with alternate colors. A move of the game consists of shifting two adjacent checkers, keeping their order, into the current two vacant positions. The goal of the game is to make a smallest number of moves to reach the final state of the game from the initial state. We are interested in algorithms which, given integers n, generate the corresponding move sequences to reach the final state of the game with smallest number of steps. In this paper we present an optimal algorithm to generate an optimal move sequence of the game consisting of n black checkers and n white checkers, and finally, we present an explicit solution for the general game of size n.