Latest revision as of 13:38, 12 February 2006

How does the following program works

Solves all sudoku puzzles for you

Lots have been said and discussed about solving Sudoku puzzles automatically.

The program above works in two modes .

It first creates a list of possible entries for all the empty squares. (1 loop in each dimension of the 3 dimensions , horizontal, vertical and within the block)

If then searches for the square with the least possiblities and spawns X new sudoku puzzles with N-1 unknow squares where N was the nr of unknown squares of the previous Puzzle.

These X puzzles are then recursively analysed again

flow

1. 3 dimension check of puzzle with N unknown
2. search for one of the squares with the lowest amount of possibilities
3. spawn X puzzles with N-1 unknown entries
4. check if puzzle is solved ==> if yes print out and exit
5. feed them to this algorithme again

articel in Spectrum

Sudoku Science By: Lauren Aaronson

Millions of people around the world are tackling one of the hardest problems in computer science—without even knowing it. 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.

Sudoku has become a worldwide puzzle craze within the past year. Previously known primarily in Japan, it now graces newspapers, Web sites, and best-selling books in dozens of countries [see photo, "Number Fad"]. A puzzle consists of a 9-by-9 grid made up of nine 3-by-3 subgrids. 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. 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. 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. No matter the difficulty level, however, a dedicated puzzler can eventually crack a 9-by-9 Sudoku game.

Sudoku has stirred up tremenDous interest in mathematics generally, especially among youngsters. "i mean, it's cool to play sudoku" A 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 [see puzzle, "Challenge"]. 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. And no one knows of an algorithm that's guaranteed to find a solution without trying out a huge number of combinations. 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. (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.)[see puzzle, "Key"]

As 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. 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.

Sudoku has already led some researchers to concrete advances in algorithm design. 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. 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. Solving a particular grid might not be inherently time-consuming, Gomes saw, but might just call for a slightly different approach.

Now many state-of-the-art hardware verification programs incorporate Gomes's findings. "The idea is, basically, you run your program, and if it's taking too long you restart it" with a new ordering, Gomes says, "because your computer may end up getting into an unlucky run, and hopefully the next run will be a lucky one." Gomes hopes to further improve algorithms by studying how people combine various rules and patterns when they play Sudoku.

Sudoku follows in a long tradition of artificial intelligence research on games, most notably chess. But some of AI's most important advances stem from more modest games. 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."

Could the Sudoku craze end up leading to breakthroughs in computer science? Perhaps, one way or another. "I'll tell you one of the things that is important for engineering," says Michael Mepham, a puzzlemaker in Great Britain whose Sudokus appear in The Daily Telegraph and The Los Angeles Times. "And that is the interest that Sudoku has stirred up in math generally, especially amongst youngsters. I mean, it's cool to play Sudoku."