Why I don’t like Sudoko

28 April 2005

When in London last week I encountered several people on the Tube doing Sudoku puzzles, introduced to these shores by The Times, and promptly copied by the rest. It’s described by one person as a “crossword for numbers”, which I think is a bit unfair to crosswords, for reasons I’ll go into later.

Anyway, the puzzle consists of a 9×9 grid partially filled with digits; the goal of the puzzle is to fill the entire grid, such that the digits 0-9 appear exactly once in every row, column and 3×3 subsquare within the grid. I had a go at a couple of examples on the web, and found them interesting and challenging. The only problem is that with geeks like me, we quickly tire of solving the problem and work on trying to solve the bigger problem – how to program a computer to do the work for you.

In this case it’s not too hard to do a simple helper program, working on purely deductive logic – I thought up the basics while queuing in Tesco’s just now. Each cell has a list (maybe a 9-length boolean array) of whether a particular number may be (true) or definitely isn’t. Every time a number is added all the cells in its row, colum and subsquare have their lists updated; if a list ends up with only one candidate (one true value and eight false in the array) then you have a definite, you add that number and repeat the process. Then I though if you have two cells in a row or column or block, each with the same two possibilities, then you can exclude those possibilities from all the others). And if you can do that with two, you can do it with sets of three, four, etc. Use binary arithmetic, and bitshifts & masks to do the dirty work, will help speed it up.

By the time I got to the front of the queue, I realised this is purely deductive and it may not be possible to solve a grid from the initial numbers given, so we may have to add an inductive element: introducing test numbers to see if they work in the grid, and retracting them if they don’t could be added. It would be a lot of fun to make a Flash applet to do it, and trying to get it to be as efficient as possible, if it hadn’t been done already by others.

An individual puzzle may be very hard and challenging, but I’d just “cheat” and make a program to do it for me. The challenge isn’t in the puzzle, the challenge I’d like is in making something that would solve the puzzle for you, as fast as possible.

Anyway, another Japanese puzzle which I was shown a few years ago by a friend is a little more enjoyable; having tracked them down on Google I’ve found they’re called Edel. Edel consists of a blank grid of squares, which can either be filled in or not (black or white). At the start of each row or column, there are numbers telling you the length of continuous blocks filled-in squares in that row or column, but crucially, not the spacing between them; it’s up to you to deduce which squares lying within are the ones filled in (this may be a shit explanation, the illustrated examples are better). This puzzle can be inductive as well as deductive, and the nice thing is that they are also artistic; finished solutions can create pictures or patterns (this final part may make it easier for humans to solve rather than computers, as we can do image recognition and inform our guesses by that).

Sadly, it’s not quite taken off in the UK yet, although with the Sudoku craze it may only be a matter of time before some newspaper puts them in as an alternative; I’ve been unable to find Edel puzzle books in the mainstream bookshops (though I’ve just thought it might be worth checking specialist Japanese shops).

Update: I’ve found out that Edel puzzles are also called Nonograms, and that some bright spark has come up with a nonogram version of Minesweeper, Nonosweeper. (via Kevan)

Still, even Edel may be universally solvable by a computer with some clever tricks and hacks, so eventually the fun may be brought out of that too. Which brings me on to crosswords – at Cambridge I was one of those who resided in the college bar for at least an hour every morning, avoiding lectures by drinking coffee and ploughing through the crosswords in the newspapers (first the Telegraph, then the Guardian, then the Times if I was feeling up to it), of late I haven’t kept up, though I stood over a complete stranger’s Telegraph shoulder in the pub last Thursday and did most of it for him (I feel bad – I ruined his challenge, and then he bought me a drink by way of saying well done!). Cryptic crossword clues are usually horrific (especially some Grauniad ones), it’s bad enough trying to parse them, let alone solve them, if you’re a human. I shudder to think how to teach solving them to a computer. Although computers can help us with anagrams and partially complete words, there is no way on Earth a computer today could be given clues and a blank grid and expected to come up with a solution. If they ever get anywhere near that smart, run for the hills.

Because no-one, least of all me, is likely to come up with a computer program that will be able to fully solve every crossword possible any time soon (although it would be fun trying to coach AIs and genetic algorithms to do so), cryptic crosswords are safe from the grubby grasp of silicon. While Sudoku, without a computer to help you, is just as challenging and intellectually stimulating, crosswords are on another level in terms of the mental approach taken; I can escape from logical restrictions into a different and artistic, but equally fun realm.

Hacking together an application to solve Sudoku in the fastest time possible is similarly artistic and demanding – it’s by no means a simple logical deduction and there are a wide variety of approaches. It’d be quite hard for a computer to write such a program straight away; it’s a talent that is still privileged to us rather than the machines. Which is funny to think about, for some, that writing programs is as much a proof of human creativity and artisanship as anything else you care to mention.

To sum up, I don’t like Sudoko. Though I don’t dislike it either, it’s just something that we can leave to the computers to do for us instead. There are much more fun challenges that we ourselves, and only ourselves, are able to do.


