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.
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?
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.
This will be tomorrow's news.
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.
812753649 943682175 675491283 154237896 369845721 287169534 521974368 438526917 796318452
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.
-
But it's not symmetric! All good sudoku puzzles should be rotationally symmetric.
How much brute force does it take to draw a wang on Marmaduke?
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.
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
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!
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.
You have to find the simplest rule/law that describes the given numbers and use that to predict the next numbers.
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?
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 ...
You just dropped your tinfoil hat. There it is.
Imagine that.
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?
That's called combinatorial search - that you consider it "brute force" just shows you are clueless.
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.
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.
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."
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.
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.
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.
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.
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.
Kolmogorov complexity is only well-defined up to a constant.
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.
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.
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
That wasn't an AC.
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!
This is the level of comment that gets +5 insightful on slashdot these days?
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."
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.
I think we can estimate the Sudoku difficulty by using this:
http://www.thegeekstuff.com/2010/01/yet-another-sudoku-puzzle-solver-using-awk/
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.
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!
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!
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.
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.
Yet another commenter who can't enter the damn initial numbers correctly. You've put the first '5' in the wrong cell.
CPAN, or it doesn't exist!
http://search.cpan.org/~mehner/Games-Sudoku-Solver-1.1.0/lib/Games/Sudoku/Solver.pm
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."
If you do have such a solution, why not provide a link? I would like to see the code.
Wrong. The answer is 31. That is a list of all my favorite numbers. The last one in the list is 70.
http://www.dailymail.co.uk/news/article-2166680/True-test-genius-monumental-waste-time-Can-solve-hardest-Sudoku.html
with the answer
see also: http://www.dailymail.co.uk/news/article-2166680/True-test-genius-monumental-waste-time-Can-solve-hardest-Sudoku.html
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.
They also think they are God and will live forever or at least more than 1450 billion years.
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.