Edit: based on suggestions from readers, the best solution is down to 162 characters! Read to the end to see how

A highlight of PyCon each year for me is working on the little coding challenges offered by companies in the expo center. I love testing my Python prowess against the problems they pose (and being rewarded with a branded mug or T-shirt!) This year, several of the challenges involved what's become known as code golf: writing a solution with minimal keystrokes.

By way of example, take a look at this function definition:

This is a valid function definition (in Python 2.7) which executes a particular task. I'll give more information on the workings of this script later on, but for now I'll leave it to the reader to ponder over what it might do.

Given the level of obfuscation involved, you might wonder what the point is: you'd never want to write "real" code in this style, so why spend the time doing it? I'd argue that it's useful for more than just upping your geek cred: good Python code golf must utilize many quirks of the Python language in seeking brevity above all else. Learning to utilize these quirks can lead to a much deeper understanding of the Python language.

I thought about putting together a list of tricks that can help lead to short programs, but the problem is there are so many of them (and there are other pages out there which do this adequately enough). Instead, I decided to simply work through a step-by-step example of creating a code golf solution to a fun little problem: solving Sudoku.

You've probably seen Sudoku: it's a puzzle consisting of a 9x9 grid of numbers, with some spaces left blank. The grid must be filled so that each row, column, and 3x3 box contains the numbers 1-9. It's a generalization of the Latin Squares first studied by Leonhard Euler nearly 300 years ago.

The reason I chose to use Sudoku here is simple: not only is today Euler's birthday, but Sudoku is how I first learned Python. My first year of graduate school, my research advisor recommended that I learn Python for the project I was working on. Sudoku had just become popular in the US at the time, and I decided to learn Python by writing a Sudoku solver. I did it over my winter break, and the rest (so it's said) is history.

Note that this is by no means a new subject: you can read about Sudoku in Python in several places, and there are even a few code golf solutions floating around out there. In particular, you should take a look at this solution, which is the shortest solver I've seen, and from which I borrowed a few of the tricks used below.

Here we'll pose the problem in a slightly different way, which will give us the chance to develop a brand new short algorithm.

The Problem¶

Every code golf challenge must start with a well-defined problem. Here is ours:

• Write a function S(p) which, given a valid Sudoku puzzle, returns an iterator over all solutions of the puzzle.

The puzzle will be in the form of a length-81 string of digits, with '0' denoting an empty grid space. The solved puzzles should also be length-81 strings, with the zeros replaced by solved values.

For example, a valid S(p) may produce the following results:

puz="027800061000030008910005420500016030000970200070000096700000080006027000030480007"
for s in S(puz):
    print(s)

327894561645132978918765423589216734463978215172543896794651382856327149231489657
327894561645132978918765423589216734463978215271543896794651382856327149132489657
327894561465132978918765423589216734643978215172543896794651382856327149231489657
327894561465132978918765423589216734643978215271543896794651382856327149132489657

puz = 81*'0'  # empty puzzle
print(next(S(puz)))

132598476598476132476132985319825764825764319764913258981257643647389521253641897

Notice that the function S() cannot simply return a list of valid solutions: if it did, then the empty puzzle example would need to produce all ~\(10^{22}\) valid sudoku grids before the first solution could be accessed! Instead, it must make use of Python's extremely useful generator syntax. If you've never used generators and generator expressions in your Python code, stop reading this right now and go learn about them: they're one of the most unique and powerful features of the Python language.

As you'll see below, my best solution is 176 162 characters, and is the code snippet I showed above:

It's rather unenlightening in itself, so below I'll explain the steps I took to arrive at it, in hopes that you can learn from my thought process. Though this is the best solution I was able to come up with, I don't know whether or not a better one might be out there. If you can beat it, please post your solution in the blog comment thread!

Step 1: Focus on Correct Code¶

A code golf script must be more than simply short: it must be correct. For this reason, I generally start by simply writing correct code, and not for the moment worrying about brevity.

In the case of Sudoku, there are many rules and rubriks that can be used to create an efficient solver (read about some of them here). Using these, it is possible to solve most (all?) Sudoku puzzles without resorting to guess-and-check approaches. To implement this strategy, one approach might be to enumerate the sets of possible values for each grid space, and apply these rules to eliminate values until only a single possibility remains within each space.

Unfortunately, this is not a very suitable approach for code golf: the number of rules required to accomplish this is very large. Instead, we'll make use of the minimal amount of rules, and write a guess-and-check based solver.

Here's a first attempt, focusing on the algorithm rather than on brevity. We'll start by defining a test puzzle with four solutions, and write a small function that can test our solver:

This is the test output we expect: it quickly finds not only the four solutions of the test puzzle, but a solution derived from a completely empty puzzle. This is by no means a complete test suite, but it gives us good reason to believe that the code is correct.

Step 2: Simplify the Algorithm¶

For me, the biggest hurdle to writing concise programs was letting go of the compulsion to write clear and efficient code. In my research, the two most important aspects of code are its scalability and its readibility. I need my code to work on extremely large datasets, and I need a collaborator to be able to use my code to reproduce or extend my results. Code that doesn't meet these requirements is hardly worth writing. Code golf, though, is different: it's often an exercise in sacrificing efficiency and readability at the altar of brevity.

For the Sudoku problem, we can start in two obvious places.

• We can condense the computation of the connected indices by using a nested list comprehension. List comprehensions are a way of shortening a loop to a single statement. In this case, the resulting algorithm is slightly less efficient, a bit less readable, but saves a lot of typing.

