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 (= 92) 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 n2 × n2 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.