Enumeration of Cryptarithms Using Deterministic Finite Automata

被引：0

作者：

Nozaki, Yuki ^{[1
]}

Hendrian, Diptarama ^{[1
]}

Yoshinaka, Ryo ^{[1
]}

Shinohara, Ayumi ^{[1
]}

机构：

[1] Tohoku Univ, Grad Sch Informat Sci, Aoba Ku, 6-6-05 Aramaki Aza Aoba, Sendai, Miyagi, Japan

来源：

IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2018 | 2018年 / 10977卷

关键词：

Cryptartihms; Alphametics; Automaton; DFA; Enumeration;

D O I：

10.1007/978-3-319-94812-6_24

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 <= 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.

引用

页码：286 / 298

页数：13

共 9 条

[1] Solving Cryptarithmetic Problems Using Parallel Genetic Algorithm [J].

Abbasian, Reza ;

Mazloom, Masoud .

SECOND INTERNATIONAL CONFERENCE ON COMPUTER AND ELECTRICAL ENGINEERING, VOL 1, PROCEEDINGS, 2009, :308-312

[2]

Collins T., ALPHAMETIC PUZZLE SO

[3]

Dudeney H. E., 1924, STRAND MAGAZINE, V68, P97

[4]

Endoh H., 2011, P 16 GAM PROGR WORKS, P54

[5]

Endoh H., 2013, THESIS

[6]

Eppstein D., 1987, SIGACT News, V18, P38, DOI 10.1145/24658.24662

[7]

Knuth D. E., 2017, ART COMPUTER PROGRAM, V4

[8]

Luoma K, 2016, SPREADSHEETS EDUC, V9

[9]

Tamura N., CRYPTARITHMETIC PUZZ

← 1 →