Generalizations and optimal solutions for coin sorting puzzles

摘要

This paper generalizes a class of coin puzzles previously known for small and fixed numbers of coins. In these puzzles, the challenge is to sort coins with theoretically smallest possible number of moves. This paper presents two algorithms that solve two different versions of coin sorting puzzles in optimal number of steps, also pointing out two other versions which cannot be solved in any number of steps. Small versions of these puzzles have appeared in several books and we b sites but a general solution has never been presented. Algorithms presented in this paper make enhanced features possible for software implementations, and increase their potential for appreciation by puzzle enthusiasts.