Enumerating Cryptarithms Using Deterministic Finite Automata

Yuki Nozaki; Diptarama Hendrian; Ryo Yoshinaka; Takashi Horiyama; Ayumi Shinohara

paper

Enumerating Cryptarithms Using Deterministic Finite Automata

arXiv:1807.11580

Abstract

A cryptarithm is a mathematical puzzle where given an arithmetic equation written with letters rather than numerals, a player must discover an assignment of numerals on letters that makes the equation hold true. In this paper, we propose a method to construct a DFA that accepts cryptarithms that admit (unique) solutions for each base. We implemented the method and constructed a DFA for bases $k \leq 7$ . Those DFAs can be used as complete catalogues of cryptarithms,whose applications include enumeration of and counting the exact numbers $G_{k} (n)$ of cryptarithm instances with $n$ digits that admit base- $k$ solutions. Moreover, explicit formulas for $G_{2} (n)$ and $G_{3} (n)$ are given.