| Peg-Solitaire, String Rewriting Systems and Finite Automata (1997) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider a class of length-preserving string rewriting systems and show that the set of encodings of pairs of strings ! s; f ? such that f can be derived from s using the rewriting rules can be accepted by finite automata. As a consequence, we show the existence of a linear time algorithm for determining the solvability of a given k Theta n peg-solitaire board, for any fixed k. This result is in contrast to the recent results of [UEHA] and [AVIS] that the same problem is NP-hard for n Theta n boards. We look at some related string rewriting systems and find conditions under which the encodings of the pairs ! s; f ? where f can be derived from s is regular. 1 Introduction Peg Solitaire is one of the most popular solitaire board games. Its history dates back to at least seventeenth century. It has been sold as a board game in various shapes, sizes and names. A complete chapter of the well-known work on mathematical games due to Berlekamp et al. [BERL] is devoted to peg-solitaire.... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||