From B-splines to Sudoku and KenKen
The Mathematics of Carl de Boor
Introduction
Halfway down Carl de Boor’s home page at the University of Wisconsin, between links to approximation-theory journals and a tutorial on the vi editor, there’s a one-line invitation: if you do Sudoku and use Matlab, try sudokon. I first discovered sudokon on the Matlab File Exchange, but it runs only in Matlab. sudokon displays a Sudoku board where every empty cell shows the digits that could still go there, and each digit you place crosses itself off everywhere it can no longer appear. It doesn’t solve the puzzle, but you don’t have to keep track of which digits are still available for any cell.
Sudokon.
I liked it enough to rebuild it, first in Python and then for the browser, and then to add KenKen. You can play both by clicking the link above (it opens in a new tab). But the more interesting story is about Carl de Boor, a mathematician who turned splines from a draftsman’s tool into mathematics a computer can work with, at a time when car companies were starting to design body panels on computers. The puzzle board comes second, along with a short proof in Lean that its central rule can never put the same digit in a row twice. De Boor’s home page shows the logo and Latin motto of a Polish academy, with a note that he doesn’t belong to it but likes the motto: dubium scientiae initium, “doubt is the beginning of science.”
Carl de Boor
Carl de Boor.
Carl de Boor saw what splines could do in the early 1960s while working at the General Motors Research Center, where splines were already being used to design cars. In Bézier polynomial curve regression we described the analysis of Paul de Casteljau at Citroën and Pierre Bézier at Renault, both of whom worked out the curves that now carry Bézier’s name while designing car bodies. The car industry needed a way to tell a computer what shape a car body should be, and three companies started looking for the mathematics to describe these shapes.
De Boor started graduate school at the University of Michigan in 1964. In 1972 the University of Wisconsin hired him straight in as a full professor, at the suggestion of Iso Schoenberg, the mathematician usually called the father of splines. Schoenberg worked in Madison from 1966 until his death in 1990, so for nearly two decades the two of them were colleagues. De Boor is now professor emeritus of computer sciences and mathematics there.
His honors include the National Medal of Science, membership in the National Academy of Sciences and the National Academy of Engineering, and SIAM’s John von Neumann Lecture in 1996. His book A Practical Guide to Splines (1978, revised 2001) is still the standard reference for anyone who has to compute with splines, and with S. D. Conte he wrote the textbook Elementary Numerical Analysis: An Algorithmic Approach, now reprinted in SIAM’s Classics series.
Splines
Before computers, a draftsman who needed a smooth curve through a set of points bent a thin strip of wood or plastic, held in place by weights, and traced along it, called a spline. The mathematical version replaces the strip with a chain of polynomials that meet end to end.
Schoenberg put it this way in 1964: “Polynomials are wonderful even after they are cut into pieces.” A single polynomial has to bend everywhere at once to follow a complicated shape, and high-degree polynomials wiggle badly between the points they pass through. A spline uses low-degree pieces, often cubics, joined at points called knots, with the joins arranged so the first and second derivatives match on both sides. It generates a curve that is smooth to the eye and still easy to compute.
Every spline of a given degree and knot sequence can be written as a sum of a few standard pieces, which makes it possible to store, evaluate, and edit the curve as just a list of coefficients. The B-splines, which de Boor helped build that theory around, are the best-known example.
B-splines and the recursion
Pick a non-decreasing sequence of knots . The B-splines of degree are the simplest functions there are: is on the interval between knot and knot , and everywhere else,
Every higher degree is built from the one below it,
Here is the degree, counts which B-spline we mean, and is the point where we evaluate it. When two knots coincide, a denominator becomes zero; the rule is that any term whose denominator is zero is simply dropped.
This is the Cox–de Boor recursion. In the early 1970s de Boor showed that a B-spline of one degree can always be written this way, as a combination of two B-splines of the degree below with coefficients that are straight lines. The intuition is a weighted blend of two neighbors. To get a degree- B-spline, take two adjacent B-splines of degree and mix them. The first weight, , climbs from to as crosses the interval, and the second weight falls from to over the interval one knot further along. Each weight is a straight line, so every step raises the degree by one, and the blending smooths out the corners left by the step below.
B-splines of degree 0 to 3 on equally spaced knots, built one degree at a time from the recursion.
Figure 3 shows what the recursion does. The degree-0 functions are boxes. Blending two boxes gives a triangle (degree 1), blending two triangles gives a rounded hump (degree 2), and blending two humps gives the smooth bell of the cubic B-spline.
Three properties fall out of the construction, and you can check each one numerically for the cubic B-splines in the figure:
- Each is zero outside the interval from to , so a cubic B-spline lives on just four knot intervals.
- No B-spline is ever negative.
- Wherever enough B-splines overlap, they add up to exactly .
A spline curve is a weighted sum of B-splines, with control points as the weights,
Because the B-splines are non-negative and add up to , every point on the curve is an average of nearby control points, which is the same behavior that makes Bézier curves easy to design with. The difference is that B-splines are local: move a control point, and you only change the curve over a short interval. With Bézier curves, the change propagates all the way across.
When de Boor told Schoenberg about the recurrence, Schoenberg was skeptical at first. Adding up rough functions and getting something smoother can happen by accident, he thought, but not reliably every time. He changed his mind quickly enough that, as mentioned above, he brought de Boor to Wisconsin in 1972.
A Bézier curve is a B-spline
Earlier, we described Bézier polynomials in Bézier polynomial curve regression. Take a degree- B-spline and put all the knots at the two ends: copies of followed by copies of . With no knots in between, there is only one polynomial piece, and the recursion produces exactly the Bernstein polynomials,
which are the weights in the Bézier formula. So every Bézier curve is a B-spline curve with this particular knot sequence.
The shark fin from the Bézier article. The degree-4 Bézier curve and the degree-4 B-spline with knots 0,0,0,0,0,1,1,1,1,1 coincide; the cubic B-spline with an interior knot at ½ uses the same control points and gives a different curve.
You can check this with the shark-fin control points from the Bézier article. The Bézier curve and the clamped degree-4 B-spline agree to within , which is floating-point rounding.
Figure 4 also shows what happens when we keep the same five control points but switch to a cubic B-spline with one interior knot at . Now the curve is made of two cubic pieces joined smoothly, and each piece only listens to the control points near it.
Local control
The practical reason designers use B-splines is that in a Bézier curve every control point affects the whole curve, because every Bernstein polynomial is nonzero across the entire interval. A B-spline only responds to the control points whose B-splines are nonzero on that spline.
Moving one control point. Left, a degree-6 Bézier curve; right, a cubic B-spline with four spans. The dashed curve is the result of moving upward.
In Figure 5, both curves have the same seven control points. The blue curve shows the result from the gray control points and the red dashed curve is after moving straight up. On the Bézier curve, 98.8% of the sampled points moved. On the cubic B-spline with interior knots at , and , only 49.8% did; the right half of the curve didn’t notice. Designing a car body or a font with hundreds of control points would be much more difficult if every adjustment affected the whole shape.
B-splines reduce errors
A representation is only useful if a computer can work with it without rounding errors running away. The usual measure is the condition number, which says how much small errors in the coefficients can change the shape of the curve. A large condition number means the effect is large. For a basis, the condition number compares the size of the coefficients with the size of the function they produce. If it’s bounded, small changes in one always mean small changes in the other.
With George Fix, de Boor found a formula that gives the B-spline coefficients of any spline directly, now called the de Boor–Fix formula. He used it to prove that the B-spline basis has a condition number bounded independently of where the knots are. DeVore and Ron call this perhaps the most counterintuitive property of splines. You might expect knots crowded into one corner to make the problem ill-conditioned, but the bound doesn’t depend on how unevenly the knots are spaced, only on the degree.
In the mid-1970s de Boor made a related conjecture. When you approximate a function by a spline using least squares, you are projecting it onto the space of splines with a given set of knots. He conjectured that the size of that projection, measured in the maximum norm, has a bound that again doesn’t depend on the knot sequence. Alexei Shadrin eventually proved it, and DeVore and Ron’s 2005 tribute reports the result as settled.
Beyond one dimension
Curves are one-dimensional, but surfaces aren’t, and the obvious way to build a spline surface (multiply a spline in by a spline in ) only works well on rectangular grids. In 1976 de Boor noticed that an old geometric picture of the B-spline due to Curry and Schoenberg could be turned into a definition in any number of dimensions.
Picture a simplex (a triangle, tetrahedron, or its higher-dimensional cousin), mapped linearly down onto a line, and measure how much of the simplex lands on each point. The resulting cross-sectional volume, as a function of the point, is a B-spline. Replace the line with a plane or with space, and you get a multivariate B-spline.
Those simplicial B-splines turned out to be awkward to compute with, and the more successful idea was to start from a cube instead of a simplex. Box splines first appeared in a 1983 paper by de Boor and Ronald DeVore, and de Boor developed much of the early theory with his Wisconsin colleague Klaus Höllig (W. Dahmen and C. A. Micchelli worked out much of it in parallel). The Loop scheme, which DeVore and Ron describe as the most commonly used surface subdivision algorithm, is based on box splines.
The connection that suits a puzzle article best came from one of de Boor’s students. Rong-Qing Jia used box-spline theory in the late 1980s to settle a conjecture of Richard Stanley about the number of solutions of the symmetric magic square problem. Splines used for designing car bodies ended up counting magic squares, which are close cousins of the Latin squares basis for every Sudoku.
Later work with Amos Ron took the ideas further. They studied which polynomial spaces make multivariate interpolation solvable for any finite set of points, and, in the early 1990s, laid the foundations of shift-invariant spaces: function spaces generated by sliding one or a few generating functions along the integer lattice. That theory connects directly to the construction of wavelets.
Back to the puzzle board
Elimination as a rule
A Sudoku is a grid in which each digit appears once in every row, every column and every box. Seen that way it is a Latin square with extra constraints. The digits a cell can never share are those in its peers, the cells that share its row, column or box. Every cell has the same number of peers,
eight others in its row, eight others in its column, and four more in its box that aren’t already in that row or column.
One cell (red) and its 20 peers (yellow).
sudokon’s rule, and Pseudo-Ku’s, is that placing a digit removes it from the candidates of all 20 peers. That’s all the board does on its own. If you right-click a small digit you remove that one candidate yourself; nothing else happens automatically, and the board never places a digit for you, even when a cell has only one candidate left. Inside the program each cell’s candidates are a 9-bit number, one bit per digit. Placing a 5 clears bit 5 in twenty numbers, which is about as cheap as an operation can get.
When I tried it on the 13 puzzles that come with sudokon, elimination alone solved one of them. Adding hidden singles (if a digit has only one possible cell left in some row, column or box, it must go there) brought the count to three. The other ten need the player to reason, which is the point of the game.
| Rule applied automatically | Puzzles fully solved (of 13) |
|---|---|
| Elimination only | 1 |
| Elimination and hidden singles | 3 |
A proof that elimination never cheats
If the board always crosses off a placed digit from its peers, and only lets you place a digit that is still a candidate, then it should be impossible to end up with the same digit twice in a row, column or box. Here is a proof in Lean 4, using only Lean’s core library.
The model keeps two things for each cell: a candidate flag for every digit, and an optional placed value. peer a c says cells a and c share a unit, and the proof only assumes that the peer relation is symmetric and that no cell is its own peer, so the same proof covers Sudoku and the KenKen boards below.
set_option linter.unusedSectionVars false
structure Board (Cell : Type) where
cand : Cell → Nat → Bool
value : Cell → Option Nat
variable {Cell : Type} [DecidableEq Cell]
variable (peer : Cell → Cell → Prop) [DecidableRel peer]
/-- The start of a game: every digit is a candidate everywhere, nothing placed. -/
def start : Board Cell where
cand := fun _ _ => true
value := fun _ => none
/-- Place `d` in cell `a`: the cell keeps only `d`, and every peer loses `d`. -/
def place (b : Board Cell) (a : Cell) (d : Nat) : Board Cell where
cand := fun c e =>
if c = a then e == d
else if peer a c ∧ e = d then false
else b.cand c e
value := fun c => if c = a then some d else b.value c
/-- Eliminate candidate `d` from cell `a` only. -/
def eliminate (b : Board Cell) (a : Cell) (d : Nat) : Board Cell where
cand := fun c e => if c = a ∧ e = d then false else b.cand c e
value := b.value
/-- Boards reachable from the start by legal moves. A placement is legal only
when the digit is still a candidate, which is the rule the game enforces. -/
inductive Reachable : Board Cell → Prop
| start : Reachable start
| place {b a d} : Reachable b → b.cand a d = true → Reachable (place peer b a d)
| elim {b a d} : Reachable b → Reachable (eliminate b a d)
/-- The invariant: a placed digit is neither a candidate in, nor placed in,
any peer cell. -/
def Safe (b : Board Cell) : Prop :=
∀ a c d, peer a c → b.value a = some d →
b.cand c d = false ∧ b.value c ≠ some d
theorem safe_start : Safe peer (start : Board Cell) := by
intro a c d _ h
simp [start] at h
theorem safe_eliminate (b : Board Cell) (a : Cell) (d : Nat)
(hs : Safe peer b) : Safe peer (eliminate b a d) := by
intro x c e hxc hx
have ⟨h1, h2⟩ := hs x c e hxc hx
refine ⟨?_, h2⟩
simp only [eliminate]
split <;> simp_all
theorem safe_place (b : Board Cell) (a : Cell) (d : Nat)
(symm : ∀ x y, peer x y → peer y x) (irrefl : ∀ x, ¬ peer x x)
(hs : Safe peer b) (hcand : b.cand a d = true) :
Safe peer (place peer b a d) := by
intro x c e hxc hx
simp only [place] at hx ⊢
by_cases hxa : x = a
· -- the new placement: x = a, so e = d
subst hxa
simp at hx
subst hx
have hca : c ≠ x := fun h => irrefl x (h ▸ hxc)
refine ⟨?_, ?_⟩
· simp [hca, hxc]
· simp only [hca, if_false]
intro hv
have := (hs c x d (symm x c hxc) hv).1
simp_all
· -- an older placement at x with digit e
simp only [hxa, if_false] at hx
have ⟨h1, h2⟩ := hs x c e hxc hx
by_cases hca : c = a
· subst hca
have hed : e ≠ d := by
intro h
subst h
simp_all
simp [hed, Ne.symm hed]
· refine ⟨?_, ?_⟩
· simp only [hca, if_false]
split <;> simp_all
· simp [hca, h2]
/-- Every reachable board is safe. -/
theorem reachable_safe
(symm : ∀ x y, peer x y → peer y x) (irrefl : ∀ x, ¬ peer x x)
{b : Board Cell} (h : Reachable peer b) : Safe peer b := by
induction h with
| start => exact safe_start peer
| place _ hc ih => exact safe_place peer _ _ _ symm irrefl ih hc
| elim _ ih => exact safe_eliminate peer _ _ _ ih
/-- Legal play never puts the same digit in two cells that share a row,
column or box. -/
theorem no_duplicates
(symm : ∀ x y, peer x y → peer y x) (irrefl : ∀ x, ¬ peer x x)
{b : Board Cell} (h : Reachable peer b)
{a c : Cell} {d : Nat} (hp : peer a c) (ha : b.value a = some d) :
b.value c ≠ some d :=
(reachable_safe peer symm irrefl h a c d hp ha).2
The idea is an invariant, a property that is true at the start and that every legal move preserves. Here it’s Safe: whenever a digit is placed, it is no longer a candidate in any peer, and no peer holds it. At the start nothing is placed, so Safe holds trivially.
Eliminating a candidate only removes possibilities, so it can’t break Safe. Placing in cell is the interesting case. The new placement is safe because the move itself crosses off every peer, and because was still a candidate in , Safe tells us no peer of already held a . An older placement of at some cell also stays safe.
Placing only ever removes candidates from other cells, and if is a peer of , then can’t equal , because Safe had already removed from the candidates of . Induction over the moves completes the proof, and no_duplicates is the desired statement.
Undo doesn’t need its own case. It returns the board to an earlier position, and every earlier position was reachable. I compiled this with Lean 4.19.0. #print axioms no_duplicates reports only propext and Quot.sound, Lean’s two standard axioms, so the proof contains no unfinished sorry steps.
You can test this proof in JuliaLab.
How many Sudokus are there?
Bertram Felgenhauer and Frazer Jarvis counted the completed Sudoku grids in 2005:
Many of those are the same grid in different forms, though. You can swap the three horizontal bands of boxes, swap rows inside a band, do the same with columns, and transpose the grid, and it’s still a valid Sudoku. Those moves give
symmetries, which is the group Ed Russell and Jarvis used, together with relabeling the digits and Burnside’s lemma, to show that only 5,472,730,538 grids are essentially different. sudokon has a permute button that applies these same moves plus a relabeling of the digits, so one puzzle can be dressed up in at most ways.
KenKen
KenKen works on an grid, usually between and . Each row and column contains the digits to once, but there are no boxes. Instead, the grid is divided into cages, each with a target and an operation: “12×” means the digits in that cage multiply to 12, “1−” means two cells differ by 1, and so on. A cage with a single cell just tells you its digit.
The elimination rule carries over unchanged, with peers now meaning row and column only, but the arithmetic is new. Back in Put Another KenKen on the Barbie I wrote two PARI/GP functions, sumPart and multPart, that list the digit combinations a cage might hold. For example, sumPart(16,3,1,[3,7]) asks for three different digits adding to 16 without using 3 or 7, and returns , and .
Pseudo-Ku handles a lot of the problems that the player needed to keep track of when using the PARI/GP code. Pseudo-Ku says either “all the digits in this cage are different” or “repeats are allowed.” The real rule is about pairs of cells because two cells in a cage may hold the same digit only if they are in different rows and different columns:
A square cage shows the difference. Each cell shares a row or column with two of the others and sits diagonally from the third, so a digit can appear at most twice, on a diagonal. With the target “72×” on a board, multPart(72,4,0) would include . Three 2s can’t fit, because two of them would have to share a row or column. Enumerating the digits cell by cell with the pair rule gives exactly seven lists:
A “72×” cage. Repeated digits must sit on a diagonal, so 1·3·3·8 fits and 2·2·2·9 can’t.
In Pseudo-Ku, clicking a cage’s rule opens a small panel with those lists. The panel uses the current state of the board, so a digit you’ve crossed off drops out of the lists, and it updates as you play. It never changes the board, and it only appears when you ask. In the 2020 post I quoted Shigeru Miyamoto’s idea of teaching without teaching, and an optional hint seemed like the closest a puzzle board can get to that.
One difference from Sudoku matters when you finish. Because the board enforces rows and columns but not cage arithmetic, you can fill a KenKen grid completely and still be wrong. When the last cell is filled, Pseudo-Ku checks every cage and names any that don’t add up.
Playing Pseudo-Ku
Open the Pseudo-Ku page and choose New game, then Sudoku or KenKen and, for KenKen, a size from 3 to 9.
- Left-click a small digit to place it. Right-click a small digit to cross it off that cell.
- Undo, or Ctrl+Z, takes back one move at a time. A cell with no digits left means a mistake somewhere earlier.
- When all nine copies of a digit are placed in Sudoku (or all in KenKen), they turn blue.
- For KenKen, click cells to select a cage (turns yellow), type its rule (
12x,2/,1-,8+, or a single number) and press Enter. Click a cage to change or delete it, and press Start when every cell is in a cage. - During KenKen play, click on any rule (e.g. 6+) to see the possible remaining solutions for that cage.
The Pseudo-Ku board.
The board is sized for a desktop browser. On a phone the candidate digits are too small to tap reliably.
How it was built
The original version was a Python engine with a test suite. The browser version is a TypeScript port with a React front end. To keep the two from drifting apart, a script plays 505 recorded games through the Python engine, including Sudoku games, Latin-square games, cage-help queries and deliberately illegal moves, and the TypeScript tests replay every one of them and require the same board after all 4,892 steps. Doubt is the beginning of science, and it’s a decent starting point for software too.
Conclusion
sudokon is a small program, but it led back to a large body of mathematics. The B-spline recursion builds smooth curves out of boxes, it contains the Bézier curves we fitted to a shark fin as a special case, and it gives designers local control without giving up numerical stability.
De Boor carried those ideas into higher dimensions with box splines, which ended up inside graphics software and, through his student Rong-Qing Jia, inside a counting problem about magic squares. On the puzzle side, the elimination rule is simple enough to prove correct in a page of Lean.
Software
Software
- Python - Python is an interpreted, high-level and general-purpose programming language.
- Lean Theorem Prover - Lean is a functional programming language that makes it easy to write correct and maintainable code. You can also use Lean as an interactive theorem prover.
- Pari/GP - PARI/GP is a widely used computer algebra system designed for fast computations in number theory (factorizations, algebraic number theory, elliptic curves, modular forms, L functions…), but also contains a large number of other useful functions to compute with mathematical entities such as matrices, polynomials, power series, algebraic numbers etc., and a lot of transcendental functions.
- React - React is the library for web and native user interfaces, and lets you build user interfaces out of individual pieces called components.
References
- C. de Boor, home page, University of Wisconsin–Madison, including the link to
sudokon. - C. de Boor,
sudokon, MATLAB Central File Exchange #9852. - R. DeVore and A. Ron, Developing a Computation-Friendly Mathematical Foundation for Spline Functions, SIAM News 38(4), May 2005. Note: The SIAM link is broken, but still appears on DeVore’s Texas A&M website.
- C. de Boor, A Practical Guide to Splines, 1978; revised edition 2001.
- C. de Boor, K. Höllig and S. Riemenschneider, Box Splines.
- S. D. Conte and C. de Boor, Elementary Numerical Analysis: An Algorithmic Approach, 3rd edition, reprinted in SIAM Classics in Applied Mathematics.
- C.-K. Shene, B-spline Basis Functions: Definition, Michigan Technological University course notes.
- B. Felgenhauer and F. Jarvis, Enumerating possible Sudoku grids, 2005.
- E. Russell and F. Jarvis, the count of essentially different grids (2006), as summarized in The Math Behind Sudoku: Symmetry, Cornell University.
- J. Peach, Put Another KenKen on the Barbie, Wild Peaches, 2020.
- J. Peach, Bézier polynomial curve regression, Wild Peaches, 2026.
- J. Peach, JuliaLab, Wild Peaches, 2026.
- C. Moler, Solving Sudoku with MATLAB, MathWorks technical article, 2009.
Image credits
- Hero: B-splines abstract art, Nano Banana, Buyer’s guide: Citroën 2CV.
sudokon, MATLAB Central File Exchange #9852- Carl de Boor: Wikipedia.