In 1981 Claude Berge asked about combinatorial properties that might be used to solve Hex puzzles. In response, we establish properties of dead, or negligible, cells in Hex and the Shannon game.
A cell is dead if the colour of any stone placed there is irrelevant to the theoretical outcome of the game. We show that dead cell recognition is NPcomplete for the Shannon game; we also introduce two broader classifications of ignorable cells and present a localized method for recognizing some such cells. We illustrate our methods on Hex puzzles created by Berge.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten