The shortest game of Chinese Checkers and related problems

Simple item page
dc.creatorBell, George I.
dc.date2008-03-08
dc.date2009-01-13
dc.date.accessioned2026-07-07T12:28:11Z
dc.date.available2026-07-07T12:28:11Z
dc.descriptionIn 1979, David Fabian found a complete game of two-person Chinese Checkers in 30 moves (15 by each player) [Martin Gardner, Penrose Tiles to Trapdoor Ciphers, MAA, 1997]. This solution requires that the two players cooperate to generate a win as quickly as possible for one of them. We show, using computational search techniques, that no shorter game is possible. We also consider a solitaire version of Chinese Checkers where one player attempts to move her pieces across the board in as few moves as possible. In 1971, Octave Levenspiel found a solution in 27 moves [Ibid.]; we demonstrate that no shorter solution exists. To show optimality, we employ a variant of A* search, as well as bidirectional search.
dc.description22 pages, 10 figures; published version
dc.identifierhttps://arxiv.org/abs/0803.1245
dc.identifierhttp://arxiv.org/abs/0803.1245
dc.identifierINTEGERS: Electronic Journal of Combinatorial Number Theory 9 (2009) #G01
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/215457
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subject00A08, 97A20
dc.titleThe shortest game of Chinese Checkers and related problems
dc.typetext

Files

Collections

arXiv