Slashdot Mirror
World's Hardest Sudoku
jones_supa writes "A Finnish PhD in mathematics, Arto Inkala, has allegedly created the world's toughest sudoku puzzle. 'There's no straightforward way to define the difficulty level of a sudoku. I myself doubt if this is the hardest in the world, but definitely harder than my previous ones,' Inkala sets off humbly. The news agencies around Europe are nonetheless excited (Google translation of Finnish original). The particular difficulty in this version lies in the number of deductions you have to make in order to fill in a single number on the grid. 'It is a common misconception that the less initial numbers, the harder the puzzle. The most challenging ones have 21-25', the creator adds."
You mean easy for your sudoku-solver ?
brute force != solving a sudoku
I'm printing it out now, nothing like someone claiming the impossible to make you want to try and prove them wrong.
You don't have to use brute-force solvers. I wrote one that codified my thinking processes and the rules I was operating buy, so that it solved them the way I would.
It's still sorta cheating, but it's not a brute-force.
Who cares about the Higgs boson?
Sudoku is real science!
brute force != solving a sudoku
Yes it is. It's a totally pointless activity, but you have certainly solved it if you end up with the right answer.
If someone asks me what is the next number in the sequence 1, 4, 9, 16, 25 and I say "36" that is the correct solution whether I knew it, guessed it or worked it out in any way whaatsoever.
To have a right to do a thing is not at all the same as to be right in doing it
It wasn't hard at all - My Galaxy S3 with Google Goggles solved it in under 3 seconds.
:-P
Of course, I personally, don't even know the rules of Sudoku.
Would love to give it a shot!
The following crappy solver I cobbled together solved it in 33 seconds under Cygwin:
https://github.com/fhstoica/NumbersAndLettersSudokuSolver
Check out Peter Norvig's web site for a very elegant solver and look for the "impossible puzzle" if you really want a difficult one:
http://norvig.com/sudoku.html
Some excellent news about the Higgs particle is announced more than 0.5 hr ago, I come hear to Slashdot to read what everyone has to say.....and the font page headline here is about motherfucking Sodoku. Really? Are the editors asleep, apathetic or all of the above? Fuck.
"'It is a common misconception that the less initial numbers..."
When you have discrete, countable units, such as the symbols, in this case numbers, already present on the Sudoku grid, you have more or you have fewer .
When it's something you can't count, you have more or you have less.
I have more 16x16 grid sheets printed up for hexadecimal Sudoku, because those are the ones I copy from 'the net'.
I have fewer (currently none, actually) of the 9x9 (4 to a page) printed because I quit doing the 1-9 version sometime back.
I'm going to try this one out, but suspect it will turn out to be the type that lets you get just so far with logic and then leaves you no alternative but trial and error, just like the Saturday ones in a certain Raleigh newspaper.
I see even classic Slashdot is now pretty much unusable on dial up anymore.
brute force != solving a sudoku
You can't brute force a sudoku, it would take about 1450 billion years using a super duper computer using only brute force. But you could use different solving techniques. Quote Peter Norvig:
"First, we could try a brute force approach. Suppose we have a very efficient program that takes only one instruction to evaluate a position, and that we have access to the next-generation computing technology, let's say a 10GHz processor with 1024 cores, and let's say we could afford a million of them, and while we're shopping, let's say we also pick up a time machine and go back 13 billion years to the origin of the universe and start our program running. We can then compute that we'd be almost 1% done with this one puzzle by now." http://norvig.com/sudoku.html
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.
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 :)
In the context of game solving, most people consider tree search with constraint checking but no guiding heuristics to be brute force.
http://www.theonion.com/articles/caltech-physicists-successfully-split-the-bill,2037/
but at least they were topical.
today's top story: worlds hardest sudoku
summary: not actually the world's hardest sudoku.
more at 11.
Dam. You beat me to it.
I am putting you all on sudoku watch.
brute force != solving a sudoku
Actually it is. All search is an exercise in brute force with the problem space reduced by heuristics. The trick is to reduce the problem space to as small as possible by using good heuristics.
Definitely not one of the hardest sudokus.
There is a tool to compute the difficulty of a puzzle, and you can also download a massive database of hard sudokus (5 millions+):
http://code.google.com/p/skfr-sudoku-fast-rating/
For reference, this one is rated 10.7:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-420.html
BTW, there is a database of 31804 puzzles of difficulty 11 and above:
http://gpenet.pagesperso-orange.fr/downloads/hard11.zip
Exactly 7 have a rank of 11.9.
maybe i'm a super programmer then, since i wrote a brute force sudoku solver in 10 min that can solve sudokus in max 100ms on my aging laptop.
Wealth is the gift that keeps on giving.
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.
HI O WISE PRINCE. WHT TOOK U SO DAM LONG?
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!
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.
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.
-
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
ics
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 ...
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.
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
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.
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!
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
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
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
When people say "brute force", they don't necessarily mean complete randomness.
It's trivial to check whether a state is valid. For instance, if you have two identical numbers in one 3x3 square, row, column or diagonal, you can ignore the rest of that branch.
Slashdot social media options: AIM, ICQ, Yahoo, Jabber and Mobile Text. Why no MySpace?
You're Finnished already?
You are welcome on my lawn.
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.
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.
Troll is not a replacement for I disagree.
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.
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)
"His name was James Damore."
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.
"His name was James Damore."
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.
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.
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
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.
Troll is not a replacement for I disagree.
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.
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"
"His name was James Damore."
It's even easier if you click the link at the bottom of the Telegraph website that says "answer"
http://www.telegraph.co.uk/science/science-news/9360022/Worlds-hardest-sudoku-the-answer.html
This post contains benzene, nitrosamines, formaldehyde and hydrogen cyanide.
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.
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.
Troll is not a replacement for I disagree.
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?
How is the Riemann zeta function like Trump rallies? Both have an endless number of trivial zeros.
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.
How can we continue to believe in a just universe and freedom to eat crackers if we have no ale?
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.
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.
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.
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!
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.
"His name was James Damore."
|8 1 2|7 5 3|6 4 9|
|9 4 3|6 8 2|1 7 5|
|6 7 5|4 9 1|2 8 3|
|1 5 4|2 3 7|8 9 6|
|3 6 9|8 4 5|7 2 1|
|2 8 7|1 6 9|5 3 4|
|5 2 1|9 7 4|3 6 8|
|4 3 8|5 2 6|9 1 7|
|7 9 6|3 1 8|4 5 2|
real 0m0.083s
user 0m0.073s
sys 0m0.003s
The interactive way to Go -- http://www.playgo.to/iwtg/en/
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.
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.
the old school type of geometry, where you just have a straightedge and a compass to draw circles around a point.
Does it also make guesses that are several levels deep? I found the bookkeeping involved rather overwhelming.
Can you post code?
source, or it didn't happen!
Chicago Herald Position Opening Announcement
Applicants for the position of Motherfucking Editor are required to appear at the interview with three mothers
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!
Tone it down you stuttering bald fuck? Fat chance!
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.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
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.
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.
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".
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.
Ummm, yes. Yes it was.
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.
Not a sentence!
Reminds me of my favorite Dilbert comic.
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.
Next time you're bored write a sudoku generator then sit back and watch them slug it out.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
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.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
Wrong. The answer is 31. That is a list of all my favorite numbers. The last one in the list is 70.
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.
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.