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

概要

論文の詳細を見る
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 be appeared in the tree many times. I use a data structure called 'Patricia' so that there is no duplication of nodes in the game tree. 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. It is expected that a game tree has nodes of 10^8 order and about 100 levels in the average case of the full size (13 columns) before the first solution is found. In the case of the full size, the program found solutions in 2 cases after searching entirely in the game tree and aborted with no solution because of memory limitation in 98 cases out of 100 times of try.