What Sudoku isn’t

28 June 2005

I like Sudoku. I quite enjoy Sudoku, as, it seems, does a vast proportion of the British population. Various people have, in recent weeks, used up an awful lot of newsprint trying to look at why it’s so popular, trying to out-Sudoku rival publications, and none of it seems very satisfactory. I mean, they bang on about how it appeals to both men and women – as opposed to chess problems, which are primarily male, and cryptic crosswords, which in my experience appeals equally (and usually equally little) to both men and women, but I think they’re missing the point.

The reason it’s popular is that it isn’t a game. It’s an exercise.

There’s only one right answer; any “wrong” answer quickly reveals itself as one. Compare that to a cryptic crossword: there’s only one right answer, but you could be wrong for quite a while before noticing it – and there’s no absolute proof that an answer’s wrong; it could be an intersecting answer that’s wrong. And so forth.

Sudoku is algorithmic. It can be solved with brute force, and brute-force solvers don’t have to be programmed with any grace (given today’s processor power). The least efficient Sudoku solver just looks at every single possible layout of the board. More efficient ones can make inferred guesses from numbers already on the grid. None are as complex as chess AI or chess problem solving. They might even be simpler than a checkers/draughts solver.

But they’re taxing enough for your average commuter. The built-in proof – that the number you’ve just entered must be right – is very satisfying, and yet also comforting. No effort put in to the solution of a Sudoku problem is ever wasted, really.

The hardest Sudoku problems tend to require a little lateral thinking, but it’s a world away from the lateral thinking a cryptic crossword demands. Once you’ve found the approach, the puzzle tends to fall into place. The cryptic crossword requires you to constantly re-adjust your approach for every clue. It keeps you on your toes.

I love solving problems I know the answer to, mainly because I love the mechanics. It’s why knowing the end of a film doesn’t make much difference to me – if anything, it excites me more because I want to know how that conclusion was reached. And I enjoy Sudoku because it’s about process, about working-through, not about the destination.

So what I find entertaining is this: all over the tube, the train, I see people solving equations – people who probably hated solving equations at school. Not playing games, not even solving anything particular puzzling. Just stepping through algorithms to solve equations. It may be on the games page of the paper, but it’s not a game: it’s an exercise. In fact, forget the pronoun: it is exercise, of sorts. Rather than being “properly” taxing, Sudoku is time-consuming. The two are easy to confuse, especially if you’re caught up in what you’re doing, much like exercise – you can push yourself, or merely fill time.

What Sudoku isn’t, then, is a game.

Now for my next question: if Sudoku isn’t a game, can the act of solving it still be described as play?

8 comments on this entry.

  • mattw | 29 Jun 2005

    sudoku as combinations of kata.

    the play for me is discovering new, more complex, patterns of movement to act out, and to perfect the existing ones. discovery by doing: that can be play.

    the process of sudoku: hikaru dorodango.

  • Tom | 29 Jun 2005

    Oh, definitely. It was a nonne question, expecting the answer yes. The discovery-by-doing aspect is very much play; indeed, the refining-algorithms-by-doing technique is classic play; taking shorter routes to work each day, refining how late I can get up to a) be clean and b) not miss my train.

    I like the idea of it as kata. Not just a series of forms/exercises, rules worked through, but applying those rules/kata to a real world problem. The kata are the toolset to approach the problem. There’s the meditative aspect of kata which runs in parallel with the practical aspect. And yet it’s still not the same as barfight (which is the best way to draw my cryptic crosswords into this analogy).

    Whittling away; making the ball of mud smoother and shinier; refining the kata rather than learning more.

    Now there’s an idea: backwards Katamari Damacy – where you have a big ball of “stuff” and the goal is not to change its size, but to make it smoother. Dorodango Damacy, as it were.

  • xander | 1 Jul 2005

    A big Dutch Sudoku site:

    http://sudoku.jouwpagina.nl

    Enjoy!

  • DJ | 23 Jul 2005

    Check out http://www.el.com/links/sudoku.asp Essential Guide and Links to Sudoku. It is a bridge to an Internet of Sudoku puzzles, sites, solutions, history, etc. etc.

  • David Wahlstedt | 14 Aug 2005

    Tom, you claim that it can be solved with brute-force. Under which conditions do you mean ? No cutting down the search space before guessing ?
    Can you give a bound of the number of combinations needed ?
    Say there are 25 given numers, then one has to fill in 56 positions with values in [1..9]. Seems to be quite a lot…

    Best regards, David

  • Tom | 14 Aug 2005

    It can be beaten by brute-force because there are only a finite number of possibly layouts – and if there’s only one correct answer, it’s not necessary to fill every square on the board to find out you’re wrong – the moment you hit an impossibility, that iteration gets ticked off as a “FAIL” and you go round again.

    Of course, the brute force required is pretty massive. My memory of permutations and combinations is failing me, I’m afraid, so I can’t offer a solution to your problem, and calculating the upper bound for “correct” sudokus (rather than for just inserting the numbers 1-9 once in a row of 9 squares) is quite tricky. Still, my point is: it has a finite number of possibilities and clearly defined points for failure, which means an automated system based around brute force – no matter how tricky it is to program – can be guaranteed to work. Unlike, say, trying to reverse-engineer private keys, or MD5 hashes.

    I never said it was easy…

  • wim | 13 Sep 2005

    WIKIPEDIA:
    A valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960 [3], which is roughly the number of micrometers to the nearest star. This number is equivalent to 9! × 72^2 × 2^7 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. A paper detailing the methodology of their analysis can be found at [4]. The number of valid Sudoku solution grids for the 16×16 derivation is not known.

    Of course, some of the 9×9 grids can easily be transformed into others; by relabelling the numbers, by rotating or reflecting the grid, and by permuting certain rows and columns. Ed Russell and Frazer Jarvis have counted the number of “essentially different” sudoku grids as 5,472,730,538: see the previous link for more details of the calculation.

  • Rijk | 7 Apr 2006

    I am addicted to Sudoku! I made an inventory of methods for solving even the most difficult Sudoku. Start with looking for duo’s, it’s an eye opener!
    Check http://www.sudokuhints.nl/en/ for details.

    Good luck!