11 Comments

Summary:

A team of University of Notre Dame researchers has developed an algorithm for solving Sudoku puzzles that doesn’t require it to guess at all. Rather, it’s able to discern patterns even with sparse available information and automatically determine which numbers go where.

Sudoku-by-L2G-20050714.svg copy

After a long day’s work, being cramped up in the middle seat on a flight from San Francisco to home to Las Vegas is bad enough. The last thing I need is to feel stupid, as well — which is exactly how I’d feel if I were struggling through a medium-level Sudoku puzzle while the guy sitting next to me breezed through it in a matter of seconds. It’s a good things humans don’t have computer chips as co-processors (yet), because a couple of University of Notre Dame researchers have developed an algorithm designed to make short work of Sudoku puzzles.

It’s easy: just fill in the blanks …

The most-impressive part of the algorithm is that it doesn’t have to guess at all. Whereas most humans solving difficult Sudoku have to use “brute force” techniques that involve testing out every possibility before filling in a square, the new algorithm just identifies patterns and fills in the correct numbers every time. Anyone who has tried solving a puzzle rated “difficult” knows just how challenging, nigh impossible, that task can be.

It’s not clear if the researchers have considered specific extra-Sudoku applications for their solving algorithm just yet, but knowing how Sudoku works might give scientific or commercial researchers some ideas. A difficult puzzle will provide a minimal amount of information, just a few seemingly random spaces filled in, but the rules regarding each space, row, column and 3-by-3 region mean there’s only one correct way to complete the whole puzzle. Applying such an algorithm to systems with similar rules in place could mean even faster prediction of how those systems will evolve or what shape they’ll ultimately take.

Image courtesy of Wikipedia Commons.

You’re subscribed! If you like, you can update your settings

  1. Umm… guessing and brute force are not required to solve Sudoku at all. To get the truly difficult ones done, you have to determine which squares are solvable first and then work your way through. It is completely algorithmic if you have really learned how to do the puzzle.

    1. That’s a good point, although I would argue most casual Sudoku puzzlers aren’t at that point yet. Simple rules work with easy puzzles, but not with the harder puzzles where there’s less data. I presume the real application of this will be in areas where we want to predict the behavior of more-complex, but rule-based systems.

  2. As an everyday sudoku solver I have to agree with Matt, if you have to guess your missing something.

    1. Like an apostrophe + “re”?

  3. You have this backwards: Researchers likely used existing methods to solve Sudoku. I was taught methods in 1975 at the University of Illinois that would make quick work of Sudoku puzzles. They’re for computers, though, and not feasible for humans to use.

  4. I developed a computer program that can solve any Sudoku puzzle I have encountered. It just mimmicks the way I solve them, using logic–if this then that. It likely is not as sophisticated and ingenious and creative as the solver done by the team of researchers. I am ready to believe that their solution may lead to further technological advances in medicine and space travel. Mine? Once I proved to myself that it would work on any Sudoku puzzle, I left it on the trash heap of personal achievements that no one in the world gives a damn about and continued solving the puzzles by hand. For the life of me, I cannot imagine how people can solve the evil level puzzles in mere seconds. But someday I will figure it out.

    1. Ha. Thanks for the comment.

    2. I did exactly as jfkliberal did. I did so many Sudoku puzzles that I realized the algorithm in my head, then coded it up just as an exercise. After verifying it was correct, I Googled and found that lots of other people had already created automated Sudoku solvers. It wasn’t much of an accomplishment and it went into the bit bin quickly, but I still get to brag about it whenever a friend is doing a Sudoku.

  5. A computer using logic to solve sudoku puzzles is hardly novel…I built a program in excel that uses all the logical techniques to solve sudoku puzzles so that if I ever got stuck I could figure out what I was doing wrong…of course all I have to do is loop the various techniques together and I can watch excel solve the full puzzles…

  6. It’s hardly novel to solve a puzzle without guessing. I built a program in excel using all the typical (and a number of rather atypical) logical techniques so that if I got stuck on a difficult puzzle it could highlight what I was doing wrong…solving the entire puzzle after that was merely a method of looping through the techniques. I’m sure this algorithm is significantly more advanced than mine was, buit’s still fun to now and then pull the program up and let it solve a puzzle while I watch.

    1. Very cool. I suspect you’re right about the sophistication of this algorithm. Sudoku is a fine early proving ground, but hopefully its utility expands beyond just puzzles.

Comments have been disabled for this post