THIS BLOG HAS MOVED AND HAS A NEW HOME PAGE.

February 01, 2006

Sudoku and scientific research

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 9x9 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.

Trackbacks

Trackback URL for this entry is: http://blog.case.edu/singham/mt-tb.cgi/5595

Comments

I love Sodoku puzzles and was particularly excited when one of the girls I nanny for brought some home from her math class. She's in the second grade, and the puzzles she were given were simplified to an appropriate level, but it was great to see her using her deduction and logic to solve the problem, and fun to share the strategies I use to solve them. I hope more schools are using this type of resource to excite and stretch younger minds.

Alyx

Posted by Alyx on February 1, 2006 01:46 PM

Sudoku was one of my fastest addictions - both in taking hold and in losing interest entirely. Once I realized that solving the puzzle required nothing more than patience and a little logic, I lost the challenge.

Theoretically, the only thing that can separate one player from another is speed of completion, and I was usually attacking these in my leisure and not trying to rush.

While I enjoyed your analogy to scientific research, it is possible to solve any sudoku puzzle without ever having to guess an entry.

I do find the mathematics behind the creation of these puzzles fascinating, probably because there are still answers to be found.

Posted by Barry on February 1, 2006 03:06 PM

Barry,

I was intrigued by your comment that "it is possible to solve any sudoku puzzle without ever having to guess an entry." In a strict sense that is true because eventually the puzzle is entirely deductive. But I was thinking that if you could not "see" the contradiction generated by a wrong entry immediately but only down the road somewhat, then I was calling it a "guess".

Am I missing a solution strategy?

Posted by Mano Singham on February 1, 2006 03:22 PM

I do my puzzles from the following two places:

http://www.msnbc.msn.com/comics/games/sudoku.asp
http://puzzles.usatoday.com/sudoku/

Typically I do not have to guess any numbers at all; if I keep looking for numbers that *have* to be correct I'll eventually be able to fill everything in. However, last Friday's USAToday puzzle was the hardest I had ever seen and I eventually gave up. I was only about to get about 4 numbers before I had to start guessing, and that way lies madness. :)

Posted by Shruti on February 1, 2006 04:57 PM

It is clear to me that both Barry and Shruti are using a strategy that I have not figured out as yet, that enables the two of you to solve the puzzles while completely avoiding the need for hypothetico-deductive reasoning.

Posted by Mano Singham on February 1, 2006 06:37 PM

Wow, I have actually never heard of sodoku before, but that is one addictive game. I felt like I was retaking the SATs while I was working on one (but in a good way... I think).

Posted by Katie on February 2, 2006 12:52 AM

In the sudoku community, sudoku puzzles that require 'hypothetico-deductive' reasoning to be solved are generally considered substandard. Many people regard puzzles that can't be solved by direct logic as not true sudoku puzzles at all.

There are a number of advanced direct logic techniques with names like hidden triple, x-wing, swordfish. There's a good explanation of them here: http://angusj.com/sudoku/hints.php

Sites like Fiendish Sudoku have puzzles in a range of difficulties right up to extremely hard, but always solvable with direct logic. In other words, you never have to say "let's try a 4 here and see if we get a contradiction".

If you want a true challenge, take a look at the puzzles here: Samurai Sudoku. Again, there's always just one solution reachable with direct logic.

KristinW
sudokulinks.com

Posted by KristinW on February 2, 2006 04:21 AM

Katie,

You had never heard of Sudoku? I had heard that it was all the rage on college campuses.

