Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

World's Hardest Sudoku

Soulskill posted more than 2 years ago | from the addition-is-tricky dept.

Math 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."

cancel ×

179 comments

Sorry! There are no comments related to the filter you selected.

Easy peasy (-1, Flamebait)

Anonymous Coward | more than 2 years ago | (#40539461)

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

Re:Easy peasy (5, Insightful)

piripiri (1476949) | more than 2 years ago | (#40539497)

You mean easy for your sudoku-solver ?

Re:Easy peasy (-1)

Anonymous Coward | more than 2 years ago | (#40539519)

How dare you, Sir! I resent that notion.

Re:Easy peasy (4, Funny)

Inda (580031) | more than 2 years ago | (#40541445)

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

Re:Easy peasy (1)

Anonymous Coward | more than 2 years ago | (#40539511)

brute force != solving a sudoku

Re:Easy peasy (4, Interesting)

Nursie (632944) | more than 2 years ago | (#40539543)

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:Easy peasy (1)

Anonymous Coward | more than 2 years ago | (#40540347)

One of two things is true about your solver:
1) You're the first to write a solver that can solve all puzzles without brute force
2) Your solver can't solve all puzzles

Start reading here: http://www.sudokuwiki.org/Crooks_Algorithm

Re:Easy peasy (1)

Nursie (632944) | more than 2 years ago | (#40540851)

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.

Re:Easy peasy (4, Insightful)

tehcyder (746570) | more than 2 years ago | (#40539597)

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:Easy peasy (1)

Anonymous Coward | more than 2 years ago | (#40539663)

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:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40540155)

You have to find the simplest rule/law that describes the given numbers and use that to predict the next numbers.

Re:Easy peasy (2, Funny)

Anonymous Coward | more than 2 years ago | (#40540297)

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!

Re:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40541331)

Kolmogorov complexity is only well-defined up to a constant.

Re:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40540099)

By that same token, if I were to bring a 9mm to a basketball game, I could be the greatest baller EVER! Yeah, bro... it's still cheating, and you therefore, suck.

actually you are wrong. (1)

decora (1710862) | more than 2 years ago | (#40540349)

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:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40541181)

I believe the next number would be 49...
1 + (3 Prime) = 4
4 + (5 Prime) = 9
9 + (7 Prime) = 16
16 + (9 ???) =25 errrr ok so maybe I don't have that figured out.....I guess ending up with the right number isn't always the only goal.

Re:Easy peasy (5, Informative)

havarh (1429591) | more than 2 years ago | (#40539629)

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:Easy peasy (1)

Anonymous Coward | more than 2 years ago | (#40539669)

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 (4, Insightful)

perryizgr8 (1370173) | more than 2 years ago | (#40539923)

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:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40540139)

We may have a debate here over exactly what constitutes "brute force" in this context. We can imagine, for example, a program whichtries each of the 9^81 ways of filling the grid with numbers 1-9, and checks each of them for compatibility with the rules of sudoku and the numbers specified for the problem. Presumably your solver is less brute-forcey than that, but less clever than a human. But even the way that a human approaches a sudoku could be described as having an element of brute force.

Re:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40540157)

It took me longer than 10 mins but it is certainly a simple and short program when you get the trick. Recursion is wonderful!
What I found harder was estimating how many cases it was evaluating, and how much back tracking to expect.
I wasted many minutes worrying about whether it was going to take seconds or minutes before running it.
Then the answer came back nearly instantaneously!
Could anyone point me in the direction of a good source for analysing truncated tree searches like this?

Re:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40540519)

That's called combinatorial search - that you consider it "brute force" just shows you are clueless.

Re:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40541123)

Sell your aging laptop to Peter Norvig, telling him that it's an aging laptop from the future that you brought back with you in that time machine he was talking about.

Re:Easy peasy (4, Informative)

mwvdlee (775178) | more than 2 years ago | (#40540393)

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:Easy peasy (1)

wisnoskij (1206448) | more than 2 years ago | (#40540653)

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 have already crossed of as impossible in a given locative, we are talking a very small number in terms of a computer.
So even on the slowest processor, and even if you are using hundreds of instructions to test one number in one location you will be done in a fraction of a second.

Re:Easy peasy (1)

Rockoon (1252108) | more than 2 years ago | (#40540913)

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:Easy peasy (1)

wisnoskij (1206448) | more than 2 years ago | (#40541321)

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:Easy peasy (1)

Rockoon (1252108) | more than 2 years ago | (#40541409)

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:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40541019)

Brute force solvers are actually quite feasible -- They use the logic of sudoku to vastly cut down on the number of iterations required because they can do a lot of other steps ahead of time to logically reduce the possible solution sets down to just two or three possible numbers for any given cell. What they do is use logic as far as it can go, then pick a cell and 'assume' that's the answer, out of the (usually only two or three) possible choices, then push logic further. If another assumption is required, it's recorded, and the wonders of recursion take over. From there, it usually takes an extremely small amount of processor time to figure out if a guess was 'wrong' since you'll usually end up with a cell with no remaining possible choices, that or it solves it.

In fact, brute-force checkers using this method are also capable of testing a puzzle to ensure that any given sudoku contains *only* one solution, and it still only takes a modern PC a couple seconds.

Re:Easy peasy (1)

k.a.f. (168896) | more than 2 years ago | (#40541115)

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 if you start it with a completely empty board.

Re:Easy peasy (1)

tangent3 (449222) | more than 2 years ago | (#40541257)

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:Easy peasy (1)

gnasher719 (869701) | more than 2 years ago | (#40541463)

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 Sudoku (digits 1 to 9, no digit twice in the same row, column, or box). If there's a question without possible answer then there is no solution. If there's a question with one possible answer you pick that. Otherwise, you pick one of the questions with the smallest number of possible answers at random, and try all the possible answers in turn.

That will find an answer quite quickly.

Re:Easy peasy (4, Informative)

1s44c (552956) | more than 2 years ago | (#40539775)

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 (1)

hvm2hvm (1208954) | more than 2 years ago | (#40540115)

Well not necessarily, you can actually find a method of solving something so you don't have to go brute force with or without filtering results

Re:Easy peasy (1)

Rockoon (1252108) | more than 2 years ago | (#40540957)

Even when your heuristic constraints reduces the problem space to only 2 possibilities, if the remaining space is guaranteed to have at least 1 solution, then its brute force.

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:Easy peasy (1)

91degrees (207121) | more than 2 years ago | (#40539965)

Except this is sort of what you're doing anyway.

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.

Re:Easy peasy (0)

Anonymous Coward | more than 2 years ago | (#40540039)

How much brute force does it take to draw a wang on Marmaduke?

extra hard sudoku = pointless (1)

decora (1710862) | more than 2 years ago | (#40540335)

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:extra hard sudoku = pointless (1)

mwvdlee (775178) | more than 2 years ago | (#40540439)

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.

Re:Easy peasy (1)

1s44c (552956) | more than 2 years ago | (#40539765)

Dam. You beat me to it.

Re:Easy peasy (1)

PopeRatzo (965947) | more than 2 years ago | (#40540529)

You're Finnished already?

Re:Easy peasy (1)

Internal Modem (1281796) | more than 2 years ago | (#40541301)

Here is another solution (there are more than one):
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

It's game on then (2)

Wild Wizard (309461) | more than 2 years ago | (#40539527)

I'm printing it out now, nothing like someone claiming the impossible to make you want to try and prove them wrong.

Re:It's game on then (2)

balouderbaer (2563063) | more than 2 years ago | (#40539573)

see you in 5 minutes after you realize it actually is kinda hard

Re:It's game on then (4, Funny)

Chrisq (894406) | more than 2 years ago | (#40539661)

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:It's game on then (0)

Anonymous Coward | more than 2 years ago | (#40539831)

aspie?

Re:It's game on then (1)

Chrisq (894406) | more than 2 years ago | (#40539841)

Probably aspie tendencies

Re:It's game on then (1, Flamebait)

TemperedAlchemist (2045966) | more than 2 years ago | (#40540173)

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:It's game on then (0)

Anonymous Coward | more than 2 years ago | (#40540513)

Everybody hates ass pies.

Hardest or Easiest (0)

Anonymous Coward | more than 2 years ago | (#40539569)

Would not filling in an entirely empty grid to match a hidden completed grid be the hardest, in that only luck of Pre-cognition will help you.

All other grids where there is a singular chain of logical inference leading to a unique solution are neither harder nor easier than each other. They are just more or less boring to fill in as you progress round the inference algorithm. I learned this after filling in my fourth "Hard" grid, in that using a simple algorithm with a good notation will always lead to a result.

This is also why I stopped doing Soduko.

Who cares about the Higgs boson? (5, Funny)

BlackPignouf (1017012) | more than 2 years ago | (#40539585)

Who cares about the Higgs boson?
Sudoku is real science!

Hard? (1)

Gumbercules!! (1158841) | more than 2 years ago | (#40539599)

It wasn't hard at all - My Galaxy S3 with Google Goggles solved it in under 3 seconds.

Of course, I personally, don't even know the rules of Sudoku. :-P

Re:Hard? (3, Informative)

perryizgr8 (1370173) | more than 2 years ago | (#40539937)

also, google goggles solves the sudoku using google's servers, not your phone. so it doesn't matter that you used an s3.

Re:Hard? (Samsung Galaxy S3) (0)

Anonymous Coward | more than 2 years ago | (#40540127)

also, google goggles solves the sudoku using google's servers, not your phone. so it doesn't matter that you used an s3.

Of course (Samsung) it (Galaxy) matters (S3), when Samsung (Galaxy S3) is paying for (Samsung Galaxy S3) your posts.

Samsung Galaxy S3!

Re:Hard? (Samsung Galaxy S3) (0)

Anonymous Coward | more than 2 years ago | (#40540237)

You just dropped your tinfoil hat. There it is.

I'll give it a try (1)

D4n13LA (2676687) | more than 2 years ago | (#40539611)

Would love to give it a shot!

Not so hard (5, Insightful)

Laxator2 (973549) | more than 2 years ago | (#40539613)

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 (4, Interesting)

BlackPignouf (1017012) | more than 2 years ago | (#40539773)

Cool link, thanks!
I love this quote :
Ben Laurie has stated : Sudoku is "a denial of service attack on human intellect".

Re:Not so hard (0)

Anonymous Coward | more than 2 years ago | (#40539799)

You're most welcome. That quote is my favorite too :-)
Plus, Perter Norvig gives an excellent explanation of the algorithm he uses before coding it up.

Re:Not so hard (1)

Anonymous Coward | more than 2 years ago | (#40540063)

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;
$ time ./CSPsudoku hardest.txt hardest_solve.txt
real 0m0.041s
user 0m0.027s
sys 0m0.008s

Re:Not so hard (0)

Anonymous Coward | more than 2 years ago | (#40540209)

Well done!
The reason I wrote the solver is that I wanted to play around with templates in C++.
I certainly did not optimize it for speed, and I know that my algorithm explores a lot of dead-ends.
I found that the best way to learn something is to solve a real-life problem.
So, solving the N queens on the NxN chess board problem was too simple, and writing a chess-playing program was too hard (for me).
I found that a Sudoku-solving program would have just the right amount of complexity for an afternoon of coding.
To justify the use of templates it can solve puzzles filled either with numbers 1 ... 9 or letters A ... I.
And no, I am not cheating on mapping the letters to numbers, solving the number puzzle, and then mapping them back when writing the output.
It's templates all the way. For me solving Sudoku had a good educational value.

Re:Not so hard (1)

mstefanro (1965558) | more than 2 years ago | (#40540315)

You don't seem to like the const keyword very much, do you?
550 lines of C++ code and nearly no appearances of const.

Re:Not so hard (0)

Anonymous Coward | more than 2 years ago | (#40540365)

You got me here, I do kind of hate it :-)

Re:Not so hard (0)

mseeger (40923) | more than 2 years ago | (#40540357)

I agree, the word "hard" and "Sudoku" should not be used in the same sentence. When i still gave coding lessons, i used "solving Sudoku" as an easy example right after "Hello world".

Re:Not so hard (0)

Anonymous Coward | more than 2 years ago | (#40540397)

Norvig's solver is a brute-force one. You can design sudokus that to be quite long to solve for a brute-force algorithm, but that a 10 years old would definitely find easy.

Make the difference between a brute-force solver and a hint-based solver!

Re:Not so hard (0)

Anonymous Coward | more than 2 years ago | (#40540579)

I have to admit that I never looked beyond the first-order approximation (i.e. brute-force with constraint propagation and backtracking).
What is remarkable, is that Norvig's solver is very short, written in an interpreted language (Python) and still can solve ~80 hard puzzles per second.
If you know of better solvers (hint-based, as you mentioned) please provide a link.

Re:Not so hard (0)

Anonymous Coward | more than 2 years ago | (#40541299)

Mine did it in less than a second, and the solution part of my code is only about 40 lines
https://github.com/robbinsr/SudokuSolver/blob/master/sudokuSolver.cc

Really Slashdot? WTF? (2, Insightful)

Slutticus (1237534) | more than 2 years ago | (#40539617)

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.

Re:Really Slashdot? WTF? (0)

Anonymous Coward | more than 2 years ago | (#40539673)

This will be tomorrow's news.

You forgot about this achievement in Physics (2, Funny)

Anonymous Coward | more than 2 years ago | (#40539695)

http://www.theonion.com/articles/caltech-physicists-successfully-split-the-bill,2037/

Re:Really Slashdot? WTF? (1)

Anonymous Coward | more than 2 years ago | (#40539941)

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:Really Slashdot? WTF? (0)

bbbaldie (935205) | more than 2 years ago | (#40540723)

Maybe you should apply for a job as a motherfucking editor? You might want to tone it back a bit on your motherfucking interview, though. Fuck.

It is a common grammatical error... (3, Informative)

unitron (5733) | more than 2 years ago | (#40539627)

"'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:It is a common grammatical error... (2)

julesh (229690) | more than 2 years ago | (#40540319)

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:It is a common grammatical error... (2)

alexhs (877055) | more than 2 years ago | (#40540437)

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:It is a common grammatical error... (2)

wvmarle (1070040) | more than 2 years ago | (#40540669)

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:It is a common grammatical error... (1)

Anonymous Coward | more than 2 years ago | (#40541255)

Wrong. Fewer can never apply to count nouns, but less can apply to either.
http://en.wikipedia.org/wiki/Fewer_vs._less

I used a sudoku-solver (1)

abednegoyulo (1797602) | more than 2 years ago | (#40539651)

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. (1, Insightful)

wild_quinine (998562) | more than 2 years ago | (#40539731)

slashdot is pretty much done at this point, right? it always was a site made by its contributors, and the articles always were misleading and sensational.

but at least they were topical.

today's top story: worlds hardest sudoku

summary: not actually the world's hardest sudoku.

more at 11.

First Solution! (0)

Anonymous Coward | more than 2 years ago | (#40539749)

812753649 943682175 675491283 154237896 369845721 287169534 521974368 438526917 796318452

Call the authorities! (2)

Quakeulf (2650167) | more than 2 years ago | (#40539769)

I am putting you all on sudoku watch.

Not the hardest one (3, Informative)

eulernet (1132389) | more than 2 years ago | (#40539843)

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:Not the hardest one (0)

Anonymous Coward | more than 2 years ago | (#40540091)

That tool might give useful ratings or it might not. Since it doesn't seem to have any documentation explaining what it does, let alone why that gives a good rating, it's a bit of a stretch to take its ratings as pure truth.

Re:Not the hardest one (1)

FrootLoops (1817694) | more than 2 years ago | (#40540185)

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 (1)

TaoPhoenix (980487) | more than 2 years ago | (#40540287)

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.

It's tough if it goes to 11? (0)

Anonymous Coward | more than 2 years ago | (#40540273)

Imagine that.

Its almost sad (1)

imsabbel (611519) | more than 2 years ago | (#40539939)

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:Its almost sad (1)

gl4ss (559668) | more than 2 years ago | (#40541367)

sudoko IS pointless.

much more pointless than folding paper cranes. has to be pretty pointless to top that off.

Difficulty level (1)

karolgajewski (515082) | more than 2 years ago | (#40539977)

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.

Symmetry? (0)

Anonymous Coward | more than 2 years ago | (#40540001)

But it's not symmetric! All good sudoku puzzles should be rotationally symmetric.

Not hard at all ... (1)

garry_g (106621) | more than 2 years ago | (#40540161)

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 empty fields ... ny solver that comes up with a solution obviously does brute force ...

Re:Not hard at all ... (1)

Tompko (1416883) | more than 2 years ago | (#40540961)

Care to give more than one solution to this sudoku? I can only find one with my solver.

Re:Not hard at all ... (1)

garry_g (106621) | more than 2 years ago | (#40541095)

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 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

Re:Not hard at all ... (1)

Tompko (1416883) | more than 2 years ago | (#40541179)

Your first solution is incorrect, B6 is 5, not 3. (Where A1 is the bottom left corner)

Uncreative (1)

hort_wort (1401963) | more than 2 years ago | (#40540291)

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? (2)

KritonK (949258) | more than 2 years ago | (#40540551)

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.

Re:World's Wrongest Sudoku? (1)

Tompko (1416883) | more than 2 years ago | (#40540981)

Could you provide the other solutions you've found, my solver only finds one valid solution. If it's going wrong I'd like to debug it.

Re:World's Wrongest Sudoku? (1)

KritonK (949258) | more than 2 years ago | (#40541309)

Here's one:

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

And here's another:

869 712 354
243 658 179
175 493 286

952 367 841
316 845 792
784 129 635

531 274 968
428 936 517
697 581 423

The list is not exhaustive.

When I wrote my reply, I got a second solution after two additional runs on the solver. Now that I actually want to reproduce a second solution, my solver kept producing the same solution, so I helped it a bit by filling in an additional cell! (It's the"2" in the second row—"1" did not work.)

If your solver does not make random guesses, making its guesses in some deterministic fashion among valid choices (e.g., in order) instead, then it is obviously not wrong! On the other hand, I think it is fun to be able to let the solver loose on an empty sudoku grid and watch it produce a different solution each time.

Re:World's Wrongest Sudoku? (1)

Tompko (1416883) | more than 2 years ago | (#40541431)

Your second solution isn't a solution to the given puzzle, D2 should be 5. (Where A1 is the bottom left)

Is this puzzable solvable with no guessing at all? (1)

NoahsMyBro (569357) | more than 2 years ago | (#40541385)

I've spent some time trying to work this puzzle out this morning, and haven't gotten one number figured out yet.

Maybe I'm just not good enough at solving Sudokus, but is this puzzle solvable at all by logical deduction? Or is it *necessary* to just guess a number at some point, and 'trial & error' it to see where it leads?

Does anyone here know whether or not this puzzle can be solved without guessing?

If it is necessary to just put a number in a box and see if that will eventually lead to a dead end, then IMO this isn't a valid Sudoku puzzle. If there is some logical way, even if difficult, to conclusively determine a specific square MUST be a specific number, then I must just not be good enough to solve the puzzle, and I'm willing to accept that.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>