Pancakes, Puzzles, and Polynomials: Cracking the Cracker Barrel

Christopher Frost, Michael Peck, David Evans.
ACM SIGACT News, March 2004.

Abstract
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

Resources


CS 655 David Evans - Publications
University of Virginia
Department of Computer Science
David Evans
evans@cs.virginia.edu