Pancakes, Puzzles, and Polynomials: Cracking the Cracker Barrel
Christopher Frost, Michael Peck, David Evans.
ACM SIGACT News, March 2004.
AbstractThe Cracker Barrel peg game is a simple, one-player game commonly found on tables at pancake restaurants. In this paper, we consider the computational complexity of the Cracker Barrel problem. We show that a variation of a generalization of the problem is NP-complete.
Leave only one — you're genius,
. . . Leave four or more'n you're just plain "eg-no-ra-moose"".
Cracker Barrel peg game instructions
DescriptionWith over 1.5 million sales, the Cracker Barrel peg game is an entertaining puzzle found on tables at pancake restaurants. We have shown that solving a variation of the peg game is an NP-complete problem.
Full Paper (4 pages): Pancakes, Puzzles, and Polynomials: Cracking the Cracker Barrel Game. SIGACT News, March 2004.
- Scheme source code for a Cracker Barrel solver, as mentioned in the paper: pegboard.ss.
- Java source code for a Cracker Barrel solver: ps4-mine.zip. See http://www.cs.virginia.edu/cs201j/problem-sets/ps4/comments.html for a description of the code, and CS201J Problem Set 4 for the original assignment.
- Christopher Frost and Michael Peck. Pancakes, Puzzles, and Polynomials: Cracking the Cracker Barrel Game. Presentation at the University of Virginia Undergraduate Research and Design Symposium, Spring 2003.
- CS200 Lectures that discuss the pegboard puzzle: Lecture 11: Pegboard Puzzle (discusses interesting aspects of the pegboard code), Lecture 19: Golden Ages and Astrophysics (discusses the computational complexity of the pegboard code).
- Cracker Barrel's web site. Play the Cracker Barrel game and learn about its history.
- Puzzling Pegboard! — a much less frustrating pegboard game created by Dan Andrino, Peter Chapman, Michael Chen, Chris Lee, Nicholas Loffredo for a cs3102 assignment.
David Evans - Publications
University of Virginia
Department of Computer Science