Log in

No account? Create an account
27 May 2007 @ 11:16 am
The Art of Sudoku  

In the weeks since becoming world champion of that puzzle with the numbers that's near the crossword in the paper (except in the NYTimes (except online)), I've realized that I am incredibly defensive about how much time I spend solving sudoku. Whenever a reporter asks (assuming my answer must be dozens of hours each week), I always explain, carefully, that I solve lots of different kinds of puzzles, from math and logic puzzles to cryptic crosswords, lateral thinking challenges to pure trivia. That I don't like being known as someone who solves a lot of sudoku may be a response I have to the way sudoku, at least as a commodity publishers have been using to generate profits, has none of the qualities of puzzles I'm proud to either write or solve. That computer generation of the puzzle makes it an essentially zero cost resource for most content-providers has turned it, in its most common form, into the "boxed wine" of puzzles. Bland, generic, mass-produced, not fit for expert consumption. Sure, it might be good for the first few times you get a buzz, but its not a lasting satisfaction.

The symptom of the disconnect between creator and purveyor is maybe best shown in the scanned image below. This came from a Puzzler publication which has now had a couple of framed pictures of sudoku used as advertisements.

Puzzler is a UK company that resells Nikoli puzzles in both the UK and the States. Nikoli, the Japanese innovator of the US puzzle that also renamed it Sudoku, often points out how their hand-made puzzles have unique qualities superior to computer-generated ones. They definitely are one source that hides solving themes in their puzzles, even their sudoku (a recent nikoli.com example is solvable exclusively as singles in 1 to 9 order - ie you look at the digit 1 and can place all 9 instances, then look at 2 and can place all 9 instances, and so on.) However, Puzzler, in trying to remarket the hand-crafted puzzle concept, missed something entirely in this photo. I somehow doubt the photographer or editor understood what can make a puzzle beautiful and worth framing when it seems they barely understand what a sudoku is.

I figured, therefore, that it might be time to collect some of the "close-to-classic" sudoku I've written recently to offer a counterpoint to the thesis that sudoku cannot have developed themes or be an interesting ground for puzzle construction. At the very least, this page will now serve as a great link to point anyone to who wants to see some of the sudoku I've written and understand my view on the possibility of puzzles in general.

The treat at the start of this entry was hand-constructed by me by testing a simple theme. The four offset rings with clear repetition of digits stand out upon first sight. Its not very hard and its symmetry actually strongly compromises its solving if you make use of it, but it certainly is visually impressive.

Computer-assisted puzzle generation itself is not an evil thing. The classic sudoku below (which is fairly hard) started with a theme I wanted to use with the two 1-9, left to right, arithmetic series. I then used some computer-assistance to determine where to place a couple extra givens to reach a valid puzzle. The extra numbers (in the center, and in the two corners) themselves were still chosen from this screening to maintain some extra reflective symmetry and I like the look of this puzzle a lot. It might not stand out as instantly as the first example, but looking at it thoroughly you discover some neat hidden sequences and symmetry. There are clear signs of a human hand at work in this puzzle's construction even if a computer helped in the finishing.

A themed classical puzzle can be as simple as using a relevant shape for the givens (perhaps at the expense of some symmetry). I was asked to write a puzzle for the Harvard Crimson's magazine Fifteen Minutes recently. I used their acronym, FM, and their implied favorite number, 15, as the theme to put together the following puzzle, again just by hand, but it took some time to resolve the bottom of the M to make a unique solution. A computer could have made the process faster, but I was not near one at the time. However, whether computer-assisted or not, the resulting puzzle presents a theme that you will rarely see in the "Jackson Pollock"-like scattering of digits of a truly randomly generated puzzle.

To further develop themes, one sometimes has to change the classic sudoku formula. One simple variation to use that's basically still a classic sudoku is from Conceptis Puzzles, which has "Even" and "Odd" sudoku where a couple cells are shaded, meaning that they can only contain even/odd numbers. I've never understood Conceptis's implementation, as they might shade as many as 4 cells (asymmetrically!), but fill one or two of them in with givens, so that they basically give you a classic sudoku that is non-unique without some shaded "even/odd" squares, but unique with them. It sometimes seems to me more a patchwork for a broken classic than a puzzle on its own right. (On other occasions, the layout of shaded cells is well-done and critical for the logical solution of the puzzle, but this is rarer than it should be.)

