Efficient Solving of Birds of a Feather Puzzles

  • Todd W. Neller Gettysburg College
  • Connor Berson Gettysburg College
  • Jivan Kharel Gettysburg College
  • Ryan Smolik Gettysburg College

Abstract

In this article, we describe the lessons learned in creating an efficient solver for the solitaire game Birds of a Feather. We introduce a new variant of depth-first search that we call best-n depth-first search that achieved a 99.56% reduction in search time over 100,000 puzzle seeds. We evaluate a number of potential node-ordering search features and pruning tests, perform an analysis of solvability prediction with such search features, and consider possible future research directions suggested by the most computationally expensive puzzle seeds encountered in our testing.

Published
2019-07-17
Section
EAAI Symposium: Full Papers