Mixed Integer Linear Programming Models to Solve the Shisen-Sho Puzzle
Renan Spencer Trindade, Guilherme Dhein, Felipe Martins Müller, Olinto César Bassi de Araújo · 2011
Shisen-Sho or Four Rivers is a game with perfect information where the objective is to remove all tiles from the board. In this work we present two mixed integer programming models for solving Shisen-Sho game, as well as techniques to improve the formulations proposed. The first mathematical model considers the classical problem of finding a sequence of moves to remove all tiles from the board, while the second mathematical model considers a variant in which it is necessary to optimize a sequence of movements according to a criterion defined by the authors. Computational results for the two models are presented considering different initial configurations and board dimensions.