As often happens when a puzzle idea seems useless to me, I make counterexamples that satisfy me. In this case I generated a type I call "What An Odd Sudoku!" with two examples. In this variation, the shaded cells must form a graphical theme, and as the title somewhat implies, there is a restriction that only odd digits can go in the greyed cells. One of the examples has the theme of basic arithmetic (1+1=2), the other a theme I've visited before in sudoku form of Tic-Tac-Toe. Both are rich puzzles and the shading, while useful in an artistic sense, is also important in the logical sense while solving here as well. Both were carefully hand-set and I'm particularly proud of the nice work-ins I hid in the "basic arithmetic" one.

There are also rare themes that are impossible to imagine a computer generating on its own. The first puzzle I ever wrote, a geometric sudoku based upon US state shapes, is the clearest example I have in this category. It is very heavily constrained (I needed shapes that fit together, plus states with 9 overlapping letters in their postal abbreviations, plus a valid solution that needed only 18 givens in the appropriate places), but also a visual treat. Here I repost it, for the sake of this entry, as it is a great example of how a theme can be used in a puzzle to generate a piece of "art". As a geometric/jigsaw variant, the "3x3 boxes" are now different shapes except for Wyoming which was always pretty box-like. New York has a special Long Island cell that is separate from the rest of the state which explains its special shading - that and its my home state. The puzzle also uses letters instead of numbers, which might make it harder for some, but it is still fundamentally a sudoku puzzle.

I don't know that these examples will ever change the business model people use to sell the puzzle. I doubt I'll be approached to put together a book on "The Art of Sudoku" nor would I necessarily want to as it takes time to set beautiful classic puzzles and I'd rather develop other puzzle ideas with my limited time. But I do hope, when I point people to this article, and to these puzzles, that people can sense what I mean by the "art" of a puzzle and can understand how puzzle creators (and not computer programs) will always be a vital part of constructing great puzzles. Sudoku may not seem to be the rich thematic ground that a crossword can be, but I contend any puzzle can be constructed in interesting ways if done by a careful and talented hand.
Bram Cohenbramcohen on May 19th, 2007 05:28 pm (UTC)
If one were to write a program where you could specify the positions in a sudoku which should be specified and the computer did the rest of the work of generating the sudoku, would you consider the results to be 'thematic'?
motrismotris on May 19th, 2007 05:50 pm (UTC)
It would be a better starting point for computer generation and there are a handful of constuctors that use computer-design in this way. Whether a sudoku "heart" or "bird" or "flower" or "house" is, after its been done thousands of times, going to seem "thematic" anymore is an interesting question. For consistency, as with nonograms, the answer probably converges to no with time - simple graphical patterns in givens is not enough.

However, your suggested program does come a step closer to how it is a human crafts a sudoku. Typically, the way a puzzle is hand-set is to choose a pattern, blocking out the positions that will become givens, and then slowly identify what the givens are as you pretend to "solve" it without defining all the positions. Unassigned givens can "force" placements provided you indicate they will not be an occurrence of a particular number.
Bram Cohenbramcohen on May 20th, 2007 05:29 am (UTC)
Given that, it's likely that the program would actually make much more 'natural' feeling sudokus in that the ways in which pieces are forced might be a lot less straightforward. It depends a lot on how the program was written, of course.

The only formula of puzzle I know which manages to not exhaust its potential themes is crosswords. Perhaps that gives a hint as to how to be thematic - maybe something which was like nonograms, but where the abstract constraints don't force anything close to a unique solution, and you have to use visual cues to find out the exact solution. Of course, that wouldn't be pure abstract, but finding a neverending list of thematic pure abstract approaches to a single schema of problem appears to be quite a tall order. Unless you simply encode into a standard NP-complete problem, of course :-)

As for standard computer-generated sudoku, I think it's a lot like solving rubik's cube - it's the same puzzle over and over, but still fun for many people to do repeatedly.