I have always liked logic puzzles. They exercise a curious fascination for me, extending even to my choice of reading. From the time I was very young, I was drawn to mystery novels of the Agatha Christie variety, which are essentially logic puzzles where the identity of the culprit is unknown until the end and the author lays out clues which the careful reader can use to solve the puzzle.

Needless to say, this extended to my choice of board games too, Clue and Master Mind being some of my favorites at one time. I also enjoy chess and card games like bridge, both of which contain a considerable element of puzzle solving.

So it should be no surprise that I have recently become addicted to doing the daily sudoku puzzle in the Plain Dealer. For those of you unfamiliar with this new craze, it is basically a logic puzzle consisting of 81 squares arranged in a 9×9 square grid in which about one-third of the squares contain numbers 1 through 9 from already filled in. The reader is required to fill in the rest containing subject to rules that are simple and can be found here.

The daily newspaper puzzle is labeled gentle, moderate, or diabolical, to indicate the expected level of difficulty, although the labeling does not always match my experience with the occasional diabolical being quite easy and the moderate quite hard.

The sudoku puzzles do not require any mathematics or even arithmetic to arrive at a solution. One could just as well do the puzzle with nine different fruits or symbols or whatever. But there is a lot of interesting underlying mathematics, and Brian Hayes has an interesting article in the January-February, 2006 issue of the American Scientist with a fascinating discussion of the mathematics of sudoku. involving such questions as how many different puzzles there are (Answer: 3,546,146,300,288) and what is the minimum amount of filled squares that must be initially provided so that there is a unique solution. It turns out that the latter question remains unsolved. “[T]he minimum number of givens is unknown. Gordon Royle of the University of Western Australia has collected more than 24,000 examples of uniquely solvable grids with 17 givens, and he has found none with fewer than 17, but a proof is lacking.” So there’s a nice challenge for the mathematically ambitious. Published problems usually have between 25 and 30 givens, with no simple correlation between the number of givens and the advertised level of difficulty.

One interesting question that the article does not answer is how the constructors of the puzzles know when they have given enough information so that there exists a unique solution. Do they have to work through the puzzles themselves and keep adding initial data until they have a unique solution? That seems tedious. In yesterday’s (January 31, 2005) Plain Dealer puzzle, it seemed to me that there were at least two solutions.

(The sudoku problems belong to a more general class of math problems associated with the term NP but there are some disagreements about whether it is NP or NP-hard or NP-complete, which I will leave to the more mathematically informed to figure out.)

After doing a few, it struck me that these puzzles are a good analogy for the way science research is done. Thomas Kuhn in his classic book The Structure of Scientific Revolutions points out that normal scientific research within a paradigm is largely a puzzle solving exercise in which there is an assurance that a solution exists to the problem and that it is only the ingenuity of the scientist that stands between her and a solution. The sudoku problem is like that. We know that a solution of a particular form exists and it is this belief that makes people persevere until they arrive at a solution.

Most of the sudoku solution strategy is deductive. One starts by filling in those empty squares with numbers that can be arrived at deductively, by rigorously ruling out all but the correct number. But in the more difficult puzzles, one reaches a stage where there may be two (or rarely) three possibilities for a crucial square and deductive logic alone cannot determine it. At that point, one has to resort to ‘hypothetico-deductive’ or ‘if-then’ reasoning. This kind of reasoning is an essential element of the scientific process. In scientific research one never knows exactly all the information needed to solve some problem. Hence one has to make reasonable assumptions about some things in order to proceed further and arrive at conclusions. And those assumptions can change in the light of new information.

Sudoku provides an example of this in that when one reaches such an impasse, one simply chooses one of the possible options and proceed to fill in all the rest of the squares using the standard deductive reasoning until either the puzzle is completed satisfactorily, confirming the correctness of the initial choice, or one runs into an obvious contradiction, indicating that one’s choice was mistaken and that one should have chosen the other option at the branch point.

In yet harder puzzles, one might encounter nested hypothetico-deductive situations, where after making one choice, one might encounter yet another impasse requiring another choice. Those are the hardest puzzles because they involve selecting between many possible options, each resulting in a different final solution. (As an aside, the mechanism of evolution by natural selection works similarly to this, with the choice options being provided by random genetic mutations and the choice being ‘made’ by natural selection.)

Scientific research is a lot like these harder sudoku puzzles, involving long chains of inferential reasoning, with assumptions being made along the way. One rarely arrives at solutions purely deductively, hence the popular notion of scientific truths being “proven” to be true is largely a mirage. There are always choices that have to be made at intervening stages. One has to make decisions as to what one assumes to be true and can be used as a basis for further investigations. Being able to do hypothetico-deductive reasoning is essential for science, and yet it is not skill we focus much on in our science teaching.

In doing this kind of hypothetico-deductive reasoning one also has to use one’s judgment and select which of the various possibilities is likely to be the most fruitful. Science also requires one to make such judgments and good scientists are those who, over time, develop a good ‘nose’ for which situations are best suited.

The extra wrinkle in scientific research that is not present in sudoku puzzles is that the correctness of the choice is also time-dependent. What may be a satisfactory choice at one time may turn out, in the light of subsequent research in a related field, to have been the wrong choice later. It is this kind of thing that causes the scientific community to sometimes reverse itself and declare that what was considered wrong once is now right and vice versa.

The hardest problems in science are those that challenge the very paradigm itself because then one is not guaranteed that a solution even exists. It is like working on a sudoku puzzle in which the data given may not be sufficient to guarantee the existence of a unique solution, or one in which the rules have changed but you are not aware of it. It takes a strong will and a great deal of perseverance to take on such problems. But it is just that kind of problem that leads to scientific revolutions.

POST SCRIPT: Warrantless wiretapping

Tom Tomorrow’s take on the NSA wiretapping story.