## Sudoku Variants

I’m finally starting to think about sudoku, and am having a lot of fun with it.

I’m taking an online class on artificial intelligence with udacity, and sudoku is being used to illustrate some ideas used to solve constraint satisfaction problems.

Naturally, before solving sudoku puzzles by using the algorithms described in the online course, I thought about what I could do with a brute force approach, which naturally led me to think about variants of sudoku where brute force is a feasible approach. And that’s what I’ll write about here.

But first, let’s recap the basics. To begin with, what is sudoku?

## Girard’s Theorem

Here’s one of my favorite theorems from geometry, both because of the result itself, and because of the proof I’ll describe in this blog post. I suspect it was much better known when spherical trigonometry used to be part of the standard curriculum, but that was before my time. Now it seems to be forgotten, and if it’s mentioned at all it’s in a differential geometry course as an elementary consequence of the more general and powerful Gauss-Bonnet theorem.

One of the very old and well known results about triangles is that the sum of the angles is equal to $\pi$ (or $180^o$ if you measure angles in degrees instead of radians, which is almost never done in modern mathematics). Girard’s theorem can be viewed as the analogous result in the context of spherical geometry, where the analogue of line segments in the plane is great circle arcs on the sphere.

Girard’s Theorem For a spherical triangle on a unit sphere (i.e. radius equal to one) with interior angles $A,B,C$ the quantity $A+B+C-\pi$ is equal to the area of the triangle.

The way this is proved nowadays (which is not the proof I’ll discuss later in this post) is by first proving the Gauss-Bonnet theorem. To do that you need to work in the more general context of Riemannian geometry where lines in a plane generalize to geodesics in a surface (or an $n$ dimensional Riemannian manifold if you really want to generalize). And then you need to introduce the concept of curvature.

Once you’ve done all that, you can finally state and prove the Gauss-Bonnet theorem, which says that the quantity $A+B+C-\pi$ (where the curves that make up a triangle are geodesics) is equal to the integral of the curvature over the surface of the triangle. For a unit sphere the curvature is one, and for the plane the curvature is zero, and so the Gauss-Bonnet theorem can be used to prove both results mentioned above.

Just as there’s a much more direct and elementary proof of the result for planar triangles, there’s a much more direct and elementary proof of the result for spherical triangles, and that’s what I’ll write about in this post.

To warm up for the proof, I’d like to discuss the solution to a seemingly unrelated combinatorial problem. It turns out to be very closely related, since an approach to solving it is exactly the same as an approach to proving Girard’s theorem.

Problem Consider all words consisting of three characters $a, b,c$ How many words of length three are there where all three characters occur? Continue reading “Girard’s Theorem”