Daniel Ratner

Papers

Total Citations

191

H-Index

About

Daniel Ratner is a foundational figure in the study of heuristic search and combinatorial problem-solving, best known for his seminal work on the \((n^2-1)\)-puzzle—a generalization of the classic 15-puzzle. His 1990 paper, "The \((n^2-1)\)-puzzle and related relocation problems," has garnered 188 citations, establishing a rigorous theoretical framework for understanding the complexity and tractability of sliding-tile puzzles. Ratner demonstrated that these puzzles are not merely recreational but serve as powerful testbeds for evaluating heuristic search algorithms, proving their utility in distinguishing effective from ineffective search strategies. His earlier dissertation (1986) laid critical groundwork by exploring theoretical and practical complexity issues in heuristic search, cementing the 8- and 15-puzzles as canonical benchmarks in artificial intelligence. Ratner’s contributions have profoundly influenced algorithm design, particularly in domains requiring efficient state-space exploration, such as robotics, planning, and combinatorial optimization. His work remains essential reading for researchers and students seeking to understand the interplay between problem structure and search performance.