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)."
Is there any proof that the classical dynamics corresponding to any given problem will settle in the ground state in a finite time? Or, in other words, could there be Sudoku puzzles with infinite hardness ?
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.
Edit submission before posting.
When you paste >'s and <'s into a submission they'll be treated as HTML tags
Sudokus are all the same difficulty: easy. Simple pairing method can solve almost any sudoku so long as you stick to pairing. The only difficulty comes when it's a multiple solution sudoku in which case it just depends on the first number you start working with.
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?!
Clearly didn't read the paper. There's a huge category of "almost" that most people don't find fun.
The difficulty lies in the algorithms required to solve the puzzle. Difficult puzzles have "choke points" that you cannot go past (not counting guessing) unless you can identify a pattern that fits an algorithm. That is hard for two reasons. One, you have to know the algorithms, and the advanced ones are not intuitive (like X-Wing, Swordfish, etc). Second, you have to spend a lot of time staring at numbers trying to recognize a pattern that you can use the algorithm on.
So when it comes to "hard" puzzles, the difficulty depends on which specific algorithms must be used to solve the puzzle, and other less obvious factors, such as how difficult it is to identify the pattern. For example, if you must use an advanced algorithm early on, before many numbers have been solved, then there are more penciled in numbers to analyze, thus the puzzle is more difficult and will take longer to solve.
Better known as 318230.
all you need to do is to compute its , a co-efficient that measures the hardness of the problem.
Which is apparently so hard to do no-one can even name the thing. Or is it just called ","?
systemd is Roko's Basilisk.
Somebody's rewritten the summary since the tag 'itswhat' was added, and I think they just removed the fragmented sentence that ended with '[...] has calculated its .' (its value of something?)
With this part removed, it makes even LESS SENSE. Just rewrite it completely!
On a "News for Nerds" site, I have to question why we're calling it a "Richter scale" instead of simply a "log-scale".
with no attribution to xkcd either.
http://xkcd.com/74/
obviously violates the CC BY-NC 2.5 license
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.
Sudoku is probably the most boring puzzle game ever. Read a book, dammit.
Is there anything that mathematicians can't do?
The new right fascists are bilingual. They speak English and Bullshit.