The Pseudo-Ku KenKen board in a browser, with cage outlines, rule labels, small candidate digits and a cage help panel listing digit combinations.

From B-splines to Sudoku and KenKen

The Mathematics of Carl de Boor

October 24, 2026 · John Peach

Ask Gemini Notebook

Play Pseudo-Ku


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.

Figure 1.

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

Figure 2.

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 t0≤t1≤t2≤⋯t_0 \le t_1 \le t_2 \le \cdots. The B-splines of degree 00 are the simplest functions there are: Bi,0B_{i,0} is 11 on the interval between knot tit_i and knot ti+1t_{i+1}, and 00 everywhere else,

Bi,0(x)={1,ti≤x<ti+1,0,otherwise.B_{i,0}(x) = \begin{cases} 1, & t_i \le x < t_{i+1}, \\ 0, & \text{otherwise.} \end{cases}

Every higher degree is built from the one below it,

Bi,k(x)=x−titi+k−ti Bi,k−1(x)+ti+k+1−xti+k+1−ti+1 Bi+1,k−1(x).B_{i,k}(x) = \frac{x - t_i}{t_{i+k} - t_i}\, B_{i,k-1}(x) + \frac{t_{i+k+1} - x}{t_{i+k+1} - t_{i+1}}\, B_{i+1,k-1}(x).

Here kk is the degree, ii counts which B-spline we mean, and xx 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-kk B-spline, take two adjacent B-splines of degree k−1k-1 and mix them. The first weight, (x−ti)/(ti+k−ti)(x - t_i)/(t_{i+k} - t_i), climbs from 00 to 11 as xx crosses the interval, and the second weight falls from 11 to 00 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.

Four stacked panels showing B-spline basis functions on knots 0 through 8: degree 0 as boxes, degree 1 as triangles, degree 2 as rounded humps, and degree 3 as smooth bells, each spanning one more knot interval than the degree below.
Figure 3.

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:

A spline curve is a weighted sum of B-splines, with control points PiP_i as the weights,

C(x)=∑iPi Bi,k(x).C(x) = \sum_i P_i\, B_{i,k}(x).

Because the B-splines are non-negative and add up to 11, 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-nn B-spline and put all the knots at the two ends: n+1n+1 copies of 00 followed by n+1n+1 copies of 11. With no knots in between, there is only one polynomial piece, and the recursion produces exactly the Bernstein polynomials,

Bi,n(x)=(ni)(1−x)n−ixi,B_{i,n}(x) = \binom{n}{i}(1-x)^{n-i}x^i,

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 five shark-fin control points with three curves: the degree-4 Bézier curve, an identical degree-4 B-spline with clamped knots drawn on top of it, and a different degree-3 B-spline with one interior knot at one half.
Figure 4.

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 4.4×10−164.4 \times 10^{-16}, 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 x=12x = \tfrac{1}{2}. 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.

Two panels with the same seven control points. On the left, moving the second control point upward changes a degree-6 Bézier curve almost everywhere. On the right, the same move changes a cubic B-spline only on its left half.
Figure 5.

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 P1P_1 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 P1P_1 straight up. On the Bézier curve, 98.8% of the sampled points moved. On the cubic B-spline with interior knots at 14\tfrac14, 12\tfrac12 and 34\tfrac34, 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 xx by a spline in yy) 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 9×99 \times 9 grid in which each digit appears once in every row, every column and every 3×33 \times 3 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,

8+8+4=20,8 + 8 + 4 = 20,

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.

A 9 by 9 Sudoku grid with one cell shaded red and the twenty cells in its row, column and 3 by 3 box shaded yellow.
Figure 6.

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 automaticallyPuzzles fully solved (of 13)
Elimination only1
Elimination and hidden singles3

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 dd in cell aa is the interesting case. The new placement is safe because the move itself crosses dd off every peer, and because dd was still a candidate in aa, Safe tells us no peer of aa already held a dd. An older placement of ee at some cell xx also stays safe.

Placing only ever removes candidates from other cells, and if xx is a peer of aa, then ee can’t equal dd, because Safe had already removed ee from the candidates of aa. 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:

6,670,903,752,021,072,936,960≈6.67×1021.6{,}670{,}903{,}752{,}021{,}072{,}936{,}960 \approx 6.67 \times 10^{21}.

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

(3!)4⋅(3!)4⋅2=12962⋅2=3,359,232(3!)^4 \cdot (3!)^4 \cdot 2 = 1296^2 \cdot 2 = 3{,}359{,}232

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 3,359,232×9!≈1.22×10123{,}359{,}232 \times 9! \approx 1.22 \times 10^{12} ways.

KenKen

KenKen works on an n×nn \times n grid, usually between 3×33 \times 3 and 9×99 \times 9. Each row and column contains the digits 11 to nn 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 {1,6,9}\{1,6,9\}, {2,5,9}\{2,5,9\} and {2,6,8}\{2,6,8\}.

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:

row(i)=row(j)  or  col(i)=col(j)  ⟹  di≠dj.\text{row}(i) = \text{row}(j)\ \text{ or }\ \text{col}(i) = \text{col}(j) \;\Longrightarrow\; d_i \ne d_j .

A 2×22 \times 2 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 9×99 \times 9 board, multPart(72,4,0) would include (2,2,2,9)(2,2,2,9). 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:

(1,1,8,9), (1,2,4,9), (1,2,6,6), (1,3,3,8), (1,3,4,6), (2,2,3,6), (2,3,3,4).(1,1,8,9),\ (1,2,4,9),\ (1,2,6,6),\ (1,3,3,8),\ (1,3,4,6),\ (2,2,3,6),\ (2,3,3,4).
Two 2 by 2 cages labeled 72 times. The left one holds 1, 3, 3, 8 with the two 3s on a diagonal. The right one tries 2, 2, 2, 9, which forces two 2s into the same row or column.
Figure 7.

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.

Figure 8.

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

References

Image credits