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 ?
I'm printing it out now, nothing like someone claiming the impossible to make you want to try and prove them wrong.
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
Some excellent news about the Higgs particle is announced more than 0.5 hr ago, I come hear to Slashdot to read what everyone has to say.....and the font page headline here is about motherfucking Sodoku. Really? Are the editors asleep, apathetic or all of the above? Fuck.
"'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
http://www.theonion.com/articles/caltech-physicists-successfully-split-the-bill,2037/
I am putting you all on sudoku watch.
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.
You have to find the simplest rule/law that describes the given numbers and use that to predict the next numbers.
Simplest rule, eh? The answer to everything is 42. Solved!
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?
One reason that you cannot solve this puzzle without making assumptions is that it has more than one solution!
One of the comments in the FA provides a solution to the puzzle, which is different from the solution I found using a sudoku solver that I wrote back when I realized that I was spending too much time on these puzzles.
When stuck, my solver starts selecting random values among the valid possibilities, backtracking if the guess does not lead to a solution. This makes it possible for the solver to solve puzzles that don't have enough (or any) numbers to solve the puzzle deterministically, producing different answers each time it is run on such a puzzle. I guess this particular puzzle is one such incomplete puzzle, as running the solver again, produced a third solution!
I would think that sudoku puzzles with more than one solution are not correct puzzles, so this particular puzzle does not qualify as such.
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.
Seems the easiest way to get those numbers is:
1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 16
5^2 = 25
6^2 = 36