Slashdot Mirror
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."
You mean easy for your sudoku-solver ?
You don't have to use brute-force solvers. I wrote one that codified my thinking processes and the rules I was operating buy, so that it solved them the way I would.
It's still sorta cheating, but it's not a brute-force.
Who cares about the Higgs boson?
Sudoku is real science!
brute force != solving a sudoku
Yes it is. It's a totally pointless activity, but you have certainly solved it if you end up with the right answer.
If someone asks me what is the next number in the sequence 1, 4, 9, 16, 25 and I say "36" that is the correct solution whether I knew it, guessed it or worked it out in any way whaatsoever.
To have a right to do a thing is not at all the same as to be right in doing it
The following crappy solver I cobbled together solved it in 33 seconds under Cygwin:
https://github.com/fhstoica/NumbersAndLettersSudokuSolver
Check out Peter Norvig's web site for a very elegant solver and look for the "impossible puzzle" if you really want a difficult one:
http://norvig.com/sudoku.html
"'It is a common misconception that the less initial numbers..."
When you have discrete, countable units, such as the symbols, in this case numbers, already present on the Sudoku grid, you have more or you have fewer .
When it's something you can't count, you have more or you have less.
I have more 16x16 grid sheets printed up for hexadecimal Sudoku, because those are the ones I copy from 'the net'.
I have fewer (currently none, actually) of the 9x9 (4 to a page) printed because I quit doing the 1-9 version sometime back.
I'm going to try this one out, but suspect it will turn out to be the type that lets you get just so far with logic and then leaves you no alternative but trial and error, just like the Saturday ones in a certain Raleigh newspaper.
I see even classic Slashdot is now pretty much unusable on dial up anymore.
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
see you in 5 minutes after you realize it actually is kinda hard
If he's anything like my son he'll not come back until he's solved it - or has to be dragged away from it!
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.
Definitely not one of the hardest sudokus.
There is a tool to compute the difficulty of a puzzle, and you can also download a massive database of hard sudokus (5 millions+):
http://code.google.com/p/skfr-sudoku-fast-rating/
For reference, this one is rated 10.7:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-420.html
BTW, there is a database of 31804 puzzles of difficulty 11 and above:
http://gpenet.pagesperso-orange.fr/downloads/hard11.zip
Exactly 7 have a rank of 11.9.
maybe i'm a super programmer then, since i wrote a brute force sudoku solver in 10 min that can solve sudokus in max 100ms on my aging laptop.
Wealth is the gift that keeps on giving.
also, google goggles solves the sudoku using google's servers, not your phone. so it doesn't matter that you used an s3.
Wealth is the gift that keeps on giving.
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.
Slashdot social media options: AIM, ICQ, Yahoo, Jabber and Mobile Text. Why no MySpace?
It's even easier if you click the link at the bottom of the Telegraph website that says "answer"
http://www.telegraph.co.uk/science/science-news/9360022/Worlds-hardest-sudoku-the-answer.html
This post contains benzene, nitrosamines, formaldehyde and hydrogen cyanide.