![]() Gomes realized that a computer can take either seconds or eons to solve the very same puzzle-and that this drastic difference depends on something as simple as the order in which the computer considers cells in the grid. At the Intelligent Information Systems Institute at Cornell University, Ithaca, N.Y., director Carla Gomes experiments with Latin Squares, a version of Sudoku without subgrids. Sudoku has already led some researchers to concrete advances in algorithm design. Although most experts believe that no such algorithm exists, they continually search for improved algorithms that provide shorter, if not the very shortest, paths to solutions. (For example, it is easy to verify whether a complete Sudoku is correctly filled in, even though the puzzle may take quite a lot of time to solve.)Īs a member of the NP-complete subset, Sudoku is an ideal tool for investigating the whole class of NP problems: an efficient algorithm for any NP-complete problem-the toughest of NP problems-automatically provides an efficient algorithm for solving all. The challenge is known as P = NP, where, roughly speaking, P stands for tasks that can be solved efficiently, and NP stands for tasks whose solution can be verified efficiently. “The question of whether there exists an efficient algorithm for solving these problems is now on just about anyone’s list of the Top 10 unsolved problems in science and mathematics in the world,” says Richard Korf, a computer scientist at the University of California at Los Angeles. Sudoku has stirred up tremendous interest in mathematics generally, especially among youngsters. This places Sudoku in an infamously difficult class, called NP-complete, that includes problems of great practical importance, such as scheduling, network routing, and gene sequencing. And no one knows of an algorithm that’s guaranteed to find a solution without trying out a huge number of combinations. On a large scale, however, such shortcuts are not powerful enough, and checking the explosive number of combinations becomes impossible, even for the world’s fastest computers. No matter the difficulty level, however, a dedicated puzzler can eventually crack a 9-by-9 Sudoku game.Ī computer solves a 9-by-9 Sudoku within a second by using logical tricks that are similar to the ones humans use, but finishes much faster. A hard puzzle requires more complex pattern recognition skills for instance, if a player computes all possible digits for each cell in a subgrid and notices that two cells have exactly the same two choices, those two digits can be eliminated from all other cells in the subgrid. An easy puzzle requires only simple logical techniques-if a subgrid needs an 8, say, and two of the columns running through it already hold an 8, then the subgrid’s 8 must go in the remaining column. Digits appear in some squares, and based on these starting clues, a player completes the grid so that each row, column, and subgrid contains the digits 1 through 9 exactly once. A puzzle consists of a 9-by-9 grid made up of nine 3-by-3 subgrids. Previously known primarily in Japan, it now graces newspapers, Web sites, and best-selling books in dozens of countries. ![]() Sudoku has become a worldwide puzzle craze within the past year. The logic game Sudoku is a miniature version of a longstanding mathematical challenge, and it entices both puzzlers, who see it as an enjoyable plaything, and researchers, who see it as a laboratory for algorithm design. Millions of people around the world are tackling one of the hardest problems in computer science-without even knowing it. Number Fad: A reader examines a Sudoko puzzle in
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |