スーパーパズにおける順位優先探索

概要

論文の詳細を見る
Superpuzz is a solitaire game with one deck of cards and was adopted as a problem on GPCC in 1991. Superpuzz has a characteristic that Aces can move more freely than other cards in the game. So you cannot find a solution by adding a new node simply to the game tree because the same node will appear in the tree many times. I use a data structure called `Patricia' so that there is no duplication of nodes in the game tree. I have made clear that it is possible to search the game tree entirely up to the case of the half size (6 columns) on a typical computer for personal use. In this paper, I found that the number of nodes searched in a priority-first search is less than those in the simple depth-first search in average case. The priority adopted here is decided from the nature of the game that the nearer is a node to the state of success, the more Aces are on the right-most column. It is expected that the number of nodes which will be searched until the first solution is found will be about 108 in case of the full-size Superpuzz.