1

2

3

4

5

6

7

8

9

erase

## Sudoku Font |
## by Erik Demaine and Martin Demaine, 2021 |

**Sudoku**
or Number Place is among the most famous pencil-and-paper puzzles,
rising in popularity in 2005
to rival even crossword puzzles,
with daily puzzles in the New York Times.
Its standard form consists of a 9 × 9 grid
decomposed into 3 × 3 subgrids that are each
3 × 3. A puzzle has some cells pre-filled with
numbers between 1 and 9; the goal is to fill in the remaining cells
such that every row, column, and 3 × 3 subgrid
has every number between 1 and 9 (each exactly once).

**Fonts.**
In this typeface, each letter is represented by a standard Sudoku
puzzle whose unique solution “draws the letter” in the
following sense: if you connect together edge-adjacent squares having
**consecutive numbers** (1 to 2, 2 to 3, …, 8 to 9), then the
**longest path** through these connections draws the letter shape.
Consecutive numbers are easy for the puzzle solver to keep track of,
and somewhat controllable by the puzzle designer, but it also seems
impossible to avoid spurious consecutive-number connections;
the longest path allows us to clean out these spurious connections.
(Inglis and Kaplan considered other approaches to designing Sudoku puzzles whose solution generate images.)

In the **Solved** font, you can see the completely solved puzzle,
which is nice for visualizing the font. But more fun is
the **Puzzle** font, where you just see enough numbers to uniquely
determine the solution, and you need to solve the puzzle to figure out
the hidden letter. You can interactively solve the puzzle by clicking
on a square and either typing the number you want to fill (1 through 9
or 0/delete/backspace to erase),
or clicking on the desired action at the top of the screen.
You can also use arrow keys (or vi's hjkl) to move around squares.
For each letter, we have designed 81 (= 9^{2}) different
puzzles that solve to the same longest path, and they are chosen at
random, so even repeated letters in a message offer distinct puzzles
and no shortcuts for recognizing duplicates. (If you want to change
the random selections made for all letters, click the **Randomize**
button.)
•
If you make a mistake (duplicate numbers in the same
row/column/subgrid), their text will turn red (unless you turn off
**Mistakes** visualization).
•
If you're stuck, you can turn on **Hints** visualization,
which will highlight squares (in green) that currently have only
one way to fill them in. (This makes the puzzles quite easy.)
•
You can also turn on or off **Consecutive edges**
(among the grid filled in so far) and the **Longest path** through
these edges (which, in puzzle mode, shows only when you solve the
entire puzzle).

**Related mathematics.**
Generalized to an
*n*^{2} × *n*^{2} grid
with *n* × *n* subgrids,
Sudoku is **NP-complete**, and even stronger,
**ASP-complete**.
This result means that it is computationally intractable to determine
whether a puzzle has a solution, and furthermore, whether it has
another solution even if we are given one or more solutions.
(The latter question is important for puzzle design, to guarantee a
unique solution.)
Even once you solve the Sudoku puzzles,
finding the longest path is also NP-complete,
even in grids.

Most real-world Sudoku puzzles (including those in this typeface) are designed in such a way to guarantee unique solvability. The general approach is to start with a solved puzzle, then repeatedly remove clues that can be uniquely determined by the remaining clues, using one or more techniques/strategies/rules (see variation descriptions). In this typeface, we just use the simplest (depth-1) rule: if a square can be filled in by only one number that does not duplicate another number in the same row, column, or subgrid, then fill it in.

**Genesis.**
This typeface design started shortly after Erik taught
a lecture
in MIT's Fundamentals of Programming class (6.009)
and realized how easy it is to write a brute-force Sudoku solver.
We designed the longest paths by hand, and used a solver to randomly
fill in the remaining squares (going back to the hand-drawing board
if no completion was possible), and then randomly removing clues that
could be filled back in by the simplest no-duplicates rule described
above.
We also prioritized the solver to avoid adding any extra consecutive
edges off the intended longest, when possible. In two letters
(N and Q), this extra goal is impossible, so we just constrained the
longest path to not change.
(These computations take a while, so we precomputed them.)

Check out other mathematical and puzzle fonts. • Feedback or not working? Email Erik.