January/February issue of acmqueue


The January/February issue of acmqueue is out now


Curmudgeon

Development

  Download PDF version of this article PDF

Anything Su Doku, I Can Do Better

The new puzzle craze from japan is sweeping the world, and testing our Boolean logic.

Stan Kelly-Bootle, Author

I dedicate this essay in memoriam to Jef Raskin (March 9, 1943 - February 26, 2005.) Many more authoritative tributes than I can muster continue to pour in, and no doubt a glorious Festschrift will be forthcoming from those who admired this remarkable polymath. “Le don de vivre a passé dans les fleurs.”

By a quirk of fate that Jef would have loved, IBM announced the death of OS/2 during the week he died. Or rather, it released what PC World called “an official roadmap to the demise of OS/2.” One imagines a GPS intoning, “Hang a left, then straight for six months. Watch out for road-bumps. Stop at the Stop sign. Your journey is over. Abandon your vehicle. Thanks for your custom and patience.”

The sad news of Jef Raskin’s demise reached me via an obituary in the London Times. Mature readers1 make this section of the Times our first page-of-call each morning, and having been assured that we have survived another day,2 dash off the crossword (a convenient four-minute egg-timer). But there’s no fast break these days for problem solvers: we now face the new, addictive quiz, the diabolical fad known as Su Doku (http://www.sudoku.com). The game comes from Japan, though it shares some traits with Western puzzles such as Latin and Magic Squares.

I’m told that, unlike the arcane literary acrostics of the Times crossword, the symbolic/logical Su Doku is totally computable (although not every puzzle has a unique or any solution). The virgin grid is a 9x9 matrix subdivided into nine 3x3 cells. Some of the 81 cells are pre-assigned with integers 1-9, leaving you to assign integers to the blank squares. Every row and column and every 3x3 box must contain exactly the digits 1-9 without repetition. This sounds like a numerical problem. In fact, it’s Boole-on-a-motorbike logic with dangerous curves. Any nine distinct symbols could be used, and some alphabetic versions have been mooted. The nine letters B to L, omitting the vowels E and I, have been suggested for Anglophones, lest some naughty sequences emerge accidentally. “Some Aspects of Consonantal Imprecation,” as a useful Ph.D. thesis, would have delighted Jef Raskin’s love of wordplay.

The crux of Su Doku is which squares are initially assigned with which numbers as “clues” by the problemists. We assume that these clues do not break the rules against repetitions. Given too many clues, the puzzle may turn out to be trivial. With, say, 81 legal clues, you have a null game, known by the insensitive as the “One-piece Polish Jigsaw Puzzle.” Given no clues, of course, the problem has so many solutions that the term “approximately infinite” can be forgiven. The upper limit is (9!)9, the number of all possible grid entries including illegal configurations. Sourendu Gupta and others (http://theory.tifr.res.in/~sgupta/sudoku/expert.html) have calculated the real total to be 6,670,903,752,021,072,936,960!, where the author’s final “!” is an exclamation, not a factorial! (No doubt the mathematical genius Ramanujan would spot something significant about this number. All I can hazard is that this string of 22 digits will occur somewhere in the decimal expansion of pi. Prove me wrong.)

Note that this is the total number of possible Su Doku solutions. The number of legal puzzles is much larger but not yet known precisely. Different clue dispositions can give rise to the same solution, and many conjectures remain unresolved. For example, 17 is believed to be the minimum number of clues needed for a soluble Su Doku. Most published puzzles have from 26 to 42 clues. Generally (with exceptions), complexity decreases as the number of clues increase, and to reduce “Su Doku rage,” the Times rates them as Very Easy, Easy, Moderate, Difficult, and Fiendish, together with a humiliating time-to-complete estimate. Then, there are debates on which puzzles, known as “satisfactory,” can be solved by pure logic without trial and error. Nevertheless, the supply of these “satisfactory” puzzles is effectively inexhaustible—a godsend since Su Doku is appearing in more and more newspapers, magazines, and Web sites, and whole books are dedicated to the craze. Be warned, Yanks: Su Doku has already infected the New York Post.

Creating a nontrivial Su Doku problem by hand is extremely taxing. The danger of producing one with multiple solutions (or none) is greatly reduced by computers, yet there remain some noncomputable, artistic aspects that reflect the Japanese sense of beauty through symmetry. Placement of clues and avoiding too many dependent clues (that is, clues that can be readily deduced from the other clues—a concept mirrored in axiomatics where the goal is a set of consistent, independent axioms) take on a mystic quality. This explains what I used to consider marketing hype: the Times claims that its puzzles are aesthetically superior. Certainly Wayne Gould, the New Zealander who popularized Su Doku worldwide, spent years in the Orient perfecting the programs that generate the Times’ puzzles.

Since a computer generates the puzzle, surely a computer can solve it—end of fun. Yet, so far, the software I’ve seen seems only to aid the solver, except in simple situations when a full solution is produced. Each blank you complete triggers a fresh iteration of the grid, and perversely, the order in which you fill some blanks can alter further progress. You can reach the proverbial “hello wall” where several blanks have apparently unresolvable alternatives. I suspect that, as with chess, algorithms do not yet capture the pattern-recognition abilities of the human brain. Already, those prodigies who can fix the Rubik Cube behind their backs, or mentally extract the 13th root of a very large number, can be seen completing the most fiendish Su Dokus at the speed of light.

Most Brits prefer to muddle through with pencil and eraser. Then there’s that masochistic frisson when you are down to a few blanks only to discover that they do not admit of a solution—whence the eraser for frantic “undo/redo” sequences. On a divine point of English etiquette (Britiquette?), one Times reader sought advice on what to do if you notice that the stranger next to you on the train has entered two 5s in the same column. The consensus is to avoid kibitzing,3 a nasty foreign habit.

There’s certainly a Brit gamespersonship that would resist automated solutions. As Kipling, or one of that crowd, once said: “It matters not who won or lost, but that we played the game.” Shun the “mindless” algorithms. Rather, show how effectively your brain’s natural Boolean sieves can perform.

The perfect exemplar is the “non-game” called, inter alia, Mornington Crescent. Any number of contestants can play together with an umpire whose decision is final and subject to the usual bribes. In turn, each player must name a London Underground station not previously named during that session. A valid, challenged repetition or ineligible name (this includes the null response) leads to your sudden-death exit. An invalid challenge, if validly challenged and accepted by the umpire, also dismisses the false challenger. The winner is the last survivor or the first to name Mornington Crescent! When we played this game at Cambridge in the 1950s, there was usually an irony-deficient foreign contestant who, on the initial round, would shout, “Mornington Crescent! Ach so—wo ist unser Preis?” Groans all round!

Reader challenge: Is Mornington Crescent computable? The number of London Underground station names is finite, so a repetition is inevitable in the absence of a premature “winning-loser.” Yet, as in chess, repetitions must be validly challenged (considered unsporting?) or else the game can, in theory, continue until the beer runs out. The real trad-Brit, face-saving winner must wait until Mornington Crescent is the last surviving unnamed station. Even then, it must be said with profuse apologies. Q

REFERENCES

  1. Allowing for rare errors such as the premature obituary that led Winston Churchill to declare, “Reports of my death have been greatly exaggerated.” As, possibly, are the reports of this too-good-to-be-false anecdote.
  2. The overloaded abbreviation EOF can be read as both end of file and extremely old fart.
  3. From the Yiddish kibits’r, a meddling onlooker. They peer over your shoulder as you program, and say, “You’ve got a dangling else on line 5.” The sublime New York Yiddish Gilbert & Sullivan Opera Society has managed to “translate” The Pirates of Penzance. The original pilots-cum-pirates becomes rabbis-cum-robbers. The mock-patriotic “I am an Englishman” is rendered “Ich bin ein gute Yid” (which, of course, is not offensive in Yiddish).

STAN KELLY-BOOTLE (http://www.feniks.com/skb/; http://www.sarcheck.com), born in Liverpool, England, read pure mathematics at Cambridge in the 1950s before tackling the impurities of computer science on the pioneering EDSAC I. His many books include The Devil’s DP Dictionary (McGraw-Hill, 1981) and Understanding Unix (Sybex, 1994). Software Development Magazine has named him as the first recipient of the new annual Stan Kelly-Bootle ElecTech Award for his “lifetime achievements in technology and letters.” Neither Nobel nor Turing achieved such prized eponymous recognition. Under his nom-de-folk, Stan Kelly, he has enjoyed a parallel career as a singer and songwriter.

acmqueue

Originally published in Queue vol. 3, no. 10
see this item in the ACM Digital Library


Tweet



Related:

Ivar Jacobson, Ian Spence, Ed Seidewitz - Industrial Scale Agile - from Craft to Engineering
Essence is instrumental in moving software development toward a true engineering discipline.


Andre Medeiros - Dynamics of Change: Why Reactivity Matters
Tame the dynamics of change by centralizing each concern in its own module.


Brendan Gregg - The Flame Graph
This visualization of software execution is a new necessity for performance profiling and debugging.


Ivar Jacobson, Ian Spence, Brian Kerr - Use-Case 2.0
The Hub of Software Development



Comments

(newest first)

Leave this field empty

Post a Comment:







© 2017 ACM, Inc. All Rights Reserved.