Sudoku in Turing-Complete Unicode Transliteration Rules

Nicolas Seriot (Hacker News, Reddit):

The core Unicode algorithms (normalization, casing, bidi, collation) are deliberately bounded, but UTS #35 transliteration rules, under their natural unbounded semantics, are not. This is a result I haven’t found published before. These rules ship as locale data in ICU, the Unicode library shipped in operating systems, browsers, runtimes, and databases. Whether a given rule file terminates on a given input is undecidable. To prove UTS #35 universality, we compile 2-tag systems (Post, 1943), a model proven universal (Cocke & Minsky, 1964), into transliteration rules. Transliteration rules were designed to turn “é” into “e”. Three lines of them can compute the Collatz function.

KT_Music:

Inspired by this, I tried creating an implementation that “solves #Sudoku” using only UTS#35 transformation rules 😎

Previously:

• Outlandish SQLite Recursive Query Examples
• Solving the “Miracle Sudoku” in Prolog
• Sudoku Solver