-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.pug
199 lines (183 loc) · 9.02 KB
/
index.pug
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
doctype html
html
head
title Sudoku Font
meta(name="viewport", content="width=device-width, initial-scale=1, user-scalable=no")
script(type="text/javascript", src="node_modules/@svgdotjs/svg.js/dist/svg.min.js")
script(type="text/javascript", src="node_modules/furls/furls.js")
script(type="text/javascript", src="node_modules/font-webapp/font-webapp.js")
script(type="text/javascript", src="fontGen.js")
script(type="text/javascript", src="sudoku.js")
script(type="text/javascript").
if (/[?&]hud=0/.test(window.location.search)) // avoid blinking
document.documentElement.classList.add('hud-false');
link(href="https://fonts.googleapis.com/css?family=Libre+Franklin:700&display=swap", rel="stylesheet")
style
:stylus
.hud-false > body > *:not(#output), #hud
display: none
textarea
vertical-align: middle
td
vertical-align: top
#randomize
margin-top: 0.5em
include:stylus sudoku.styl
//#include virtual="../../analytics.html"
body
#numbers
#number1 1
#number2 2
#number3 3
#number4 4
#number5 5
#number6 6
#number7 7
#number8 8
#number9 9
#number0 erase
table.w-100
tr
td.text-left.align-middle
h1
a(href="./") Sudoku Font
td.text-right.align-middle
h2 by <a href="https://erikdemaine.org/">Erik Demaine</a> and <a href="http://martindemaine.org">Martin Demaine</a>, 2021
table#data.w-100.noprint
tr
td
label(for="text") Enter text to render:
textarea#text(name="text", rows=4, cols=40) text
td
input#animMode(type="radio", checked, name="mode", value="anim")
label(for="animMode") Animation
br
input#solvedMode(type="radio", name="mode" value="solved")
label(for="solvedMode") Solved
br
input#puzzleMode(type="radio", name="mode", value="puzzle")
label(for="puzzleMode") Puzzle
br
button#randomize Randomize
td
input#edges(type="checkbox", checked)
label(for="edges") Consecutive edges
br
input#path(type="checkbox", checked)
label(for="path") Longest path
br
input#mistakes(type="checkbox", checked)
label(for="mistakes") Mistakes
br
input#hints(type="checkbox")
label(for="hints") Hints
br
input#hud(type="checkbox", checked)
#size.noprint
p
#output.w-100
.text-right.noprint
button#nohud(title="Use browser back button to restore interface.") Hide all but font rendering
hr.noprint
p.noprint.
<b><a href="https://en.wikipedia.org/wiki/Sudoku">Sudoku</a></b>
or Number Place is among the most famous pencil-and-paper puzzles,
<a href="https://trends.google.com/trends/explore?date=all&q=%2Fm%2F04x1d_,%2Fm%2F0j4mv">rising in popularity in 2005</a>
to rival even crossword puzzles,
with <a href="https://www.nytimes.com/puzzles/sudoku/">daily puzzles in the New York Times</a>.
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).
p.noprint.
<b>Fonts.</b>
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
<b>consecutive numbers</b> (1 to 2, 2 to 3, …, 8 to 9), then the
<b>longest path</b> 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.
(<a href="https://archive.bridgesmathart.org/2011/bridges2011-187.pdf">Inglis and Kaplan</a> considered other approaches to designing Sudoku puzzles whose solution generate images.)
p.noprint.
In the <b>Solved</b> font, you can see the completely solved puzzle,
which is nice for visualizing the font. But more fun is
the <b>Puzzle</b> 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 wasd or vi's hjkl) to move around squares.
For each letter, we have designed 81 (= 9<sup>2</sup>) 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 <b>Randomize</b>
button.)
•
If you make a mistake (duplicate numbers in the same
row/column/subgrid), their text will turn red (unless you turn off
<b>Mistakes</b> visualization).
•
If you're stuck, you can turn on <b>Hints</b> 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 <b>Consecutive edges</b>
(among the grid filled in so far) and the <b>Longest path</b> through
these edges (which, in puzzle mode, shows only when you solve the
entire puzzle).
p.noprint.
<b>Related mathematics.</b>
Generalized to an
<i>n</i><sup>2</sup> × <i>n</i><sup>2</sup> grid
with <i>n</i> × <i>n</i> subgrids,
Sudoku is <b>NP-complete</b>, and even stronger,
<b><a href="https://academic.timwylie.com/17CSCI4341/sudoku.pdf">ASP-complete</a></b>.
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,
<a href="https://en.wikipedia.org/wiki/Longest_path_problem">finding the longest path</a> is also NP-complete,
<a href="https://arxiv.org/abs/1706.10046">even in grids</a>.
p.noprint.
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
(<a href="https://www.sudokudragon.com/sudokustrategy.htm">see</a>
<a href="https://www.conceptispuzzles.com/index.aspx?uri=puzzle/sudoku/techniques">variation</a>
<a href="https://www.kristanix.com/sudokuepic/sudoku-solving-techniques.php">descriptions</a>).
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.
p.noprint.
<b>Genesis.</b>
This typeface design started shortly after Erik taught
<a href="https://py.mit.edu/_static/fall19/lectures/lecture04/lecture4.zip">a lecture</a>
in MIT's Fundamentals of Programming class (<a href="https://py.mit.edu/fall19">6.009</a>)
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.)
p.noprint.
Check out <a href="http://erikdemaine.org/fonts/">other mathematical and
puzzle fonts</a>. • Feedback or not working?
<a href="mailto:[email protected]">Email Erik</a>. •
<a href="https://github.com/edemaine/font-sudoku">Source code on GitHub</a>.