Dancing-links: What Programming Is

Most people have no idea what ‘being a programmer’ is about. A common response when saying what you do is ‘oh, I couldn’t do that, staring at a screen all day’.

In the hope of communicating better, I’ve been trying out a few different responses. One I tried recently is “I solve abstract problems through the manipulation of symbols”. By itself it doesn’t actually help all that much but it does open up a whole realm of possible conversations that would normally be shut down by ‘oh I couldn’t do that, staring at a screen all day’.

What do I mean by abstract problem? Well, the sudoku in the paper on friday is a concrete problem. An abstract problem would be solving every sudoku. Solving the friday sudoku gives you the solution and some limited insight into how you got there. Solving the abstract sudoku problem gives you every solution for any sudoku you come across in the future, and an insight into what kind of thing sudoku actually is, what solutions are, and often what sorts of things are going on in the human brain, and what sorts of things would go on in the human brain if its ability to keep track of things without getting bored wasn’t hopelessly stunted.

Every time you tried to solve a sudoku and found yourself jotting little notes to help you keep track of more information than could reasonably be kept in your head you were reaching for solutions that were beyond what is practical in a normal human brain. If you ever started reading about ‘techniques’ or trying to work out all the different ways you can make progress on a sudoku, you were thinking about the abstract problem.

Solving the problem teaches you the solution. Solving the abstract problem teaches you about yourself and the nature of the world.

What does the solution to the abstract problem look like? The solution to the abstract problem has to be able to generate a solution to any of the concrete problems, so rather than a filled in grid, the solution to the abstract problem is a process that given a puzzle grid will generate the filled in grid. Both the concrete problem and the concrete solution can easily be printed in a newspaper but the abstract solution is a process which could be represented in many different ways none of which look anything like a sudoku grid, just as a recipe for cupcakes doesn’t look anything like an actual cupcake.

cat sleeping when it should be doing sudoku because this *is* the internet after all
A cat is not a good abstract solution to the problem of sudoku.

Still, while the abstract solution may be a process, we need a way to communicate it to other people, so we describe the process in words. As you come up with more and more abstract solutions, you discover that a lot of the parts of the process can be broken down into small steps that are used in all sorts of different abstract solutions. Amazingly, these steps are simple enough that they can all be done by machine, so you can build a machine that takes a description of an abstract solution and makes that process easily repeatable (which is in fact what a computer is).

One of the interesting things that comes out of finding the abstract solutions to problems instead of the concrete solution is that sometimes you find that the exact same abstract solution can be used to solve apparently different problems. Often this involves converting between different representations of the problem. For example, there’s no difference between a sudoku puzzle where the symbols you use are the numbers 1 to 9 or the same puzzle using the letters A to I. You can rotate a sudoku puzzle or flip it upside down, but it’s still essentially the same problem. Once you start thinking like this, you can make surprising discoveries, like the fact that tiling shapes into a chessboard can be solved with exactly the same abstract solution as sudoku.

For a time, it was hoped that perhaps all problems in the universe could ultimately be solved by one single master abstract solution, which would contain the answer to everything. Starting perhaps with logic and maths puzzles, and then ultimately, as we find better descriptions for the universe moving on to problems of physics, chemistry, biology and psychology. The german mathematician David Hilbert in the early nineteen hundreds was particularly associated with the first part of this task. The dream of being able to do this with everything looks pretty unlikely now that Gödel proved that any system that includes simple mathematics can represent problems for which it is unable to represent solutions, but there are many interesting stories in the history of logic puzzles, going back at least to Archimedes who proposed a maths puzzle about the ‘cattle of the sun’ which when solved gives an answer of more cows than could possibly fit in the visible universe.

In computing we call the process that is an abstract solution an algorithm after the Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī from the 9th century House of Wisdom in Baghdad. One of the abstract solutions for solving sudoku (and n-queens, and shape tiling…..) is called Algorithm X, and an efficient way of keeping track of all the moving parts was named ‘dancing links’ by computing legend Donald Knuth (currently working for Google).

For fun, I’ve implemented dancing links here where you can see it solve sudoku and shape tiling (at the bottom of the page). It’s also a project that I created using particular tools and services; javascript, jasmine, node.js, heroku, jsdoc, cloud9, git, github and I will write a more technical blog about my experiences with those soon.

Leave a Reply

Your email address will not be published. Required fields are marked *