Efficient Solution of Space-Filling Puzzles.

Abstract

The Eight-queens, the Mutilated Checkerboard of Golomb, Instant Insanity, and the various figures that can be built out of the seven Soma pieces are all examples of space-filling puzzles. Such puzzles may be described in terms of sets and groups. Puzzle solution is then seen to be a special case of finding an exact cover for a set. The latter can be solved by backtrack algorithms. Certain well-known combinatorics-reducing counting arguments applicable to the puzzles are formalized relative to the exact cover problem. Then the special group structure of the space-filling puzzles is used to choose specific counting arguments and to pick representatives for symmetrically equivalent solutions. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1978
Accession Number
ADA052951

Entities

People

  • M. J. Fay
  • T. J. Pennello
  • William M. Mckeeman

Organizations

  • University of California, Santa Cruz

Tags

Communities of Interest

  • Advanced Electronics
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Combinatorial Analysis
  • Computations
  • Computer Programming
  • Contracts
  • Electronics Laboratories
  • Equations
  • Geometry
  • Information Science
  • Information Systems
  • Insanity
  • Mathematics
  • Military Research
  • Naval Operations
  • New York
  • Universities

Readers

  • Approximation Theory.
  • Computational Linguistics
  • Game Theory.

Technology Areas

  • Space