Sudoku Science

Posted on February 22, 2007  Comments (0)

Sudoku Science:

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.

“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. 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 route-finding algorithm that powers car navigation systems, for instance, was first demonstrated on the Sliding Tile puzzle, a child’s toy in which a player tries to move 15 tiles around a grid so that their surfaces form a picture. The same algorithm helps video game characters steer through virtual worlds. “This is an algorithm developed back in 1968 in abstract kinds of things,” says UCLA’s Korf, who himself has explored algorithms for the Rubik’s Cube. “It’s used all the time.”

Related: GPS РCar Navigation MapsDonald Knuth, Computer ScientistPoincaré Conjecture
Computer Science Revolution