KristinW clarifies a lot of things. Maybe the one in the Plain Dealer (which are the only ones I've done) are occasionally substandard as she described. The Samurai Sudoku looks pretty intimidating and poses the essential question: How much time can I devote to this hobby?

But the appeal of a purely deductive logic solution will probably draw me in...

Posted by Mano Singham on February 2, 2006 10:02 AM

I'm not up on the actual strategies, I just play by instinct. I tried guessing when I first started playing, and the inevitable backtracking drove me insane. It takes a little more patience, but I just prefer not writing anything down until I'm 100% sure.

To try and sum up my strategy, my thought process:
This row needs a 4. The 4 can't be here because this box already has a 4. It also can't be there because that column has a 4.

And so on. The harder puzzles require longer rationalizations, but there's always an answer.

I've mainly played the MSNBC puzzle online, but I've never been stumped as long as I keep at it.

Posted by Barry on February 2, 2006 02:48 PM

I'm a college student studying criminal justice. One of my classmates was telling about a bizarre series of homicides
from the 1970's. I never heard of it before and I was wondering if anyone had more details about the case.

The case involved the murders of three or four university students. The girls returned to their dorms after classes. A man would hide in their dorms and when they would step inside he would grab them and first thing he would put a plastic bag over their heads and suffocate them to death. In one case he would smother the girl with a pillow. He would only attack girls wearing mini-skirts and pantyhose. After he killed them he would remove their pantyhose and keep them for a trophy. Since his signature was always the removal of his victims pantyhose he was referred to as a pantyhose killer or in some cases called the mini-skirt killer.

He did not rape his victims, they were found fully clothed except for their missing pantyhose. I am curious about more info in this weird case. Thank you.

Posted by Sherill jones on February 6, 2006 04:41 AM

Sherill,

I am sorry, I have never heard of this story. Perhaps some other readers of this site can help.

But here's a suggestion of how to find out more. The New York Times has put its entire history of newspapers in an online database. Your college library is sure to have access to it. Your best bet would be to ask the reference librarian to help you with a search of this source.

Good luck!

Posted by Mano Singham on February 6, 2006 10:08 AM

I love this blog. I myself have a special interest in Web Suduko

Posted by web suduko expert on January 29, 2008 06:25 PM

Hello everybody,
I have to write a technical report on Sudoku game.
Can anyone help me out, where can i find articles, journals or previous research paper on Sudoku game.

please help me and email me for any info.

regards,
Harsh.

Posted by Harsh on September 17, 2008 01:36 AM

Harsh,

I suggest that you look at the American Scientists article referred to in the post.

Posted by Mano on September 17, 2008 08:28 AM

Sudoku is one addictive game i can tell you.
I mostly like samurai sudoku because it's a real challenge for me.
The harder puzzles require longer rationalizations, but there's always an answer.
You can find lots of printable sudoku's at http://www.printablefillinpuzzles.net free of charge.

Posted by Printable Puzzles on November 23, 2008 09:16 AM

Hi i just love solving sudoku puzzles,for those that enjoy sudoku, theres Gemsweeper,a nonogram puzzle game from http://www.lobstersoft.com. Nonograms are picture logic puzzles, whereby you have numerical clues,bit similar to sudoku.
Gemsweeper is based o restoring an ancient mayan temple via 225 puzzles available.Easy to learn with the help of a tutorial. Game has colourful graphics.Nice soft background music was a plus.
Great way to test your logial skills.Ideal for kids as well.

Posted by karin on January 5, 2009 11:28 AM

I've been amazed at how fast the programming community is pushing ahead with ever more complex techniques for solving sudoku puzzles....and yet I still see loads of people unable to get a start on the techniques involved.

I found a site that goes from the basics up for people that want to do these puzzles and become a sudoku solver in their own right without using a computer.

Martin

Posted by Martin on July 2, 2009 09:39 AM

Oh sudoku is definatly hee to stay, every day more and more daily sudoku puzzles sites. Personally I think it's a good thing sudoku has alwasy been know as a great way to relieve stress

Posted by webceo on November 17, 2009 06:12 AM

My Sudoku Strategy techniques would be severely tested if I attempted all of the possible 5,472,730,538 uniquely different Sudoku puzzle grids mathematicians Frazer Jarvis and Ed Russell have counted. It does not seem much but if you just do one puzzle a day it would take you just over 14,993,782 years to complete all of them.

I don't think that I could hack that!

Posted by Sudoku Strategy on February 26, 2010 05:23 PM

i really never liked Sudoku was one of my fastest addictions but i think the article is good

Posted by arnel on April 7, 2010 02:31 AM

I love sudoku! I've been playing it for a few years now, (i run a driving school) and i play it to pass the time between lessons.

Posted by Jonny on April 18, 2010 12:21 AM

I have found one alternative method to solve any sudoku, this is wonderful mathematics based method, I want someone to review it, please advise whom I can sent it and get it publish...

Posted by harsh goel on October 12, 2010 10:46 AM

I think sudoku may have peaked in popularity in the United States around 2009. I have no actual facts to know for sure, but it just seems that way to me. It is still published everyday in my local newspaper. But, you have to wonder if newspapers themselves are going out of style. Hopefully, that will never happen.

I have also been curious as to what the minimum given numbers could be for there to be only one definite solution. You mention in your article that, although not yet proven, the answer seems to be 17. That still seems to be the case, at least according to Wikipedia's Mathematics of Sudoku.

Personally, I am very fond of the game myself. I always try to first put in numbers that I am 100% sure are correct, but there always seems to be a crucial part of the game where you are less than 100% certain and you sometimes have to trust your intinct. Of course, with sudoku you cannot afford to make a mistake because one mistake leads to another.

I have a game review blog. One of the many games I reviewed is a game named Sudoku Challenge. I had hoped it would have been one of the more popular games on my site, but so far it hasn't really caught on. But, who knows. Trends change. So, hopefully someday it will.

Posted by Richard on April 29, 2011 07:26 PM

I'm currently studying to get a master in information assurance and these sudoku puzzles are what gets me through the day when waiting for class.

Posted by kevin on May 3, 2011 12:14 PM