{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Code Golf in Python: Sudoku"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook originally appeared as a [blog post](http://jakevdp.github.com/blog/2013/04/15/code-golf-in-python-sudoku/)\n",
"on [Pythonic Perambulations](http://jakevdp.github.com),\n",
"by Jake Vanderplas."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"*Edit: based on suggestions from readers, the best solution is down to 162 characters!\n",
"Read to the end to see how*"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A highlight of PyCon each year for me is working on the little coding\n",
"challenges offered by companies in the expo center.\n",
"I love testing my Python prowess against the problems they pose (and\n",
"being rewarded with a branded mug or T-shirt!)\n",
"This year, several of the challenges involved what's become known as\n",
"[code golf](http://codegolf.com/): writing a solution with minimal keystrokes.\n",
"\n",
"By way of example, take a look at this function definition:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def S(p):i=p.find('0');return[(s for v in\n",
"set(`5**18`)-{(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:])),[p]][i<0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is a valid function definition (in Python 2.7) which executes a\n",
"particular task. I'll give more information on the workings of this\n",
"script later on, but for now I'll leave it to the reader to ponder\n",
"over what it might do.\n",
"\n",
"\n",
"\n",
"Given the level of obfuscation involved, you might wonder what the point\n",
"is: you'd never want to write \"real\" code in this style, so why spend the\n",
"time doing it? I'd argue that it's useful for more than just upping your\n",
"geek cred: good Python code golf must utilize many quirks of the Python\n",
"language in seeking brevity above all else. Learning to utilize these\n",
"quirks can lead to a much deeper understanding of the Python language.\n",
"\n",
"I thought about putting together a list of tricks that can help lead to\n",
"short programs, but the problem is there are so many of them (and there\n",
"are other pages out there which do this adequately enough). Instead,\n",
"I decided to simply work through a step-by-step example of creating\n",
"a code golf solution to a fun little problem: solving Sudoku."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![Sudoku Grid](http://jakevdp.github.com/images/sudoku.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You've probably seen Sudoku: it's a puzzle consisting of a 9x9 grid\n",
"of numbers, with some spaces left blank.\n",
"The grid must be filled so that each row, column,\n",
"and 3x3 box contains the numbers 1-9. It's a generalization of the\n",
"*Latin Squares* first studied by Leonhard Euler nearly 300 years ago.\n",
"\n",
"The reason I chose to use Sudoku here is simple: not only is today\n",
"Euler's birthday, but Sudoku is how I first learned Python.\n",
"My first year of graduate school, my research advisor\n",
"recommended that I learn Python for the project I was working on.\n",
"Sudoku had just become popular in the US at the time, and I decided to\n",
"learn Python by writing a Sudoku solver. I did it over my winter\n",
"break, and the rest (so it's said) is history.\n",
"\n",
"Note that this is by no means a new subject: you can read about Sudoku\n",
"in Python in several places, and there are even a few code golf solutions\n",
"floating around out there. In particular, you should take a look at\n",
"[this solution](http://www.scottkirkwood.com/2006/07/shortest-sudoku-solver-in-python.html),\n",
"which is the shortest solver I've seen, and from which I borrowed a few\n",
"of the tricks used below.\n",
"\n",
"Here we'll pose the problem in a slightly different way, which will give\n",
"us the chance to develop a brand new short algorithm."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The Problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Every code golf challenge must start with a well-defined problem.\n",
"Here is ours:\n",
"\n",
"- *Write a function* ``S(p)`` *which, given a valid Sudoku puzzle,\n",
"returns an iterator over all solutions of the puzzle.*\n",
"\n",
"The puzzle will be in the form of a length-81 string of digits, with\n",
"``'0'`` denoting an empty grid space. The solved puzzles should also\n",
"be length-81 strings, with the zeros replaced by solved values.\n",
"\n",
"For example, a valid ``S(p)`` may produce the following results:\n",
"\n",
"```python\n",
"puz=\"027800061000030008910005420500016030000970200070000096700000080006027000030480007\"\n",
"for s in S(puz):\n",
" print(s)\n",
"```\n",
"\n",
"```\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"```\n",
"\n",
"```python\n",
"puz = 81*'0' # empty puzzle\n",
"print(next(S(puz)))\n",
"```\n",
"\n",
"```\n",
"132598476598476132476132985319825764825764319764913258981257643647389521253641897\n",
"```\n",
"\n",
"Notice that the function `S()` cannot simply return a list of valid solutions:\n",
"if it did, then the empty puzzle example would need to produce all ~$10^{22}$\n",
"valid sudoku grids before the first solution could be accessed!\n",
"Instead, it must make use of Python's extremely useful\n",
"**generator** syntax. If you've never used generators and\n",
"generator expressions in your Python code,\n",
"stop reading this right now and go learn about them: they're one of\n",
"the most unique and powerful features of the Python language.\n",
"\n",
"As you'll see below, my best solution is ~~176~~ 162 characters, and is the\n",
"code snippet I showed above:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def S(p):i=p.find('0');return[(s for v in\n",
"set(`5**18`)-{(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:])),[p]][i<0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It's rather unenlightening in itself, so below I'll explain the steps\n",
"I took to arrive at it, in hopes that you can learn from my\n",
"thought process. Though this is the best solution I was able to come\n",
"up with, I don't know whether or not a better one might be out there.\n",
"If you can beat it, please post your solution in the blog comment thread!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 1: Focus on Correct Code"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A code golf script must be more than simply short: it must be correct.\n",
"For this reason, I generally start by simply writing correct code, and\n",
"not for the moment worrying about brevity.\n",
"\n",
"In the case of Sudoku, there are many rules and rubriks that can be used\n",
"to create an efficient solver (read about some of them [here](http://www.sudokuoftheday.com/pages/techniques-overview.php)).\n",
"Using these, it is possible to solve most (all?) Sudoku puzzles without\n",
"resorting to guess-and-check approaches. To implement this strategy,\n",
"one approach might be to enumerate the sets of possible values\n",
"for each grid space, and apply these rules to eliminate values until\n",
"only a single possibility remains within each space.\n",
"\n",
"Unfortunately, this is not a very suitable approach for code golf:\n",
"the number of rules required to accomplish this is very large. Instead,\n",
"we'll make use of the minimal amount of rules, and write a guess-and-check\n",
"based solver.\n",
"\n",
"Here's a first attempt, focusing on the algorithm rather than on brevity.\n",
"We'll start by defining a test puzzle with four solutions, and write a\n",
"small function that can test our solver:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"puz = \"027800061000030008910005420500016030000970200070000096700000080006027000030480007\"\n",
"\n",
"def test(S):\n",
" # solve an empty puzzle\n",
" print(next(S(81*'0')))\n",
" print('')\n",
"\n",
" # find all four solutions of puz\n",
" for s in S(puz):\n",
" print(s)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985351249768789361254624857319943785621817624593265913847\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"# Write functions that, given an index 0 <= i < 81,\n",
"# return the indices of grid spaces in the same row,\n",
"# column, and box as entry i\n",
"def row_indices(i):\n",
" start = i - i % 9\n",
" return range(start, start + 9)\n",
"\n",
"def col_indices(i):\n",
" start = i % 9\n",
" return range(start, start + 81, 9)\n",
"\n",
"def box_indices(i):\n",
" start = 27 * (i // 27) + 3 * ((i % 9) // 3)\n",
" return [i for j in range(3) for i in range(start + 9 * j, start + 9 * j + 3)]\n",
"\n",
"# compute and store the full set of connected indices for each i\n",
"connected = [(set.union(set(box_indices(i)),\n",
" set(row_indices(i)),\n",
" set(col_indices(i)))\n",
" - set([i]))\n",
" for i in range(81)]\n",
"\n",
"# S(p) will recursively find solutions and \"yield\" them\n",
"def S(p):\n",
" # First, find the number of empty squares and the number of\n",
" # possible values within each square\n",
" L = []\n",
" for i in range(81):\n",
" if p[i] == '0':\n",
" vals = set('123456789') - set(p[n] for n in connected[i])\n",
" if len(vals) == 0:\n",
" return\n",
" else:\n",
" L.append((len(vals), i, vals))\n",
" \n",
" # if all squares are solved, then yield the current solution\n",
" if len(L) == 0 and '0' not in p:\n",
" yield p\n",
" \n",
" # otherwise, take the index with the smallest number of possibilities,\n",
" # and recursively call S() for each possible value.\n",
" else:\n",
" N, i, vals = min(L)\n",
" for val in vals:\n",
" for s in S(p[:i] + val + p[i + 1:]):\n",
" yield s\n",
"\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is the test output we expect: it quickly finds not only the four solutions\n",
"of the test puzzle, but a solution derived from a completely empty puzzle. This\n",
"is by no means a complete test suite, but it gives us good reason to believe\n",
"that the code is correct."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 2: Simplify the Algorithm"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For me, the biggest hurdle to writing concise programs was letting go\n",
"of the compulsion to write clear and efficient code.\n",
"In my research, the two most important aspects of code are its scalability\n",
"and its readibility. I need my code to work on extremely large datasets,\n",
"and I need a collaborator to be able to use my code to reproduce or extend\n",
"my results. Code that doesn't meet these requirements is hardly worth\n",
"writing. Code golf, though, is different: it's often an exercise in\n",
"sacrificing efficiency and readability at the altar of brevity.\n",
"\n",
"For the Sudoku problem, we can start in two obvious places.\n",
"\n",
"- We can condense the computation of the connected indices by using\n",
" a nested list comprehension. List comprehensions are a way of shortening\n",
" a loop to a single statement. In this case, the resulting algorithm is\n",
" slightly less efficient, a bit less readable, but saves a lot of typing.\n",
"\n",
"- Rather than finding the grid space with the fewest possibilities\n",
" to recursively guess at a solution, we simply choose any unknown\n",
" grid space. This can be much less efficient, but saves a lot of typing.\n",
"\n",
"Applying these two ideas leads to the following:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"# store the full set of connected indices for each i\n",
"connected = [set([j for j in range(81)\n",
" if (i%9==j%9) or (i//9==j//9)\n",
" or (i//27==j//27 and i%9//3==j%9//3)])\n",
" for i in range(81)]\n",
"def S(p):\n",
" # find any grid space without a known value\n",
" i = p.find('0')\n",
" \n",
" # if no entry is zero, then yield the current solution\n",
" if i < 0:\n",
" yield p\n",
" \n",
" # otherwise, take this index and recursively call S()\n",
" # for each possible value.\n",
" else:\n",
" for val in set('123456789') - set(p[n] for n in connected[i]):\n",
" for s in S(p[:i] + val + p[i + 1:]):\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is good, but we can go further by moving the ``connected`` list\n",
"definition into the ``S()`` function. Again, this is less efficient\n",
"than computing the sets once beforehand, but it saves some typing:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"def S(p):\n",
" i = p.find('0')\n",
" if i < 0:\n",
" yield p\n",
" else:\n",
" for v in set('123456789')-set(p[j] for j in range(81)\n",
" if (i%9==j%9) or (i//9==j//9)\n",
" or (i//27==j//27 and i%9//3==j%9//3)):\n",
" for s in S(p[:i]+v+p[i+1:]):\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can go a little further by using a **set comprehension** for\n",
"the loop over possible values. Set comprehensions are like list comprehensions\n",
"or generator expressions, but are denoted with curly brackets: ``{}``.\n",
"\n",
"We'll also use a trick here based on the way Python implements boolean logic.\n",
" When you execute something like\n",
"\n",
" (A or B)\n",
"\n",
"you might expect the result to be either ``True`` or ``False``. Instead, Python\n",
"does something a bit clever. If the result is False, it returns ``A`` (which,\n",
"naturally, evaluates to ``False``). If the result is True, it returns ``A`` if\n",
"``A`` evaluates to ``True``, and ``B`` otherwise. We can use this fact to\n",
"remove the ``if`` statement completely from the set comprehension. We'll end\n",
"up with some extra values within the second set, but the set difference conveniently\n",
"removes these."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"def S(p):\n",
" i = p.find('0')\n",
" if i < 0:\n",
" yield p\n",
" else:\n",
" for v in set('123456789')-{(i%9!=j%9)and(i//9!=j//9)\n",
" and(i//27!=j//27or i%9//3!=j%9//3)\n",
" or p[j]for j in range(81)}:\n",
" for s in S(p[:i]+v+p[i+1:]):\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 3: Combining Expressions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we have the basics of the algorithm. We can keep shrinking the\n",
"implementation by combining the two loops into a single generator\n",
"expression. It's important that we use a generator expression\n",
"(surrounded by ``()``) rather than a list comprehension (surrounded\n",
"by ``[]``), because otherwise all possible solutions would need to\n",
"be computed in order to return a single one!\n",
"\n",
"For clarity, we'll create a temporary explicit container for the\n",
"generator, which we can remove later.\n",
"The result of combining the loops looks like this:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"def S(p):\n",
" i = p.find('0')\n",
" if i < 0:\n",
" yield p\n",
" else:\n",
" g = (s for v in set('123456789')\n",
" - {(i%9!=j%9)and(i//9!=j//9)\n",
" and(i//27!=j//27or i%9//3!=j%9//3)\n",
" or p[j]for j in range(81)}\n",
" for s in S(p[:i]+v+p[i+1:]))\n",
" for s in g:\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can further combine the ``if-else`` statement into the generator expression\n",
"to save some more room: if there are no zeros in ``p``, we'll just loop over\n",
"``[p]`` instead of looping over the generator."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"def S(p):\n",
" i = p.find('0')\n",
" g = (s for v in set('123456789')\n",
" -{(i%9!=j%9)and(i//9!=j//9)and(i//27!=j//27or i%9//3!=j%9//3)\n",
" or p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:]))\n",
" for s in (g if i>=0 else[p]): # parentheses here for clarity\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Step 4: Sweating the Details"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We've condensed the script about as much as we can now, but there\n",
"are still some tiny changes we can make that will save a few\n",
"characters here or there. This step is the difference between\n",
"a code golf amateur and a true code golf pro. Some of the tricks\n",
"I apply here would not have been obvious to me had I not come\n",
"across\n",
"[this solution](http://www.scottkirkwood.com/2006/07/shortest-sudoku-solver-in-python.html),\n",
"so I don't think I can call myself a pro just yet!\n",
"\n",
"First of all, we can shorten the definition of the full set of nine digits.\n",
"Observe:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"set(['1', '3', '2', '5', '4', '7', '6', '9', '8'])\n",
"set(['1', '3', '2', '5', '4', '7', '6', '9', '8'])\n"
]
}
],
"source": [
"print(set('123456789'))\n",
"print(set(str(5**18)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One character shorter! We're making progress.\n",
"\n",
"Next, we can use compact bitwise operators to test whether\n",
"square ``i`` and square ``j`` are related. Our previous\n",
"expression was\n",
"\n",
"```\n",
"(i%9!=j%9)and(i//9!=j//9)and(i//27!=j//27or i%9//3!=j%9//3)\n",
"```\n",
"\n",
"we can equivalently write\n",
"\n",
"```\n",
"(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)\n",
"```\n",
"\n",
"which saves about 12 more characters.\n",
"\n",
"Further, observe that the variable ``i``, which denotes the index\n",
"of the first zero in the puzzle string, will be ``-1`` if the\n",
"string has no zeros. The bitwise inverse of ``-1`` is zero,\n",
"so ``~i`` will evaluate to False only if there are no zeros in\n",
"the puzzle. This saves a couple more characters. The result is:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"def S(p):\n",
" i = p.find('0')\n",
" g = (s for v in set(str(5**18))\n",
" -{(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)\n",
" or p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:]))\n",
" for s in g if~i else[p]:\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, though it's standard to use four spaces for an indentation,\n",
"Python will also recognize one-space indentations, which save white\n",
"space characters. At the same time, we'll remove other unnecessary\n",
"spaces, and move the definition of ``g`` into the statement where\n",
"it's used. To make things easier to parse, we'll replace a required\n",
"white-space with a line break (between ``or`` and ``p``).\n",
"Because this break falls\n",
"between two parentheses, the lack of indentation is still parseable."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"132598476598476132476132985319825764825764319764913258981257643253641897647389521\n",
"\n",
"327894561465132978918765423589216734643978215172543896794651382856327149231489657\n",
"327894561465132978918765423589216734643978215271543896794651382856327149132489657\n",
"327894561645132978918765423589216734463978215172543896794651382856327149231489657\n",
"327894561645132978918765423589216734463978215271543896794651382856327149132489657\n"
]
}
],
"source": [
"def S(p):\n",
" i=p.find('0')\n",
" for s in(s for v in set(str(5**18))-{(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:]))if~i else[p]:\n",
" yield s\n",
"test(S)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We've gotten our solution down to 182 characters!\n",
"As far as I can tell, this is the best we can do\n",
"in Python versions less than 3.2. Python 3.3,\n",
"however, added the \"``yield from``\" statement, which\n",
"can help us further shorten this. In a generator\n",
"definition, writing\n",
"\n",
" yield from G\n",
"\n",
"is (for our purposes, anyway) essentially equivalent to writing\n",
"\n",
" for g in G:\n",
" yield g\n",
"\n",
"so it fits the bill exactly. As a bonus, the removal of nested\n",
"indentation allows us to write things on a single line, using\n",
"the ``;`` character in place of a new line:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def S(p):i=p.find('0');yield from(s\n",
"for v in set(str(5**18))-{(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:]))if~i else[p]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using this new syntactic sugar buys us another twelve characters.\n",
"We're down to 176 characters: not yet tweetable, but I think it's\n",
"pretty good! Once again, if you see any further abbreviations that\n",
"can be made, please let me know in the blog comments."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Another Approach"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The other shortest sudoku script I've seen is this one, dating back eight\n",
"years or so and coming in at 185 characters (see the\n",
"[source](http://www.scottkirkwood.com/2006/07/shortest-sudoku-solver-in-python.html),\n",
"and note that due to the change in integer division syntax, the python 3 version,\n",
"here, is six characters longer than the python 2 version):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def r(a):i=a.find('0');~i or exit(a);[m\n",
"in[(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)or a[j]for\n",
"j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]\n",
"from sys import*;r(argv[1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This script has a slightly different purpose: it's meant to take an\n",
"argument in the command line and output one answer. For this reason,\n",
"a direct comparison of the two solutions is somewhat misleading. Taking\n",
"away the command-line call brings the count down to 174 characters\n",
"(note the ``from sys import*`` is still required for the ``exit()`` call).\n",
"On the other hand, this script only finds a single solution,\n",
"and does it in a clever but unorthodox way:\n",
"in order to break out of the recursion efficiently, it returns the solution\n",
"as an exit code. This works in the sense that the answer prints to the\n",
"screen, but means that the script is only useful as a stand-alone application.\n",
"\n",
"Regardless of judgments about which solution \"won\" this round of code\n",
"golf, I hope you agree with me that this is a valuable exercise.\n",
"To me, the end goal of code golf is not simply a concise program: it's\n",
"the pursuit of a deeper knowledge of the ins and outs of the\n",
"Python language itself."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Update"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Several commenters on the blog and on reddit have suggested improvements to the algorithm.\n",
"First of all, the conditional of the form\n",
"\n",
" (genexp if~i else[p])\n",
"\n",
"can be made one character shorter by using the fact that boolean variables are interpreted\n",
"as either 1 or zero:\n",
"\n",
" ([p],genexp)[i<0]\n",
"\n",
"Also, it was pointed out that the ``yield from`` can be replaced by a simple ``return`` in\n",
"this case, because ``yield`` is not used anywhere in the function. So the shortest version\n",
"of the function becomes this:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def S(p):i=p.find('0');return[(s for v in\n",
"set(str(5**18))-{(i-j)%9*(i//9^j//9)*(i//27^j//27|i%9//3^j%9//3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:])),[p]][i<0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is 171 characters!\n",
"\n",
"But there's more. Now that the `yield from` is unnecessary, we can move to python 2.x and\n",
"change all the Python 3-style integer division operators (``//``) to Python 2-style (``/``).\n",
"This saves six more characters:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def S(p):i=p.find('0');return[(s for v in\n",
"set(str(5**18))-{(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:])),[p]][i<0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"165 characters, but note that this requires Python 2.7.\n",
"\n",
"There's one more thing we can add, as noted by a commenter below.\n",
"In Python 2.x, back-ticks can be used as a shorthand for\n",
"string representation (this is a feature removed in Python 3.x). Thus:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3814697265625\n",
"3814697265625\n"
]
}
],
"source": [
"print(str(5**18))\n",
"print(`5**18`)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A problem, though, is that in 32-bit architectures, ``5**18`` is a long integer, so that\n",
"the string representation is ``'3814697265625L'`` (note the ``L`` appended at the end).\n",
"This would lead to incorrect solutions. But as long as we're assured that we're on a 64-bit\n",
"platform, we can use this to save three more characters:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def S(p):i=p.find('0');return[(s for v in\n",
"set(`5**18`)-{(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or\n",
"p[j]for j in range(81)}for s in S(p[:i]+v+p[i+1:])),[p]][i<0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That brings our best to 162 characters, though it requires Python 2.7 and\n",
"a 64-bit system. Thanks to all commenters who suggested these improvements!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This post was written in the IPython notebook. The raw notebook can be\n",
"downloaded [here](http://jakevdp.github.com/downloads/notebooks/SudokuCodeGolf.ipynb).\n",
"See also [nbviewer](http://nbviewer.ipython.org/url/jakevdp.github.com/downloads/notebooks/SudokuCodeGolf.ipynb)\n",
"for an online static view."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python [default]",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}