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.
