World's Hardest Sudoku

jones_supa writes "A Finnish PhD in mathematics, Arto Inkala, has allegedly created the world's toughest sudoku puzzle. 'There's no straightforward way to define the difficulty level of a sudoku. I myself doubt if this is the hardest in the world, but definitely harder than my previous ones,' Inkala sets off humbly. The news agencies around Europe are nonetheless excited (Google translation of Finnish original). The particular difficulty in this version lies in the number of deductions you have to make in order to fill in a single number on the grid. 'It is a common misconception that the less initial numbers, the harder the puzzle. The most challenging ones have 21-25', the creator adds."

Comments

Re:Easy peasy

[havarh]

brute force != solving a sudoku

You can't brute force a sudoku, it would take about 1450 billion years using a super duper computer using only brute force. But you could use different solving techniques. Quote Peter Norvig:

"First, we could try a brute force approach. Suppose we have a very efficient program that takes only one instruction to evaluate a position, and that we have access to the next-generation computing technology, let's say a 10GHz processor with 1024 cores, and let's say we could afford a million of them, and while we're shopping, let's say we also pick up a time machine and go back 13 billion years to the origin of the universe and start our program running. We can then compute that we'd be almost 1% done with this one puzzle by now." http://norvig.com/sudoku.html

Re:Easy peasy

[1s44c]

brute force != solving a sudoku

Actually it is. All search is an exercise in brute force with the problem space reduced by heuristics. The trick is to reduce the problem space to as small as possible by using good heuristics.

Re:Easy peasy

[mwvdlee]

When people say "brute force", they don't necessarily mean complete randomness.
It's trivial to check whether a state is valid. For instance, if you have two identical numbers in one 3x3 square, row, column or diagonal, you can ignore the rest of that branch.