World's Hardest Sudoku 179
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."
It's game on then (Score:3)
I'm printing it out now, nothing like someone claiming the impossible to make you want to try and prove them wrong.
Re: (Score:2)
Re:It's game on then (Score:5, Funny)
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!
Re: (Score:2)
Re: (Score:2, Flamebait)
I'm an aspie, as soon as I heard about this I broke out my whiteboards and went to work.
Took me about two hours (including the thirty minutes deciding how best to actually draw the sudoku board). I suppose the hardest part was finding out where to start -- I rummaged through dozens of combinations and tried to deduce a single number, but that method didn't work (didn't have enough colored markers anyway, >:( ).
Re: (Score:2)
Dunno why someone would consider it flamebait. Maybe someone thought I was making fun of aspies?
And I thought I was the one who had trouble understanding people.
Re: (Score:2)
Guess or toss a coin.
Who cares about the Higgs boson? (Score:5, Funny)
Who cares about the Higgs boson?
Sudoku is real science!
Hard? (Score:2)
Of course, I personally, don't even know the rules of Sudoku.
Re:Hard? (Score:4, Informative)
also, google goggles solves the sudoku using google's servers, not your phone. so it doesn't matter that you used an s3.
Re: (Score:2)
Oh the irony!
Re: (Score:2)
Re: (Score:2)
You forgot that each number must be between (and inclusive of) 1 through 9.
And that they all must be whole numbers.
I'll give it a try (Score:1)
Not so hard (Score:5, Insightful)
The following crappy solver I cobbled together solved it in 33 seconds under Cygwin:
https://github.com/fhstoica/NumbersAndLettersSudokuSolver [github.com]
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 [norvig.com]
Re:Not so hard (Score:5, Interesting)
Cool link, thanks!
I love this quote :
Ben Laurie has stated : Sudoku is "a denial of service attack on human intellect".
Re: (Score:1)
I wrote my own solver a few years ago and got this;
812 753 649
943 682 175
675 491 283
154 237 896
369 845 721
287 169 534
521 974 368
438 526 917
796 318 452
I do think you need to work a little on your runtime; ./CSPsudoku hardest.txt hardest_solve.txt
$ time
real 0m0.041s
user 0m0.027s
sys 0m0.008s
Re: (Score:2)
33 seconds? No offense, but methinks you need to review your algorithm, because either you
a) have a bug, or
b) have totally over-engineered the implementation of the algorithm.
My solver in 106 lines of C++ solves it in by *brute* force in less then 1 second. I wrote this back on 6/6/6.
There is also a 141 _byte_ sudoku solver in Javascript that someone else wrote. Check
http://www.reddit.com/r/javascript/comments/ku0mb/tweet_sized_sudoku_solver_in_javascript/ [reddit.com]
My input file is: // stupid lameness f
8-- --- ---
Re: (Score:2)
> The whole point of writing that program was to play around with templates (and SLT/BOOST),
Looking at your code I see that my hunch (b) was right -- it is *totally* over-engineered. There is a time for STL (and that abomination BOOST), but if you want to be a *great* coder focus on the _simple_ solution. It will be:
a) easier to write
b) easier to debug (prove correct)
c) easier to maintain
d) easier to optimize
Here are two quotes from Einstein that you should keep in mind:
* "Everything should be made as
Re: (Score:2)
Depends how you define it.
If you brute-force it, it's pretty easy.
However, there's no skill nor challenge in doing so. The challenge relies on a solver that doesn't just guess all the way, but applies standard solving techniques to solve it. It's a lot harder than a brute-force solver, but it tends to be a bit more "satisfying"
Really Slashdot? WTF? (Score:2, Insightful)
You forgot about this achievement in Physics (Score:2, Funny)
http://www.theonion.com/articles/caltech-physicists-successfully-split-the-bill,2037/
Re: (Score:1)
Welcome to Slashdot, you must be new here. Slashdot is more newspaper-like than most other web resources, as it provides us with yesterday's news today!
Re: (Score:2)
Chicago Herald Position Opening Announcement
Applicants for the position of Motherfucking Editor are required to appear at the interview with three mothers
Re: (Score:2)
It is a common grammatical error... (Score:4, Informative)
"'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.
Re: (Score:3)
I had a quick look at it a couple of days ago, and it seems to require you to resort to trial and error from the very first step. I figured I had better things to do with my life.
Re: (Score:3)
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've tried my own sudoku solver on it which puposefuly doesn't do the guessing/backtracking stuff. It didn't solve one single number. So, you might not want to waste time on trying by hand.
Re: (Score:3)
The description of the puzzle by The Telegraph already says you have to resort to trial-and-error (unless you can think ahead ten moves in your head):
Instead of being able to spot where a number goes based solely on the boxes that have already been filled in, most moves will face you with two or more spaces where a number could fit.
Only one of these is correct, but to find it you must examine all possible options for your next move and perhaps the move after that, continuing in the same vein until all but one potential route results in a dead end.
Re: (Score:3)
Wrong. Fewer can never apply to [non]-count nouns, but less can apply to either.
http://en.wikipedia.org/wiki/Fewer_vs._less [wikipedia.org]
I could care fewer about people mixing these two up.
Re: (Score:2)
Thank you for your re-post, these things do matter.
Wikipedia is bound to get something wrong somewhere along the line, as are the sources they cite.
This seems to be a case of both.
For instance, in one of the examples they give "However, in the case of singular but discretely quantifiable nouns as in "one less cup of flour in this canister", the adjective less should be used, the prescriptivists argue.", the actual wording should be "one cup fewer of flour", or "one cup of flour fewer".
As for their example o
Re: (Score:2)
they make the mistake of thinking that the number of results has changed, when it is actually their individual and collective promise which is less.
I'm not sure I see a mistake - isn't it exactly that ambiguity which they're trying to demonstrate?
I used a sudoku-solver (Score:1)
The site that I used was http://www.sudokuwiki.org/sudoku.htm [sudokuwiki.org] . One of the feature of this site is to tell you the possible techniques that you can use on solving a given sudoku. Unfortunately, when it analyzed the sudoku found in the fine article it could not tell what technique to use. I used a sudoku app on my java phone to record the sudoku but it wont accept puzzles with less than 22 givens, Yeah the site brute forced the puzzle and solved it but it cannot solve it by normal means.
Slashdot is coming undone. (Score:2, Insightful)
but at least they were topical.
today's top story: worlds hardest sudoku
summary: not actually the world's hardest sudoku.
more at 11.
Call the authorities! (Score:2)
Not the hardest one (Score:4, Informative)
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/ [google.com]
For reference, this one is rated 10.7:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-420.html [enjoysudoku.com]
BTW, there is a database of 31804 puzzles of difficulty 11 and above:
http://gpenet.pagesperso-orange.fr/downloads/hard11.zip [pagesperso-orange.fr]
Exactly 7 have a rank of 11.9.
Re: (Score:2)
Definitely, eh? Did you even read the first sentence of the summary?
'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
[Yes, this completely contradicts the first link and the article title which both say this is the hardest Sudoku in the world. Terrible editing. Again.]
Re:define the difficulty level of a sudoku (Score:2)
Actually that's an interesting problem in itself. "What constitutes hard" in a sudoku puzzle? Maybe he meant that there are differences of opinion on whether one type of concept is numerically more difficult than another combined with the depth of the process, aka a harder extension of an easier concept vs an easier extension of a harder concept.
Re: (Score:2)
It's very literally a matter of opinion. Sudokus are trivial for computers. "Hard" for a sudoku means "not amenable to the kinds of tricks a human brain throws at the problem", and since brains vary, hardness is a matter of opinion.
Many human strategies are known and categorized; a puzzle that is amenable to none of them is "harder" than one that isn't. Within the range, though, it will vary from person to person.
It's kinda like the inverse of a Turing test. Too bad we can't use it for a reverse CAPTCHA: Ca
Its almost sad (Score:2)
Wiped out my Android, started augemented reality solver, pointed camera at monitor at it took 45ms to show me the complete field.
Makes Sudoku feel rather pointless.
Re: (Score:2)
sudoko IS pointless.
much more pointless than folding paper cranes. has to be pretty pointless to top that off.
Difficulty level (Score:1)
If you read the "official" difficulty level, it's 11.
Yes, it goes to 11. You know it's harder when it's one more.
Not hard at all ... (Score:2)
mainly because it's not deterministic, it's under-defined (or whatever it's called). If you can solve it with (at least) two different solutions, this PhD ought to give back his degree and go back to school for making such a claim without actually checking into the facts ... otherwise, here's my "hardest sudoku": "1" at E5. Send back the correct solution I have here.
Btw, any Sudoku solver that goes by deterministic rules without using guesswork/brute force should stop after eliminating some numbers from emp
Re: (Score:2)
Here's two solutions I managed to get out of Sudoku Sensai by filling in a couple fields randomly (that is, for fields where only two possible locations for a single digit in 3x3 field were available, I picked one, let the program solve deterministically until no more steps were available, then repeated)
8 1 4 2 5 3 6 7 9
9 2 3 6 7 8 1 5 4
5 7 6 4 9 1 2 8 3
1 3 5 9 6 7 8 4 2
6 8 2 3 4 5 7 9 1
7 4 9 1 8 2 5 3 6
4 5 1 7 2 9 3 6 8
2 6 8 5 3 4 9 1 7
3 9 7 8 1 6 4 2 5
This one I got out of Google Goggles ...
8 1 2 7 5 3 6
Uncreative (Score:2)
I can make a tougher puzzle than that. It's just a regular Sudoku, but if you make a mistake, I'll kick your shin.
World's Wrongest Sudoku? (Score:2)
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
0,046 seconds (Score:2)
Not very hard (Score:2)
|8 1 2|7 5 3|6 4 9|
|9 4 3|6 8 2|1 7 5|
|6 7 5|4 9 1|2 8 3|
|1 5 4|2 3 7|8 9 6|
|3 6 9|8 4 5|7 2 1|
|2 8 7|1 6 9|5 3 4|
|5 2 1|9 7 4|3 6 8|
|4 3 8|5 2 6|9 1 7|
|7 9 6|3 1 8|4 5 2|
real 0m0.083s
user 0m0.073s
sys 0m0.003s
The Challenge to Me... (Score:2)
The challenge to me of this type of puzzle is to use the tools and skills available to me and to write my own solver program for it on computers with compilers that I have available. Like I've done for Maverick Solitaire in the past. And to have an efficient solution that doesn't need the Amazon Cloud to solve every possible combination through poor programming. The satisfaction of having my own program reach the answer well exceeds using anyone else's solver program.
Re:Easy peasy (Score:5, Insightful)
Re:Easy peasy (Score:5, Funny)
http://www.telegraph.co.uk/science/science-news/9360022/Worlds-hardest-sudoku-the-answer.html
Re: (Score:2)
Re: (Score:2)
Well I like the Sudoku Solver at sudokuwiki.org, but it didn't find a single number before saying "Run out of known strategies. Use 'Solution Count' to check to see if the puzzle has only one solution."
I did, and after 2068781 recursions it said OK, there's just one solution.
Re: (Score:1)
brute force != solving a sudoku
Re:Easy peasy (Score:5, Interesting)
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.
Re: (Score:2)
Does it also make guesses that are several levels deep? I found the bookkeeping involved rather overwhelming.
Can you post code?
Re: (Score:2)
Sorry, code is long-since lost to bitrot and hard-drive failures.
It didn't make guesses at all, which is one of the reasons it was a lot less than perfect.
It simply applied a sequence of rules in a set of nested loops. Keep an array of 9-bit fields, one for each little square. If a bit is set to one then the corresponding number is a possibility. Use the rules to narrow down possibilities. Any time a rule is 'hit' then you go back to the start. The first few rules were something like this -
1. Reconcile rule
Re: (Score:2)
Thanks for the feedback.
Your rule #3 is interesting. I haven't thought of that one. I was playing around with a solver, that when logic runs out falls back to trial and error (not brute force, it starts from boxes that only have 2 possible numbers etc.). I read further down in the comments that recursion is the key to this, so I will try this next.
Of course, this is just a hobby project, so it will take a while before it is complete.
Re: (Score:2)
Never claimed it could solve all puzzles, it was the work of a single bored afternoon, when I realised I was getting bored of sudoku and the way to extract a little more entertainment from the format was to write a sudoku-solver that mimicked my process.
fight! fight! fight! (Score:2)
Next time you're bored write a sudoku generator then sit back and watch them slug it out.
Re: (Score:2)
Re:Easy peasy (Score:5, Insightful)
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.
Re: (Score:1)
Any number would fit in your sequence: anyone can find a polynomial that matches the beginning of the sequence and any number afterwards. So any answer fits :)
Re: (Score:2, Funny)
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!
actually you are wrong. (Score:2)
please check http://oeis.org/ [oeis.org]
Largest square = sum of squares of divisors of n.
1, 4, 9, 16, 25, 49, 49, 81, 81, 121, 121, 196, 169, 225
Re: (Score:2)
Amusingly enough, OEIS confirms the other replies. The only way it actually responds with your sequence is if you enter 1, 4, 9, 16, 25, 49, which presupposes the answer to the GP's question was "49." If you put in the GP's sequence, it responds with the GP's answer of "36."
Re: (Score:2)
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
not so easy if you are using a compass only (Score:2)
the old school type of geometry, where you just have a straightedge and a compass to draw circles around a point.
Re:Easy peasy (Score:5, Informative)
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 [norvig.com]
Re: (Score:1)
In the context of game solving, most people consider tree search with constraint checking but no guiding heuristics to be brute force.
Re:Easy peasy (Score:5, Insightful)
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.
Re: (Score:2)
source, or it didn't happen!
Re: (Score:2)
Re: (Score:2)
Re:Easy peasy (Score:5, Informative)
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.
Re: (Score:2)
It ran constantly when you started it, looping through the grid. Each square was represented as an array of the nine possible numbers. Whe
Re: (Score:2)
What?
That makes very little sense.
First off lets take "21-25" = 23 as a average number of nodes already complete.
That leaves 81-23 = 58 left to find matches for.
There are 10 possible numbers that will fit in a given node, but we are pretty much guaranteed to find everyone on average after 5 tries.
So 5 * 58 = 290
Lets assume that most of the nodes have multiple solutions the first iteration through, even if we have to iterate through a reducing set of nodes and do not even keep track of the numbers that we ha
Re: (Score:2)
So 5 * 58 = 290
That should be 5^58, or 5**58 if you only know a C dialect.
3.46944695E+40 is hardly the small number you wrongly concluded.
In actual practice, this number is way larger than necessary because it presumes an average of 5 not-immediately-constraint-breaking possibilities per square, which is not at all even close to true in practice (p.s: its still brute force when you check for constraint violations at each insertion, unlike what some folks are claiming)
Re: (Score:2)
A sudoku puzzle is not a password where you only know if you are correct if you get every single digit right.
Every single digit can stand alone, and you can have 100% certainty that one particular node is right without having any of the others.
That is why it is times, and not exponential.
But I guess in the worst case scenario, using a bad algorithm it is exponential.
IT depends on if we are measuring the worst case scenario instead of the average and exactly how brute force our brute force algorithm is.
Re: (Score:2)
That is why it is times, and not exponential.
You are drawing incorrect conclusions. It is not times no matter how you slice it.
When you try a number with your algorithm, it might be "100% certainly right", "100% certainly wrong", or the option you seem to be ignoring... "dont know yet"
Re: (Score:2)
Yes, but exponential is as wrong and overly simplistic as saying it is times.
It varies from exponential to times, depending on the algorithm and the sudoku.
Re: (Score:2)
Exponential is right... his "5" is what is wrong.
Re: (Score:2)
In actual practice, this number is way larger than necessary because it presumes an average of 5 not-immediately-constraint-breaking possibilities per square, which is not at all even close to true in practice (p.s: its still brute force when you check for constraint violations at each insertion, unlike what some folks are claiming)
Just a quick look shows that in this puzzle, there are three cases with only two possibilities: In row 6, the number 5 fits into two places only. Same in column 5. In column 2, the number 8. And a few more. And of course once those numbers are placed, it reduces the possibilities elsewhere.
Re: (Score:2)
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.
It's quite disingenuous to say that brute force doesn't work. It only takes this long if you insist on using the most brain-dead generate-and-test algorithm imaginable (i.e., generate complete 81-tuples and then check whether they happen to be valid). Add the smallest possible amount of cross-checking (i.e. don't extend candidate tuples in a way that violates the constraints), and a simple backtracking algorithm will succeed near-instantaneously. In fact, it will start spewing out solutions immediately even
Re: (Score:2)
That is the dumbass brute force method trying every single number irregardless of the givens, which will take forever. Why the fuck will anyone do it that way?
Several years ago I wrote a brute force solver that pruned numbers for each cell that has already appeared in the same row/cell/box, and it solved all puzzles in under 200ms on a sub-100MHz ARM processor.
Re: (Score:2)
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:
That's not brute force, that is stupid.
A simple brute force algorithm: With every puzzle, you can ask the questions: "Which digit goes into row r, column c", "where in row r does the digit d go", "where in column c does the digit d go", and "where in box b does the digit d go". There are 4 x 81 questions. Each number that is already given, 4 questions are answered. Check which answers are possible for each unanswered question, just by removing the possibilities that are ruled out directly by the rules of
Re: (Score:2)
All of you are weak. Real men solve sudoku by rolling a nine-sided die and recording the results in the grid.
It didn't work in this universe, but somewhere it did.
Re:Easy peasy (Score:5, Informative)
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: (Score:2)
Re: (Score:2)
I think you are all getting confused by alpha-beta chess engines not being brute force.. but have wrongly decided the reason for them not being so. The reason they are not is that they are truncated searches.. they do not look ahead all the way to the end of the game.
Re: (Score:2)
I think what GP meant to say was that - while heuristic-guided brute force solves the puzzle - it's not a "pure" solution in that the solution wasn't deduced logically.
The holy grail of sudoku solvers is one that can universally solve any given puzzle using only heuristics - and no brute force/trial and error element. So far, none have been created.
Re: (Score:1)
Brute force sudoku solvers will attempt a partial solution and backtrack when it's clear that the solution is invalid.
It looks like you'll need to do something similar with this one. Speculatively try a solution for a specific number in a specific square, and if that means that you end up with an invalid configuration, you need to try the other possible solution.
The brute force solution is a much less directed version of the same thing.
extra hard sudoku = pointless (Score:2)
its like chess. the point of the thing isn't to "solve problems", it is to exercise the problem solving center of the brain. its supposed to be somewhat amusing and/or entertaining. if you make sudoku so hard that only a computer can solve it, you have kind of defeated the purpose of the game in the first place. like trying to play basketball with 20 foot high hoops
Re: (Score:2)
I found the process of forming a process to solve these things much more stimulating than actually solving the sudoku's.
It does kinda ruin the game though.
metagame (Score:2)
Gaming the game can become a game in its own right.
Take a look at the constant arms race between games operators & the wallhacking/aimbot fraternity.
No brute force needed. (Score:2)
Re: (Score:2)
Dam. You beat me to it.
Re: (Score:2)
You're Finnished already?
Re: (Score:2)
If there is more than one solution, then it is not a valid puzzle -- and several solving techniques are dependent on the axiom that there is exactly one correct answer. I know that I invoked such a technique at least once in coming up with this solution:
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 8 2 3
1 5 4 8 3 7 2 9 6
3 6 9 2 4 5 7 8 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
Perhaps there is an error in the original article's depiction of the puzzle?
Re: (Score:2)