Dead Cell Analysis in Hex and the Shannon Game


Ynvgi Björnsson, Ryan Hayward, Michael Johanson and Jack van Rijswijck. Dead Cell Analysis in Hex and the Shannon Game. In Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge (GT04 Paris), pages 45-60, 2007.

Download


Abstract

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 NP- complete 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.


BibTeX

@InProceedings{ 2007-gtip-deadcell,
  Title = "Dead Cell Analysis in Hex and the Shannon Game",
  Author = "Yngvi Bj{"o}rnsson and Ryan Hayward and Michael Johanson 
            and Jack van Rijswijck",
  Booktitle = "Graph Theory in Paris: Proceedings of a Conference in 
               Memory of Claude Berge (GT04 Paris)",
  Year = "2007",
  Pages = "45-60",
  Publisher = "Birkauser"
}