10 Responses

Chris Booth

There are so many ways to respond to your article! This is my third attempt.

First, it seems to me that almost all puzzles rely on following some sort of recipe. Cryptic crosswords have more complex recipes than does Su Doku, but you can still teach people the recipe. An extension of this thought is that chess or go are iterated puzzles (every time it is your turn you have to solve a puzzle). The puzzle is so large and complex that humans can do very well by pattern matching and intuition guided by experience. In principle, however, both puzzles could be completely solved by a computer that was large and powerful enough.

Second, solving Su Doku isn’t the only challenge available to computer programmers. Like you, I recently came across these puzzles, but rather than thinking about how to write a program to solve the puzzle, I thought it might be interesting to write a program to generate them. One approach I have in mind is to randomly fill a grid with numbers according to the rules, then pick a number at random and if it is logically entailed by what is in the grid at the time, then remove it. Repeat until no more numbers can be removed.

Finally, I have to agree with you that puzzles that only humans can solve have a certain something. I love The Independent’s “Get the picture” for that reason. But the best example of this class of puzzle (often done for charity) are those where the clues are initial letters and lengths of the key words in a phrase (e.g. “The T—– D— of C——–”). What fascinates me about them is that there doesn’t seem to be any analytical process one can go through to solve them, but the answers are almost always universally accepted as right. And they can pop into my head at any time.

Today’s Independent features a “Super Su Doku” – 16×16 grid with the digits plus the letters A-F. I like solving Su Doku puzzles (if ‘like’ is the word – they absorb my attention almost to the point of a fugal state) but I’m too cheap to buy the paper just for this one. I’m intrigued, though; I wouldn’t have thought the larger scale would make much difference to the difficulty of the puzzle, all else being equal, but it’d be interesting to find out.

Um… any Indie-readers with scanners out there?

nach0king

If you like Edel, and have access to a SNES emulator, download “Picross” ROMs from:

http://www.cherryroms.com/ (requires free registration)

p.s. I was here for the electoral map; excellent work on that.

Andy

Puzzler Media call Edel puzzles Hanjie, and publish books of them monthly. They’re only available at WHSmiths, and you can get normal sized or “sumo sized”. See here:

http://www.puzzler.co.uk/D/D1X00000.asp?id=TSU&user=null

(taken out of a frameset, since I couldn’t link to it otherwise.) The puzzler.co.uk website has a couple of sample puzzles you can play online as well.

I think that they used to refer to these puzzles as “Tsunami”; if that’s the case, they may have renamed them after recent events in Asia.

Will Guthrie

Edel puzzles are also called Griddlers. They are published in The Sunday Telegraph and there are many books out in the puzzle section of most bookstores.

The main difficulty in completing the new ‘super’ Su Doku is in keeping all that new information in your head if, as I do, you solve them without writing any notes.

Jamie GUTHRIE

Nice article, but my main reason for posting is that someone has posted with the same surname as me! “Will Guthrie” – wow. Not many Guthrie’s around.

Sorry for the rather off topic posting, but I am amazed at the coincidence of this :)

Sarah

Do you think there are fewer Will Guthries than there are Dave Gormans?

Will Guthrie

I don’t know but it would be fun finding out!

My brother’s name is James Guthrie by-the-bye. So close but so far Jamie!

Will Guthrie

Sarah’s question fascinated me and I couldn’t leave it alone…

I decided to do some reasearch…

My first thought was to look in the phone book. How many Guthries are there? How many Gormans are there? Then using statistics on the first name and a bit of extrapalation I could work it out – I’m a mathematician ( not a good one but one none the less) so it didn’t seem that hard.

In the phone book it turns out there are three Guthries and two Gormans. This didn’t look good. It wasn’t enough to find out if there were more or less: I wouldn’t to be more unique. I also knew that my family wasn’t registered in the phone book – and there are five of us. So so far I had at least eight Guthries to two Gormans – not looking good. Now as it happens one of those Gormans happens to be Dave Gorman’s mother – incredible (he went to the same school albeit a couple of years earlier).

Now if the trend was to continue (that is eight Guthries to two Gromans) across the country then I would be stuffed; there would be more of me and less of him: I would be less unique.

However, a thought struck me: when I went to see Dave Gorman at the Surgery in his (and my) home town of Stafford he had said about a website called http://www.yournotme.com. I decided to check it out.

I typed in my name and waited for the results: 86. Brilliant there are 86 people out there in the UK with my name. Is that good? I didn’t know. I typed in Dave Gorman and… 0. There are no people called Dave Gorman. I thought ‘ but I know one’. Then I realised I knew noone called DAVE Groman, but I did know one called DAVID. I typed it in, pressed enter and bang: 146. Yes. I’m more unique!

So in answer to your question Sarah there are more Dave Gormans than William Guthries in the UK. Worldwide? I can only guess, but I hope so

Not being too rude, but you possibly couldn’t take this to GuthriesReunited.com, or somewhere like that?