• Rather than finding the grid space with the fewest possibilities to recursively guess at a solution, we simply choose any unknown grid space. This can be much less efficient, but saves a lot of typing.

Applying these two ideas leads to the following:

This is good, but we can go further by moving the connected list definition into the S() function. Again, this is less efficient than computing the sets once beforehand, but it saves some typing:

We can go a little further by using a set comprehension for the loop over possible values. Set comprehensions are like list comprehensions or generator expressions, but are denoted with curly brackets: {}.

We'll also use a trick here based on the way Python implements boolean logic. When you execute something like

(A or B)

you might expect the result to be either True or False. Instead, Python does something a bit clever. If the result is False, it returns A (which, naturally, evaluates to False). If the result is True, it returns A if A evaluates to True, and B otherwise. We can use this fact to remove the if statement completely from the set comprehension. We'll end up with some extra values within the second set, but the set difference conveniently removes these.

Step 3: Combining Expressions¶

Now we have the basics of the algorithm. We can keep shrinking the implementation by combining the two loops into a single generator expression. It's important that we use a generator expression (surrounded by ()) rather than a list comprehension (surrounded by []), because otherwise all possible solutions would need to be computed in order to return a single one!

For clarity, we'll create a temporary explicit container for the generator, which we can remove later. The result of combining the loops looks like this:

We can further combine the if-else statement into the generator expression to save some more room: if there are no zeros in p, we'll just loop over [p] instead of looping over the generator.

Step 4: Sweating the Details¶

We've condensed the script about as much as we can now, but there are still some tiny changes we can make that will save a few characters here or there. This step is the difference between a code golf amateur and a true code golf pro. Some of the tricks I apply here would not have been obvious to me had I not come across this solution, so I don't think I can call myself a pro just yet!

First of all, we can shorten the definition of the full set of nine digits. Observe:

One character shorter! We're making progress.

Next, we can use compact bitwise operators to test whether square i and square j are related. Our previous expression was

(i%9!=j%9)and(i//9!=j//9)and(i//27!=j//27or i%9//3!=j%9//3)

we can equivalently write

(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)

which saves about 12 more characters.

Further, observe that the variable i, which denotes the index of the first zero in the puzzle string, will be -1 if the string has no zeros. The bitwise inverse of -1 is zero, so ~i will evaluate to False only if there are no zeros in the puzzle. This saves a couple more characters. The result is:

Finally, though it's standard to use four spaces for an indentation, Python will also recognize one-space indentations, which save white space characters. At the same time, we'll remove other unnecessary spaces, and move the definition of g into the statement where it's used. To make things easier to parse, we'll replace a required white-space with a line break (between or and p). Because this break falls between two parentheses, the lack of indentation is still parseable.

We've gotten our solution down to 182 characters! As far as I can tell, this is the best we can do in Python versions less than 3.2. Python 3.3, however, added the "yield from" statement, which can help us further shorten this. In a generator definition, writing

yield from G

is (for our purposes, anyway) essentially equivalent to writing

for g in G:
    yield g

so it fits the bill exactly. As a bonus, the removal of nested indentation allows us to write things on a single line, using the ; character in place of a new line:

Using this new syntactic sugar buys us another twelve characters. We're down to 176 characters: not yet tweetable, but I think it's pretty good! Once again, if you see any further abbreviations that can be made, please let me know in the blog comments.

Another Approach¶

The other shortest sudoku script I've seen is this one, dating back eight years or so and coming in at 185 characters (see the source, and note that due to the change in integer division syntax, the python 3 version, here, is six characters longer than the python 2 version):

This script has a slightly different purpose: it's meant to take an argument in the command line and output one answer. For this reason, a direct comparison of the two solutions is somewhat misleading. Taking away the command-line call brings the count down to 174 characters (note the from sys import* is still required for the exit() call). On the other hand, this script only finds a single solution, and does it in a clever but unorthodox way: in order to break out of the recursion efficiently, it returns the solution as an exit code. This works in the sense that the answer prints to the screen, but means that the script is only useful as a stand-alone application.

Regardless of judgments about which solution "won" this round of code golf, I hope you agree with me that this is a valuable exercise. To me, the end goal of code golf is not simply a concise program: it's the pursuit of a deeper knowledge of the ins and outs of the Python language itself.

Update¶

Several commenters on the blog and on reddit have suggested improvements to the algorithm. First of all, the conditional of the form

(genexp if~i else[p])

can be made one character shorter by using the fact that boolean variables are interpreted as either 1 or zero:

([p],genexp)[i<0]

Also, it was pointed out that the yield from can be replaced by a simple return in this case, because yield is not used anywhere in the function. So the shortest version of the function becomes this:

This is 171 characters!

But there's more. Now that the yield from is unnecessary, we can move to python 2.x and change all the Python 3-style integer division operators (//) to Python 2-style (/). This saves six more characters:

165 characters, but note that this requires Python 2.7.

There's one more thing we can add, as noted by a commenter below. In Python 2.x, back-ticks can be used as a shorthand for string representation (this is a feature removed in Python 3.x). Thus:

A problem, though, is that in 32-bit architectures, 5**18 is a long integer, so that the string representation is '3814697265625L' (note the L appended at the end). This would lead to incorrect solutions. But as long as we're assured that we're on a 64-bit platform, we can use this to save three more characters:

That brings our best to 162 characters, though it requires Python 2.7 and a 64-bit system. Thanks to all commenters who suggested these improvements!

This post was written in the IPython notebook. The raw notebook can be downloaded here. See also nbviewer for an online static view.