Integer programming based algorithms for peg solitaire problems

Abstract: Peg solitaire is a classical one player game. In this paper. we dealt with the peg solitaire problem as an integer programming problem. We proposed algorithms based on the backtrack search method and relaxation methods for integer programming problem. The algorithms first solve relaxed problems and get an upper bound of the number of jumps for $\mathrm{e}\mathrm{a}\mathrm{c}1_{1} $ jump position. This upper bound saves much time at the next stage of backtrack searching. While solving the relaxed $\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{S}_{i} $ we can prove many peg solitaire problems are infeasible. We proposed two types of backtrack $\mathrm{s}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}_{j} $ forward-only searching and forward-backward searching. Our algorithnl can solve all the peg solitaire problem instances we tried and the total computational time is less than 20 minutes on an ordinary notebook personal computer