Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs Export

@article{buro01simple, abstract = {Amazons is a young board game with simple rules and a high branching factor, which makes it a suitable test-bed for planning research. This paper considers the computational complexity of amazons puzzles and restricted amazons endgames. We first prove the NP-- completeness of the Hamilton circuit problem for cubic subgraphs of the integer grid. This result is then used to show that solving amazons puzzles is a NP-complete task and determining the winner of simple amazons endgames is...}, author = {Buro, Michael}, citeulike-article-id = {550036}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9731}, journal = {Lecture Notes in Computer Science}, keywords = {complexity, games}, pages = {250--??}, posted-at = {2006-03-13 20:59:08}, priority = {0}, title = {Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9731}, volume = {2063}, year = {2001} }

TY - JOUR ID - buro01simple L3 - citeulike-article-id:550036 N2 - Amazons is a young board game with simple rules and a high branching factor, which makes it a suitable test-bed for planning research. This paper considers the computational complexity of amazons puzzles and restricted amazons endgames. We first prove the NP-- completeness of the Hamilton circuit problem for cubic subgraphs of the integer grid. This result is then used to show that solving amazons puzzles is a NP-complete task and determining the winner of simple amazons endgames is... JF - Lecture Notes in Computer Science EP - ?? TI - Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs VL - 2063 SP - 250 KW - complexity KW - games AU - Buro, Michael PY - 2001/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9731 ER -