Modelling and solving English peg solitaire.

*(English)*Zbl 1086.90070Summary: Peg Solitaire is a well known puzzle, which can prove difficult despite its simple rules. Pegs are arranged on a board such that at least one ’hole’ remains. By making draughts/checkers-like moves, pegs are gradually removed until no further moves are possible or some goal configuration is achieved. This paper considers the English variant, consisting of a board in a cross shape with 33 holes. Modelling Peg Solitaire via constraint or integer programming techniques presents a considerable challenge and is examined in detail. The merits of the resulting models are discussed and they are compared empirically. The sequential nature of the puzzle naturally conforms to a planning problem, hence we also present an experimental comparison with several leading AI planning systems. Other variants of the puzzle, such as ’Fool’s Solitaire’ and ’Long-hop’ Solitaire are also considered.

##### MSC:

90C90 | Applications of mathematical programming |

90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |

PDF
BibTeX
XML
Cite

\textit{C. Jefferson} et al., Comput. Oper. Res. 33, No. 10, 2935--2959 (2006; Zbl 1086.90070)

Full Text:
DOI

##### References:

[1] | Beasley, J.D., The ins and outs of peg solitaire, (1992), Oxford University Press Oxford |

[2] | Uehara, R.; Iwata, S., Generalized hi-Q is NP-complete, Transactions of IEICE, 73, 270-273, (1990) |

[3] | de Bruijn, N.G., A solitaire game and its relation to a finite field, Journal of recreational mathematics, 5, 133-137, (1972) |

[4] | Berlekamp ER, Conway JH, Guy RK. Winning ways for your mathematical plays, vol. 2: games in particular. London: Academic Press; 1982. p. 729-30. |

[5] | Avis D, Deza A. On the boolean solitaire cone. Technical report, McGill University and Tokyo Institute of Technology, 1999. · Zbl 0988.91017 |

[6] | Moore, C.; Eppstein, D., One-dimensional peg solitaire, and duotaire, (), 341-350 · Zbl 1062.91527 |

[7] | Beeler M, Gosper RW, Schroeppel R. HAKMEM. Technical report, MIT, Artificial Intelligence Laboratory, Memo AIM-239; 1972. |

[8] | Allen, J.; Hendler, J.; Tate, A., Readings in planning, (1990), Morgan Kaufmann Los Altos, CA |

[9] | Kautz, H.; Walser, J.P., State-space planning by integer optimization, (), 526-533 |

[10] | Vossen, T.; Ball, M.; Lotem, A.; Nau, D., Applying integer programming to AI planning, Knowledge engineering review, 16, 85-100, (2001) |

[11] | Haas A. The case for domain-specific frame axioms. Proceedings of the workshop on the frame problem in artificial intelligence, 1987. |

[12] | Bockmayr A, Dimopoulos Y. Mixed integer programming models for planning problems. Proceedings of the CP98 workshop on constraint problem reformulation, 1998. |

[13] | Jefferson C, Miguel A, Miguel I, Tarim A. Modelling and solving english peg solitaire. Proceedings of the 5th international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR), 2003. p. 261-75. |

[14] | Kautz, H.; Selman, B., Pushing the envelopeplanning, propositional logic, and stochastic search, (), 1194-1201 |

[15] | van Beek, P.; Chen, X., Cplana constraint programming approach to planning, (), 585-590 |

[16] | Do, M.B.; Kambhampati, S., Planning as constraint satisfactionsolving the planning graph by compiling it into CSP, Artificial intelligence, 132, 151-182, (2001) · Zbl 0983.68181 |

[17] | Blum, A.; Furst, M., Fast planning through planning graph analysis, Artificial intelligence, 90, 281-300, (1997) · Zbl 1017.68533 |

[18] | Miguel I. Dynamic flexible constraint satisfaction and its application to AI planning, Springer distinguished dissertation series, 2004. |

[19] | Kautz, H.; Selman, B., Unifying SAT-based and graph-based planning, (), 318-325 |

[20] | Moskewicz, M.W.; Madigan, C.F.; Zhao, Y.; Zhang, L.; Malik, S., Chaffengineering an efficient SAT solver, () |

[21] | Koffman, J.; Nebel, B., The FF planning systemfast plan generation through heuristic search, Journal of artificial intelligence research, 14, 253-302, (2001) · Zbl 0970.68044 |

[22] | Bonet, B.; Geffner, H., Planning as heuristic search, Artificial intelligence, 129, 5-33, (2001) · Zbl 0971.68146 |

[23] | Long, D.; Fox, M., Efficient implementation of the plan graph in STAN, Journal of artificial intelligence research, 10, 87-115, (1999) · Zbl 0914.68180 |

[24] | Fikes, R.; Nilsson, N., Stripsa new approach to the application of theorem proving to problem solving, Artificial intelligence, 5, 2, 189-208, (1971) · Zbl 0234.68036 |

[25] | Gent, I.; Smith, B., Symmetry breaking in constraint programming, (), 599-603 |

[26] | Fahle T, Schamberger S, Sellman M. Symmetry breaking. Proceedings of the principles and practice of constraint programming, Lecture Notes in Computer Science, vol. 2239, 2001. p. 93-107. · Zbl 1067.68631 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.