Sudoku and Doing Your Best Work

A lot of our lives, both our working lives and our personal lives, are spent doing repetitive, uncreative tasks. Many of these tasks are enjoyable: they include hobbies like gardening or baking that we enjoy for hard-to-articulate reasons. But, they also include things we don’t want to do, like laundry or washing the dishes.

While we cannot simply program a robot to do the tasks listed above, there are a lot of repetitive tasks, especially ones that don’t involve manipulating physical objects, for which we can. For example, scientific software packages like Wolfram Alpha can solve most differential equations automatically, so that humans no longer have to solve them by hand.

Given that these software packages exist, we would find it odd if a mathematician measured his own quality based on his ability to solve differential equations by hand quickly, since a computer could solve them much faster. This would make sense only if he had spent his time deep within the math department and hadn’t ventured out to learn about computer science — he simply might not see that differential equations could be solved by a computer, and therefore might see solving them manually as a productive use of time.

This is exactly what occurs when people solve Sudoku puzzles. Sudoku is a fundamentally repetitive task that can be solved according to simple rules with a computer program. The fact that Sudoku is still one of the most popular puzzle games in the world, and that most of the people that do it don’t see that it is a task that could be described with an algorithm, says a lot about how easy it is to confuse activity with productivity, and should serve as a wake up for all of us to examine what aspects of our work simply involve conditioning ourselves to follow a set of well-specified rules with increasing efficiency — in other words, doing the equivalent of “getting good at solving Sudoku” — when instead we should be learning how to do the equivalent of getting a computer to handle the job.

Why I’ve been thinking about this

Over the past couple of months, I have been working through the projects in the very well-designed Udacity Artificial Intelligence Nanodegree, which teaches classic Artificial Intelligence techniques via having you apply them to real problems and learn the algorithms by coding them yourself.

The first problem is to write an algorithm that solves Sudoku puzzles. Given that the “classical AI” bent of this Nanodegree, the solution is not simply to build a neural net that sees a bunch of positive and negative examples and iteratively learns how to solve the puzzles by adjusting its weights, and/or to use a reinforcement learning algorithm which penalizes an agent for placing a number in a place that breaks the rules and rewards it when it correctly solves puzzles. No, Sudoku is simple enough that we can “teach” a computer how to play Sudoku by telling it explicitly what to do given the numbers that it sees on the board. This was a fun exercise—I found figuring out how you would tell a computer to solve Sudoku much more rewarding than solving them myself.

Below is an outline of the solution. I’ll note that this solution and the Udacity solution closely follow Peter Norvig’s classic essay Solving Every Sudoku Puzzle.

How to Solve Every Sudoku

Start by defining a data structure to keep track of which numbers are already on the board. This data structure should also keep track of all the “candidate” numbers for the empty cells — that is, numbers that could possibly go in those cells.

Then, follow a few steps over and over again to solve the puzzle, until it is solved:

  • Step 1: “Elimination”. Use the rules of Sudoku to eliminate numbers as candidates from empty cells. For example, if a 9 is in a particular row, use this rule to eliminate 9 as a candidate from the other cells in that row.
  • Once we only have one number left in a cell, continue the “elimination” strategy and eliminate that number from the other cells on the board. As I learned, this is known in classical AI as “Constraint Propogation”.
  • If necessary, employ advanced techniques for “eliminating” numbers, such as the “Naked Twins” technique depicted below:
An illustration of the Naked Twins strategy. Credit Ronald Eddings

Humans can in theory do all of this. However, what if they hit a roadblock — there are no more numbers that can easily be eliminated from cells. What then?

Computers can solve this easily — and not just by trying all possible board combinations until they find one that works. They can simply do the following: let’s say there are two cells, Cell 1 and Cell 2, and given all the information we have about the board, we know that either Cell 1 contains a 5 and Cell 2 contains a 6, or vice versa. But, we have no information that would tell us which is which. Here, a human is stuck, but a computer can simply try out the first possibility, putting a 5 in Cell 1 and a 6 in Cell 2, and then attempt to continue going through the entire board until the puzzle is either solved or until it finds a cell where there are no possible values left — if this happens, it knows that its original choice at the “fork in the road” was wrong, and that the 6 should have gone in Cell 1 and the 5 in Cell 2. This can be implemented using a classic algorithm called “depth-first search”.

Indeed, the final step of the project was to have our program solve a Sudoku that both required search to solve as well as having the additional constraint that the numbers 1–9 could not repeat on each main diagonal in addition to the rows, columns, and nine “sub-blocks”:

A diagonal Sudoku that would be extremely difficult for a human to solve. Go ahead, try it.

(Humans could in theory do this too, but it would involve a lot of erasing, and erasing is messy.)

So, Sudoku can be completely described with an algorithm — (the code from my GitHub that solves the puzzles is contained here). It is remarkable, then, that people do them at all! After all, people solve them by keeping track of information in various ways and employing similar — usually less sophisticated — strategies to the ones above.

As a brief aside: many “puzzle” games thought of as similar to Sudoku are algorithmic in nature, but not all. For example, word search puzzles are algorithmic: you could easily program a computer to search for a specific set of words in a grid of letters. By contrast, crossword puzzles are creative, requiring not only awareness of the subtleties of natural language but also of the social and cultural context in which the puzzle was written.

Doing Your Best Work

I have written previously about how a lot of white collar work — even work that “feels productive” — is fundamentally organizational in nature. Some of this work, such as writing emails with status updates, is non-repetitive and, in large organizations especially, is useful and requires skill. But much of it, like many spreadsheet-based analyses that take place in consulting or finance, are just repetitive.

Moreover, much of this white collar work will eventually be displaced — it’s not that the jobs will disappear entirely, but there will be tools built that, for example, do a lot of the manual analysis done in Excel in a much less manual fashion, so that we’ll need fewer people to get the same amount of work done. This is of course a great thing for society as a whole — but it is an unfortuate thing from the perspective of the people currently working in an struggling to excel in these jobs. And I think the root of the problem is that most people in these jobs don’t see what they are doing as fundamentally algorithmic — that they are the equivalent of doing Sudoku over and over again, when someone could come along and simply write a program that does Sudoku for you.

The problem.

So, I think it is actually a problem that people view Sudoku and things like it as enjoyable activities. Confusing mental stimulation with things that actually require critical thinking, creativity, and reflection can not only lead to bad time management by confusing busy-ness and productivity, it can also lead to bad career choices by making you seek out jobs where you “feel” like you are “doing a lot of work”, rather than focusing on finding ones where you’re “adding a lot of value”.

The straightforward lesson here is: if you’re in a job where you’re doing this kind of repetitive work: get out (and if you want to get into Data Science, taking an immersive program from Metis can be a great way to do it) — “the robots” — or at least the people who know how to teach (i.e. program) them — are coming for you. The first step, however, is to realize that doing the equivalent of “doing Sudoku over and over again”, while it may keep you busy, isn’t actually productive.

More generally: don’t just stop doing Sudoku. Always look for ways to automate the repetitive, organizational tasks at work and in your life. Do this, and use the time you save to cultivate your creative, innovative, more human side — the side you will ultimately need to do your most valuable and most rewarding work.