Sudoku and the Turkey Bird
November 29, 2009
I was asked to teach a class on algorithms. This was a regular part of
the Tufts undergraduate ciriculum and it had a set book and language:
C++. I was not a happy camper.
It's damn hard to write any program in C++ and it's especially
difficult for younger programmers who only have half an idea of how a
computer works in the first place. The book didn't make things any
easier. The authors seemed to think that it was important for students
to learn every feature of the language at the same time.
Moreover, they were quite fond of the STL (Standard Template Library)
for C++. The STL is an excellent example of how NOT to write a
library. It supplies a complex interface to an unorganized set of
classes and adds no protection against simple mistakes.
The STL Vector class is basically an ArrayList (that doesn't check for
out of bounds errors) and a List is a LinkedList. They are not
related. If you are using a List and realize that a Vector would be a
better choice, you have to rewrite your entire program.
By contrast, Java, Python, and many of the newer languages do it
right: Both LinkedList and ArrayList are implementations of List, so
all you have to do is change the constructor and everything will
continue to work, only faster. (If it isn't faster, then don't make
Programmers need protection.
Undergraduate programmers need a lot of protection.
If you don't give them that protection, then they'll waste a lot of
time trying to track down stupid bugs and get bored with computer
science and leave.
So our first project was a Java-like List hierarchy, with out of
bounds protection. And then maps and hash tables and trees, all with
simple, safe interfaces. We basically rewrote the Java Collections
And it worked.
Usually most students don't manage to finish all the assignments
because they get lost in a mass of compilation errors and runtime
exceptions. My students did.
By Thanksgiving, the class was ready for something bigger. They were
ready for dealing with abstract datatypes in the real world.
At this time, Sudoku had recently taken off in the Boston newspapers
and folks were solving puzzles everywhere. Now what could be more real
world than Sudoku?!
I wrote up a Sudoku solver in Java, refined it, and translated it to
C++. (I could not have written it in C++ from scratch, certainly not
that quickly.) I was able to separate the basic data structures from
the logic of the solver cleanly, and then introduce the students to
the basic structures independently.
Now my idea of a good time is to hang out at Thanksgiving with my
brother on his ranch in Utah, take the horses up the mountain
(sneaking around the security guards*), cook some coffee over a fire
and dream about data structures. This particular year, I arrived to
find a 55 gallon drum heating water in the driveway and a monsterous
turkey looking on.
Sandy had decided to raise the turkey himself and he fed it a little
too well. He couldn't find anything smaller to de-feather it in than
the drum. We had to remove the drumsticks just to get it in the
oven. And we ate around midnight.
So this is what my assignment to my students was. I introduced them to
the basic ideas of Sudoku and what the useful ADTs were (there's the
individual cell, then three versions of sets of nine cells--boxes,
rows, and columns, but NO two dimentional arrays!). Then I told them
to go enjoy the vacation and day dream about their soon-to-be glorious
And they came back and built the structures under my watchful eye,
then built their own solvers (not under my watchful eye) and succeeded!
Not only did they learn about the realities of programming with ADTs,
they left the class with something cool that they could show to their
It's hard to get English majors excited about writing an N log(N) sort
routine, but a Sudoku solver! That's something one can brag about.
* Actually, there's not much they can do even if they do see
you. Pickup trucks are not very good over rough terrain and horses
can go anywhere. They'd shake their fists at us and we'd smile and