Sudoku. Nobody knows exactly how to pronounce it, but almost everybody 
knows what the rules are. And each person has their own Special Method 
for playing it.

Apparently it's actually a graph colouring problem. Or, equivilently, an 
exact cover problem. And it's provably NP-complete. (So, uh, how come 
it's solvable then? I thought "NP-complete" is supposed to mean 
"impossible to solve in less time than the age of the universe"?)

It appears you can theoretically solve it using the dancing links algorithm.

Post a reply to this message