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.
