Slashdot Mirror
The Chaos Within Sudoku - a Richter Scale of Difficulty
mikejuk writes "A pair of computer scientists from the Babes-Bolyai University (Romania) and the University of Notre Dame (USA) have made some remarkable connections between Sudoku, the classic k-SAT problem, and the even more classic non-linear continuous dynamics.
But before we go into the detail let's look at what this means for Sudoku enthusiasts. Maria Ercsey-Ravasz and Zoltan Toroczkai have devised a scale that provides an accurate determination of a Sudoku puzzle's hardness. So when you encounter a puzzle labelled hard and you find it easy, all you need to do is to compute a co-efficient that measures the hardness of the problem. An easy puzzle should fall in the range 0-1, medium ones in 1-2, hard ones in 2-3, and for ultra-hard puzzles, 3+, with the hardest puzzle, the notorious Platinum Blond, being top of the scale at 3.6. We will have to wait to see if newspapers and websites start to use this measure of difficulty. The difficulty is measured by the time it takes the classical dynamics corresponding to the problem to settle in the ground state and this depends on the degree of chaos in the search for a solution (PDF)."
We will have to wait to see if newspapers and websites start to use this measure of difficulty
Why would they? What's the incentive for grandma to see the Sudoku as '1.1' instead of 'Hard' ?
Write boring code, not shiny code!
Compute its comma? I think the editors accidentally a word.
Sudoku puzzles are like solving simultaneous equations, sometimes it's really easy to fill in a cell - it's the last empty one in a row, for instance. One equation. Sometimes you need to keep track of many cells and their effects to solve them all at once.
The difficulty of a sudoku depends on how many cells have to be solved at once in the most difficult set in the puzzle. There could also be a number of difficult sets that individually are moderately difficult, but taken as a whole require some endurance. Those are probably more satisfying to solve than a puzzle with a huge set, but they're not more difficult.
If I needed a hardness rating, that's what I'd pick - the the number of cells in the largest group that must be solved together. This chaos method offers no fidelity. 0-3 is easy and the hardest puzzle they found to study is 3.6, wth?
Can you be Even More Awesome?!
It's possible to design a Soduku that is ambiguous; meaning, there is more that one acceptible answer. I image that such a puzzle could be considered "infinitely hard". But, could such a puzzle be considered a Soduku? Does the definition of a Soduku require that it only have one answer?
Because that's what the authors used on their paper:
A Richter-type scale for Sudoku hardness
Dilbert RSS feed
Sudoku's are really simple for computers. Simply map them to an Exact Cover and then solve the Exact Cover by reduction. Never takes more than a few seconds, even for the most hard ones. This is because Sudoku's have one solution and I have never come across a Sudoku that has one solution and cannot be solved by simple logic reasoning. There do exist Exact Covers that have one solution, but require guessing. But even if some Sudoku would require some guessing, it still cannot be a complex problem, and a back-tracking algorithm would solve it quickly. See Hardest Sudoku for some more details, algorithms and such.
It gets much, MUCH more complicated than that.
In the "most" difficult puzzles you can actually reach a point where you cannot gain any additional useful information by logic (even triples exclusion, X-wing exclusion and other less obvious to the naked eye things) and are forced to guess on a square, test the validity of that guess, then potentially rewind and guess again. Computers can actually solve any valid sudoku purely by this method, but it's not as fun as teasing out the logic (if it exists).
You probably have never seen enough really nasty puzzles to realize that those techniques will not work.
Here is a valid, single solution Sudoku that using your technique may result in your insanity.
46...1...
1..2....8
Good luck.
You are being MICROattacked, from various angles, in a SOFT manner.
I'm not being flippant or showing off, but for a while when they first came about in the UK papers I was partial to the odd Sudoku and in order to speed up the process of grid filling, I printed out some prepared grids with all the little numbers (the ones you're supposed to pencil in) in every single box.
Then after filling in the published starting numbers it became a simple task to simply black out those small numbers that were no longer possible i.e all the ones of the same number in the same square, row or column). Then almost invariably I'd be left with a number of squares that could be filled and the process repeated. Then, as with normal play I'd find a row column or square with pairs or triples of numbers enabling other numbers to be black out. This would solve most Sudoku, and it didn't even require any thinking.
And that's what ultimately weaned me off the things. I was essentially imitating a computer process, blacking out and filling in numbers as the rules laid down allowed. In other words utterly pointless and boring.
There are puzzles this won't solve, but then there's no actual skill to be employed in solving those ones either. Sudoku guides would bill this as "ariadne's thread", but ultimately it comes down to guesswork. When you're stuck then you have to pick a square and take a guess. If you're right, and it works, you solve the puzzle, otherwise your guess was wrong, you go back to where you were and choose the other number. To give it another name: brute force. No skill, no intelligence, just number crunching. Sudoku puzzles aren't puzzles at all, they're just an exercise in box filling.
I think that mathematical labels on human issues are usually false. There should be an analysis on the techniques used by novice solvers, then rate whether the puzzle is solvable with only those techniques, and the number of iterations necessary (for the 0-3 range), then, for the 4-7 range, look at the intermediate solvers. Then, for the 8-10 hardness, the techniques talked about here may be appropriate, as some are solvable only through trial and error.
Learn to love Alaska
I started a new job. In the first week I heard the CEO tell the VP to 'go fuck himself' in the hall. I knew I was home.
Perhaps you just work with pussies.
John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'