Pancakes, Puzzles, and Polynomials: Cracking the Cracker Barrel
ACM SIGACT News, March 2004.
 |
The 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
Description
With 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.
Code
- 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.
Resources
- 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.
