Sudoku Made Easy with New Algorithm

April 8, 2009

Having trouble with Sudoku puzzles? Retired computer scientist J.F. Crook of Winthrop University, in Rock Hill, S.C., has come up with a search algorithm for solving any Sudoku puzzle, no matter how difficult.

"Sudoku has become the passion of many people the world over," Crook wrote in an article in the April Notices of the American Mathematical Society. The interesting thing "is that it is a trivial puzzle to solve," he said.

Here is the essence of Crook's "paper-and-pencil" algorithm for solving Sudoku puzzles, which involves identifying what Crook describes as preemptive sets.

(1) Find all forced numbers in the puzzle.

(2) Mark up the puzzle.

(3) Search iteratively for preemptive sets in all rows, columns, and boxes—taking appropriate crossout action as each new preemptive set is discovered—until

(4) either

     (a) a solution is found; or

     (b) a random choice must be made for continuation.

(5) If 4(a), then end; if 4(b), then go to step 3.

Even by following Cook's approach, you may still end up with two possibilities for a particular box. Therefore, Cook suggests switching pencil colors when that's the case. If the first guess doesn't pan out, erase it and go to the other option with the other color.

Number theorist M. Ram Murty of Queen's University, who has published theoretical work on Sudoku, said Crook's algorithm follows well-known mathematical approaches to solving puzzles. It codifies what people do unconsciously when they work on the puzzle.

"Sudoku is really just a kind of math in action,"Murty indicated.

Source: USA Today, March 15, 2009, The Herald (Rock Hill, S.C.), March 17, 2009.