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

Easy peasy

[Anonymous Coward]

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

[piripiri]

You mean easy for your sudoku-solver ?

Re:Easy peasy

[Anonymous Coward]

brute force != solving a sudoku

Re:Easy peasy

[Anonymous Coward]

How dare you, Sir! I resent that notion.

Re:Easy peasy

[Nursie]

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

[tehcyder]

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

[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

[Anonymous Coward]

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

[Anonymous Coward]

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

[1s44c]

Dam. You beat me to it.

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

[perryizgr8]

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

[91degrees]

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

[Anonymous Coward]

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

Re:Easy peasy

[Anonymous Coward]

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.

Re:Easy peasy

[hvm2hvm]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

Re:Easy peasy

[Anonymous Coward]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

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

Re:Easy peasy

[Anonymous Coward]

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

Re:Easy peasy

[PopeRatzo]

You're Finnished already?

Re:Easy peasy

[wisnoskij]

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

[Nursie]

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

[Rockoon]

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

[Rockoon]

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

[Anonymous Coward]

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

[k.a.f.]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

[tangent3]

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

[Internal Modem]

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

Re:Easy peasy

[wisnoskij]

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

[Anonymous Coward]

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

Re:Easy peasy

[Rockoon]

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

[Inda]

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

[gnasher719]

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

[wisnoskij]

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:Easy peasy

[Mal-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:Easy peasy

[aardvarkjoe]

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

[Rockoon]

Actually no.. because only one number at a given location is right, if there are currently 5 possibilities then it adds p*5 more things to be searched no matter what (where p is the number of cases already counted)

Exponential is right... his "5" is what is wrong.

Re:Easy peasy

[thePowerOfGrayskull]

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:Easy peasy

[excelsior_gr]

Does it also make guesses that are several levels deep? I found the bookkeeping involved rather overwhelming.

Can you post code?

Re:Easy peasy

[excelsior_gr]

source, or it didn't happen!

Re:Easy peasy

[Anonymous Coward]

This is the level of comment that gets +5 insightful on slashdot these days?

Re:Easy peasy

[willy_me]

There are ~ 9^39 ways that a sudoku board can be filled in - much less then 9^81. Regarding "brute force" algorithms, I would define them as algorithms that attempt every possible option without the use of heuristics. This does not imply they are stupid and check possibilities that can not exist, which would be 9^81, just that they do not try the most likely solution first.

Re:Easy peasy

[willy_me]

Correction here, poor definition for "brute force", other described it better. Should be described as a search algorithm that tries all possible valid solutions - heuristics are allowed.

Re:Easy peasy

[Beardydog]

That's about all my solver actually did, if I recall correctly. I worked at a small game publisher a couple years ago, and one of my many and varied duties was game testing. We had a Brain Age clone type of game in, and I had to grind through some sudoku, which was obviously not a great use of my time. So during my lunch break, I wrote what I think amounted to a sieve.

It ran constantly when you started it, looping through the grid. Each square was represented as an array of the nine possible numbers. When an array got down to a single digit, that digit was removed from all of its square, row, and column-mates.

Then the next loop check for new squares that had been knocked down to a single digit, to repeat the process.

They were relatively easy puzzles, and I think that actually solved the bulk of them, but I did have to add a check that went a level deeper at some point.

i'm a terrible programmer, and it was a terrible program, but it was very fun to use. Because it was always running, it was actually just waiting for the user to input the starting numbers drom the puzzle. Each time you enter a starting digit, all the numbers wiggled around for a moment finding new stable values, with locked digits turning from red to green. By the time you entered the last digit, the puzzle was more or less solved, and the last few green numbers would lock into place.

if you've ever played Uplink, it was very much like an interactive "Elyptic Curve Cipher".

Re:Easy peasy

[gnasher719]

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:Easy peasy

[DMUTPeregrine]

800 000 000
003 600 000
070 090 200

050 007 000
000 045 700
000 100 030

001 000 068
008 500 010
090 000 400

There is a unique solution. The puzzle in the parent and GP is different from that in the article.
Correct solution:
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

Brute force must be used to place digit 2 in R6C1
All other used techniques:
Full House
Mixed Single
Box Single
Row Single
Column Single
Naked Single
Locked Pair
Locked Candidates type 1 & 2
2-string Kite
Sue De Coq
Almost Locked Sets
Table Conflict
and Last Digit.

Re:Easy peasy

[interkin3tic]

Reminds me of my favorite Dilbert comic.

Re:Easy peasy

[Nursie]

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 - sweep all slots eliminating possible values from empty squares - i.e, if there's a 4 in slot A1, knock off bit 4 as possible value for all slots in column A, row 1 and major square (A-C,1-3)

2. If a slot has only one possible value left, then it must take that value. Go back to 1.

3. If two slots in a row, column or major square have the same two possible values left, eliminate those possible values from all other little squares in that row, column or major square. Go back to 1.

4. Same as 2, but for three slots. ...

There were another couple of rules. It couldn't solve all sudoku by any means, because it couldn't do 'suppose this slot is a 5, does that break things' type calculations, but it got quite a lot of them.

Re:Easy peasy

[Anonymous Coward]

CPAN, or it doesn't exist!

http://search.cpan.org/~mehner/Games-Sudoku-Solver-1.1.0/lib/Games/Sudoku/Solver.pm

Re:Easy peasy

[FitForTheSun]

Wrong. The answer is 31. That is a list of all my favorite numbers. The last one in the list is 70.

Re:Easy peasy

[Anonymous Coward]

see also: http://www.dailymail.co.uk/news/article-2166680/True-test-genius-monumental-waste-time-Can-solve-hardest-Sudoku.html

Re:Easy peasy

[excelsior_gr]

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:Easy peasy

[Lorens]

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.

It's game on then

[Wild Wizard]

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

[balouderbaer]

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

Re:It's game on then

[Chrisq]

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

[Anonymous Coward]

aspie?

Re:It's game on then

[Chrisq]

Probably aspie tendencies

Re:It's game on then

[TemperedAlchemist]

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

[Anonymous Coward]

Everybody hates ass pies.

Re:It's game on then

[FitForTheSun]

flamebait? is that a mistaken mod?

Re:It's game on then

[TemperedAlchemist]

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

[FitForTheSun]

I bet it was just a mistake. Once you mod, you can't retract, or you might not even notice the mistake.

I copied down the puzzle and wrote down the possibilities for each square, but haven't spent time to solve it yet. What did you do to get to fill in the first number?

Re:It's game on then

[TemperedAlchemist]

Guess or toss a coin.

Hardest or Easiest

[Anonymous Coward]

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?

[BlackPignouf]

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

Hard?

[Gumbercules!!]

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?

[perryizgr8]

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?

[Anonymous Coward]

1. Each number may appear only once per row
2. Each number may appear only once per column
3. Each number may appear only once per 3x3 block
4. ?????
5. Profit!

Re:Hard?

[TriezGamer]

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

[D4n13LA]

Would love to give it a shot!

Not so hard

[Laxator2]

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

Re:Not so hard

[BlackPignouf]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

[mstefanro]

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

[mseeger]

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

[Anonymous Coward]

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

Re:Not so hard

[Anonymous Coward]

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

[Anonymous Coward]

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

[Anonymous Coward]

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

Re:Not so hard

[Anonymous Coward]

The following crappy solver I cobbled together solved it in 33 seconds under Cygwin:
https://github.com/fhstoica/NumbersAndLettersSudokuSolver

Just wondering...
If you find one that takes much longer to solve with this solver... Does it mean that it is actualy harder, or just that this solver is not exactly the most efficient one for this particular sudoku?

Re:Not so hard

[Anonymous Coward]

There's a reason 'const' wasn't appropriated by C# ... (And I am mainly a C++ programmer)

Re:Not so hard

[UnknownSoldier]

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/

My input file is:
8-- --- --- // stupid lameness filter
--3 6-- --- // more stupid line too few
-7- -9- 2-- // again

-5- --7 --- // /. filters suck
--- -45 7-- // more kludge hacks
--- 1-- -3- // for lame filter

--1 --- -68 // almost done
--8 5-- -1- // /. is annoying
-9- --- 4-- // OK input is done

#include <stdio.h> // g++ -DLOG=0 sudoku3.cpp -O2 -o sudoku3.exe // 107 lines
#include <string.h> // memset

struct Board
{
char cell[9][9];
int nEmpty;

Board() { memset( (void*)cell, 0, sizeof( Board ) ); }
Board( const Board& copy ) { *this = copy; }

void Print() {
for( int y = 0; y < 9; y++ ) {
if (y && (y%3 == 0)) printf("---+---+---\n");
for( int x = 0; x < 9; x++ ) {
if (x && (x%3 == 0)) printf("!");
printf( "%c", cell[y][x] ? '0' + cell[y][x] : ' ' );
}
printf("\n");
}
printf( "\n" );
}

int GetInvalidMoves( int x, int y ) // bitmask of invalid moves
{
int cx, cy, wx, wy, bMask = 0;
cy = y; for( cx = 0; cx < 9; cx++ ) // horizontal
bMask |= (1 << cell[cy][cx]);
cx = x; for( cy = 0; cy < 9; cy++ ) // vertical
bMask |= (1 << cell[cy][cx]);
wx = x - (x % 3); // 3x3 block
wy = y - (y % 3);
for( int by = 0; by < 3; by++ )
for( int bx = 0; bx < 3; bx++ )
bMask |= (1 << cell[wy+by][wx+bx]);
return bMask;
}

void TotalEmptyCells()
{
nEmpty = 9 * 9;
for( int y = 0; y < 9; y++ )
for( int x = 0; x < 9; x++ )

Re:Not so hard

[Anonymous Coward]

Yeah, because sloppy people don't like it.

Re:Not so hard

[Anonymous Coward]

No offense taken. The whole point of writing that program was to play around with templates (and SLT/BOOST), and efficiency was never a concern.
As long as it managed to solve some puzzle, it was OK for me. Just wanted a "real world" problem to solve, one of moderate complexity.

As you point out, there is no need for 550 lines of code if you aim to solve the puzzle, but you need that many to try various things, like template specialization.
There is only that much you can do with STL/BOOST for simpler problems, like N queens on an N-by-N chessboard, or generating all subsets of a set.

I pointed out that it is a crappy algorithm and made the point that even that one solved the puzzle in 33 seconds. Not that hard a puzzle then.

Thanks for the code and the solution, it confirms the one that I found as well.
     

Re:Not so hard

[Anonymous Coward]

No, because only idiots think it's a good idea to have your virtual methods call the wrong override because suddenly someone called your method on a const object. Get over yourself.

Re:Not so hard

[tlhIngan]

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

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" in its solution

Every (valid) sudoku can be brute-forced. But not every one can be solved.

Re:Not so hard

[Anonymous Coward]

The algorithm is not particularly efficient. There are other puzzles that take up to 4 minute to solve, and Norvig's Python script solves them in 10 milliseconds.
The algorithm explores a lot of dead ends, creating tables with repeated values on rows or columns, and then it has to backtrack.

Re:Not so hard

[UnknownSoldier]

> 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 simple as possible, but not simpler."
* "Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius -- and a lot of courage -- to move in the opposite direction."

You can tell your solution (code) is getting better when it gets smaller. You are able to do more with less. Solve the _specific_ problem, NOT the _general_ problem. Other people will THANK you for being succinct, not verbose.

Cheers

Re:Not so hard

[Anonymous Coward]

33 second? 8-o You have Atari or what? My solver in javascript embeded in HTML took TWO seconds @ pentium M 1,7 GHz and 700MB RAM. It would be faster on my new desktop with i7, but I am away from it. See this "hardest" input here: http://trida.hy.cz/cima/

For the record I made this 6 years ago when broke my thumb and tried to kill time by solving sudoku. I have never finished my first sudoku manually :-). Secondly I am not web programmer. I like real programming languages like C++ or Java. I just wanted to explore something new and possibilites of clients side scripting.

Re:Not so hard

[Anonymous Coward]

33 seconds? 8-o You have Atari or what? I my javascript solver embeded in HTML took 2 seconds @ pentium M, 1,7 GHz 760 MB RAM. It would be faster on my desktop with i7, but I am away from it. See it here http://trida.hy.cz/cima/

For the record I made this 6 years ago when I broke my thumb and tried to kill some time. I have never finished my first sudoku manually. And I am not web developer. I like real languages like C++ and Java. I just wanted to try something new and explore possibilities of client side scripting.

Re:Not so hard

[Anonymous Coward]

Yep, 33 seconds. Just as you mentioned that you tried to kill some time, I was trying my hand at C++ templates with some STL/BOOST included.
I complicated the problem as much as I could, over-engineering it, just to have some reason to use the templates.

My purpose was never that of solving the puzzle fast.

Did you look over the code? I made a class template "Node" where a simple integer would suffice, just so that I can find an application for templates.
As a result, my solver can complete a puzzle with either number or letters.

I can write efficient code too, if you want just look at:
https://github.com/fhstoica/AbelianHiggs

Re:Not so hard

[Anonymous Coward]

Yes I did look over the code and the overengeneering was the first word that came to my mind. However the main performance problem might be usage of linked structures such as Set, which is Tree. And the vector of vector. Two dimensional array is always perfomance killer. I used them too, but with á priori known constat size, so they might be optimized in firefox. And another killer might be shared pointer. It is cool thing but we did research and they are 10 slower than plain pointers. Generally dynamic structures are big performance consumers. So it is best to use fixed size directly accessible structures such as vector in cases where size is fixed. For example I used three-dimensional array where true signalized that number is used elswhere and thus cannot be used in current cell. This benefits of cashing. I have no time to fully understand your code, but there must be some mistake in cycles, such as calculating something redundantly, because templates are no performance consumers cos they are resolved during compilations, vectors are OK, sets are fast enough and shared pointers are killer, but not so much as interpreted javascript in browser. Such an overengeneering cannot be 20× killer. Effective code is also a part of engeerig, because algorithm precedes usage of particular structures.

Re:Not so hard

[Anonymous Coward]

It should be 33ms rather than 33 sec, using Norvig's code.

Re:Not so hard

[Anonymous Coward]

My solver I assembeld in less than 100 lines (years ago) solves it in 0.08s

http://ideone.com/VpvVZ

Really Slashdot? WTF?

[Slutticus]

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 grammatical error...

[unitron]

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

[julesh]

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

[alexhs]

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

[wvmarle]

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

[Anonymous Coward]

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

Re:It is a common grammatical error...

[wonkey_monkey]

Reposting what an AC said, because these things matter ;)

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

I could care fewer about people mixing these two up.

Re:It is a common grammatical error...

[Anonymous Coward]

It requires brute force for two early moves.

After that there are a bunch of exclusions due to things like locked candidates and hidden pairs.

Re:It is a common grammatical error...

[Anonymous Coward]

It is a common misconception that less modifies only mass nouns.

Re:It is a common grammatical error...

[unitron]

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 of "...the ambiguity it may provide in noun phrases like less promising results".", 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.

Re:It is a common grammatical error...

[wonkey_monkey]

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

[abednegoyulo]

The site that I used was http://www.sudokuwiki.org/sudoku.htm . 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.

Re:I used a sudoku-solver

[Anonymous Coward]

My brute force solver took 7681 trials or moves to solve the puzzle, which is indeed a lot of backtracking. I may need to work on improving the optimizer algorithm for these kinds of puzzles. You need optimizers to greatly speed up solution time and even avoid infinite loops.

Re:Really Slashdot? WTF?

[Anonymous Coward]

This will be tomorrow's news.

You forgot about this achievement in Physics

[Anonymous Coward]

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

Slashdot is coming undone.

[wild_quinine]

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!

[Anonymous Coward]

812753649 943682175 675491283 154237896 369845721 287169534 521974368 438526917 796318452

Call the authorities!

[Quakeulf]

I am putting you all on sudoku watch.

Not the hardest one

[eulernet]

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.

Re:Not the hardest one

[Anonymous Coward]

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

[FrootLoops]

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

Its almost sad

[imsabbel]

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

[gl4ss]

sudoko IS pointless.

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

Re:Really Slashdot? WTF?

[Anonymous Coward]

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!

Difficulty level

[karolgajewski]

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?

[Anonymous Coward]

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

Re:Hard? (Samsung Galaxy S3)

[Anonymous Coward]

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!

Not hard at all ...

[garry_g]

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

[Tompko]

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

Re:Not hard at all ...

[garry_g]

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

[Tompko]

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

Re:Hard? (Samsung Galaxy S3)

[Anonymous Coward]

You just dropped your tinfoil hat. There it is.

It's tough if it goes to 11?

[Anonymous Coward]

Imagine that.

Re:define the difficulty level of a sudoku

[TaoPhoenix]

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.

Uncreative

[hort_wort]

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.

extra hard sudoku = pointless

[decora]

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

[mwvdlee]

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.

actually you are wrong.

[decora]

please check http://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:actually you are wrong.

[Anonymous Coward]

depends on what HIS formula is... the series he is promoting is
1+3=4
4+5=9
9+7=16
16+9=25
25+11=36
36+13=49
49+15=64... and so on...

nothing says it has to be what you think it is - i.e. largest square=sum of squares

i am sure the mathematicians here can derive the formula for this.

Re:actually you are wrong.

[otterpop81]

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

Re:actually you are wrong.

[Fjandr]

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

World's Wrongest Sudoku?

[KritonK]

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?

[Tompko]

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?

[KritonK]

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?

[Tompko]

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

Re:World's Wrongest Sudoku?

[KritonK]

Hmm, now that you mention it, I see that the solution in the article's comments is also wrong, as cell D6 has a value of 3. instead of 5. Perhaps the puzzle does have only one solution, after all, and this is why most of my runs produce the same result.

It looks like this puzzle is one of the hardest to type, if not to solve!

Re:World's Wrongest Sudoku?

[Tompko]

My solver finds all solutions to a given puzzle, when given a choice it recurses through all possible branches and returns all valid solutions. For this puzzle it returns only one.

Re:Really Slashdot? WTF?

[bbbaldie]

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.

Is this puzzable solvable with no guessing at all?

[NoahsMyBro]

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.

Fork

[Anonymous Coward]

While you can put down a number grid and by process of elimination get the right ones is a possible fork where you guess a number's position really what this is about?

After all, when is it considered hard and when is it not sudoku? if you have a puzzle with 4-5 forks it's more guessing than solving. In that case we can create a sudoku with a minimal amount of numbers and call it "the hardest" it would simply contain 15+ forks.

No brute force needed.

[Frans Faase]

If you convert this Sudoku to an exact cover problem, it can be solved by logic reduction alone. An exact cover solver that I wrote took 0.031 seconds to do this (including generating output for each reduction it made). Exact cover problems are in NP-complete, but a Sudoku that can be solved with logic reasoning alone, can always be solved with only logic reductions.

0,046 seconds

[Frans Faase]

My program for converting a Sudoku to an exact cover took 0,015 second. My program for solving an exact cover took 0,031 seconds. This time is including producing 23K output file containing log and result. This mainly due to the fact that the exact cover can be solved with only applying logic reductions, taking two columns and see if there an implication. If this is the case, all rows that do not contain a 1 value in both columns can be removed. This results in 60 rows giving the solution to the sudoku, one row for each empty position.

Re:Is this puzzable solvable with no guessing at a

[Frans Faase]

According to my exact cover program (which required only logic reductions to solve the puzzle) this sudoku can be solved without having to make any guess.

Re:Hard? (Samsung Galaxy S3)

[Gumbercules!!]

Oh no! You caught me out! My master plan has failed. I signed up to slashdot almost a decade ago, posted consistently throughout that that entire time with good karma and then wham! When I finally pull out my single, masterly Astro-Turf-Master comment, this AC foils me!

Oh the irony!

Not very hard

[igomaniac]

/Users/morten/Project/Sudoku> time sudoku worlds_hardest.sudoku
|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

I know its cheating but ...

[PenguinJeff]

I typed it up in the format that the commandline program sudoku couls understand and it solved it flatout. I made a file with the following %World's hardest sudoku: can you crack it? 8........ ..36..... .7..9.2.. .5...7... ....457.. ...1...3. ..1....68 ..85...1. .9....4.. then ran it like so sudoku -n hardest_suduko.txt you can cheat using v solves instantly even with a slow computer.

not so easy if you are using a compass only

[decora]

the old school type of geometry, where you just have a straightedge and a compass to draw circles around a point.

Re:Really Slashdot? WTF?

[rubycodez]

Chicago Herald Position Opening Announcement

Applicants for the position of Motherfucking Editor are required to appear at the interview with three mothers

Re:Hard? (Samsung Galaxy S3)

[Anonymous Coward]

That wasn't an AC.

Re:define the difficulty level of a sudoku

[jfengel]

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: Can you solve this Sudoku? Oops, you must be a bot!

Re:Really Slashdot? WTF?

[Slutticus]

Tone it down you stuttering bald fuck? Fat chance!

The Challenge to Me...

[Nom du Keyboard]

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.

Promoter said hard sudoku need trial and error

[Anonymous Coward]

The English promoter of sudoku, in one of his many books, indicated that the hard puzzles would need trial and error and that several false starts were to be expected. In my view, it is a logic problem and can, nay must, be solved by logic. No lets try a 5 here?

The hexadecimal version just takes too long, the binary version is really too short. The only real problem is that, if you put it down, like a crossword, when you pick it back up, you have to reload short term memory. So it is solved best in one sitting.

Sudoku Solver in AWK

[Anonymous Coward]

I think we can estimate the Sudoku difficulty by using this:

http://www.thegeekstuff.com/2010/01/yet-another-sudoku-puzzle-solver-using-awk/

Re:Hard? (Samsung Galaxy S3)

[Gumbercules!!]

Ummm, yes. Yes it was.

i don't do sudoku, so i do sudoku code

[Anonymous Coward]

A few years ago a friend gave me a daily calendar with sudoku puzzles. I'm not really into solving pencil-and-paper puzzles, but I didn't want to just give it away without using it somehow first. So I wrote a sudoku solver. First I implemented a basic solver for constraint satisfaction problems (CSPs). It's about 360 lines of C++ (including the header file). Then I wrote the sudoku solver on top of that. It's about 260 lines. Running it on this problem on a basic few-year-old OTS desktop solved it in ~0.6s.

Here's the interesting thing. Before I ran the solver on this problem, I thought that "hard" for pencil-and-paper solving is different than hard for a CSP solver. But I was wrong. My solver solves the old sample problems I had from the calendar in 0.1-0.2s, about 4 to 6 times faster than this hard one. So this one is measurably harder!

Re:Emacs Lisp

[Anonymous Coward]

My Emacs Lisp program took 16 seconds to solve this. It uses a backtracking technique when it gets stuck - I think this is the "brute force" method mentioned in other notes.

What's with all the failures?

[Anonymous Coward]

Yet another commenter who can't enter the damn initial numbers correctly. You've put the first '5' in the wrong cell.

fight! fight! fight!

[Hognoxious]

Next time you're bored write a sudoku generator then sit back and watch them slug it out.

Re:fight! fight! fight!

[FitForTheSun]

My question, though, is whether such a setup would ever halt.

Re:fight! fight! fight!

[RockDoctor]

That would rather depend on whether or not you wrote a halting condition into the code.

metagame

[Hognoxious]

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.

Re:Emacs Lisp

[Anonymous Coward]

If you do have such a solution, why not provide a link? I would like to see the code.

old news

[Anonymous Coward]

http://www.dailymail.co.uk/news/article-2166680/True-test-genius-monumental-waste-time-Can-solve-hardest-Sudoku.html

with the answer

Some people think they can brute-force it

[Anonymous Coward]

They also think they are God and will live forever or at least more than 1450 billion years.

Certainly not the hardest

[Anonymous Coward]

It's certainly not the hardest puzzle if you can actually solve it by deduction. I've seen puzzles that have no way to solve except to make several of "guess and check" branches and see which one allows the puzzle to be solved. And yes, I do know all the funky mathematical tricks to the game, and even wrote a program to do so just to make sure I wasn't missing anything. I wish I still had that puzzle so I could post here, but it was the only one I've found that I've ever given up on. It had only 17 numbers pre-filled, which is the minimum that guarantees a unique solution.