# The Chaos Within Sudoku - a Richter Scale of Difficulty

#### samzenpus posted more than 2 years ago | from the give-it-a-number dept.

74
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)."*

## Infinite Hardness ? (1, Interesting)

## mbone (558574) | more than 2 years ago | (#40886567)

Is there any proof that the classical dynamics corresponding to any given problem

willsettle in the ground state in a finite time? Or, in other words, could there be Sudoku puzzles with infinite hardness ?## Re:Infinite Hardness ? (0)

## gl4ss (559668) | more than 2 years ago | (#40886589)

Is there any proof that the classical dynamics corresponding to any given problem

willsettle in the ground state in a finite time? Or, in other words, could there be Sudoku puzzles with infinite hardness ?sure, make the starting setup impossible to finish. pretty easy to argue though that in a case like that proving that it can't be finished would be the solution, as the sudoku board is certainly finite in size and possible markings on it, it most certainly isn't infinite. it's just a fucking sudoku you know.

## Re:Infinite Hardness ? (-1)

## Anonymous Coward | more than 2 years ago | (#40886821)

It has been shown in studies that people who bandy about profanity for no reason or reasons of base humor - are not taken seriously at work and rarely progress. In your case, I suspect you are a 45 year old first-tier Help Desk monkey.

## Re:Infinite Hardness ? (-1)

## Anonymous Coward | more than 2 years ago | (#40887023)

It has been shown that when faggots like you are punched in the throat,

their trachea collapses and they cannot ever suck cock well again.

## Re:Infinite Hardness ? (0)

## russotto (537200) | more than 2 years ago | (#40887387)

Unless you're in management, you're by definition at the bottom of the hierarchy, whether you're a Help Desk monkey or a Principal Engineer. I have no desire to be in management. Therefore, fuck you.

## Re:Infinite Hardness ? (4, Funny)

## HornWumpus (783565) | more than 2 years ago | (#40889245)

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.

## Re:Infinite Hardness ? (1)

## Galaga88 (148206) | more than 2 years ago | (#40893739)

Congratulations on your job with Microsoft.

## Re:Infinite Hardness ? (0)

## Anonymous Coward | more than 2 years ago | (#40894703)

Watch out for chairs.

## Re:Infinite Hardness ? (1)

## gl4ss (559668) | more than 2 years ago | (#40893003)

It has been shown in studies that people who bandy about profanity for no reason or reasons of base humor - are not taken seriously at work and rarely progress. In your case, I suspect you are a 45 year old first-tier Help Desk monkey.

how the hell would someone who keeps spouting profanities manage to keep a helpdesk job?

stupid answer for a stupid question, if a problem has possible solutions it can't be infinitely hard to solve, furthermore sudokus are stupid.

## Re:Infinite Hardness ? (2)

## dmomo (256005) | more than 2 years ago | (#40886895)

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?

## Re:Infinite Hardness ? (1)

## Frans Faase (648933) | more than 2 years ago | (#40887269)

## Re:Infinite Hardness ? (0)

## Anonymous Coward | more than 2 years ago | (#40887399)

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?

a true Sudoku has only 1 solution

## Re:Infinite Hardness ? (1)

## gl4ss (559668) | more than 2 years ago | (#40892885)

a sudoku with multiple answers wouldn't qualify as being infinitely hard, it would qualify as easier.

if the rules were such that you had to end up with specific solution or all the possible solutions, then it would be a bit harder, but in the specific solution required it would be just a

trick question.## Re:Infinite Hardness ? (0)

## Anonymous Coward | more than 2 years ago | (#40887333)

Yep. Pick any size grid. No starting numbers. Go!

## Re:Infinite Hardness ? (0)

## Anonymous Coward | more than 2 years ago | (#40894387)

That's not infinitely hard. A blank sudoku is a trivially easy puzzle. It is also one with multiple answers.

## Re:Infinite Hardness ? (2)

## AK Marc (707885) | more than 2 years ago | (#40889125)

## Huh? (4, Informative)

## Pieroxy (222434) | more than 2 years ago | (#40886639)

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' ?

## Re:Huh? (1)

## 1u3hr (530656) | more than 2 years ago | (#40886801)

## Re:Huh? (0)

## Anonymous Coward | more than 2 years ago | (#40887073)

forget about eta. The reason is bad parsing of < and > signs as HTML tag delimiters. I was confused as to why 0-3 is easy but hardest is 3.6.

## Re:Huh? (3, Insightful)

## ThatsMyNick (2004126) | more than 2 years ago | (#40887423)

No, but Grandma will be disappointed if an easy puzzle is marked as hard. If I ran a newspaper, I would run this score, and define scores 0-1.5 Easy 1.5-2.5 Medium and 2.5+ Hard. This was grandma is not confused, neither is she disappointed by the hardness level.

## Re:Huh? (1)

## LordLimecat (1103839) | more than 2 years ago | (#40888079)

Multiply the number by 30 and we're in business. 0-45= easy, 45-75=medium, 75+=hard. The aforementioned "Platinum Blond" would be a 108, but whatever.

## All you need to to is compute its , (2, Funny)

## Anonymous Coward | more than 2 years ago | (#40886649)

Compute its comma? I think the editors accidentally a word.

## Re:All you need to to is compute its , (1)

## bistromath007 (1253428) | more than 2 years ago | (#40891627)

## Tip for editors; (1)

## 91degrees (207121) | more than 2 years ago | (#40886675)

When you paste >'s and <'s into a submission they'll be treated as HTML tags

## Re:Tip for editors; (-1)

## Anonymous Coward | more than 2 years ago | (#40886701)

I'm wondering if samzenpus drank too much last night. He's delivered three terrible summaries for three terrible "stories" in a row.

## Re:Tip for editors; (1)

## Megane (129182) | more than 2 years ago | (#40887601)

## Re:Tip for editors; (1)

## mikejuk (1801200) | more than 2 years ago | (#40886789)

## Re:Tip for editors; (0)

## Anonymous Coward | more than 2 years ago | (#40887895)

## Who cares? (0)

## JMJimmy (2036122) | more than 2 years ago | (#40886687)

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.

## Ignorance is bliss (0)

## Anonymous Coward | more than 2 years ago | (#40886811)

Clearly didn't read the paper. There's a huge category of "almost" that most people don't find fun.

## Re:Who cares? (1)

## Anonymous Coward | more than 2 years ago | (#40886983)

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 should have one unique solution else they are in error.

## Re:Who cares? (1)

## JMJimmy (2036122) | more than 2 years ago | (#40894727)

Computer Science 101 - build a simple brute force sudoku solver which solves for every variant. See how false that statement is.

## Re:Who cares? (0)

## Anonymous Coward | more than 2 years ago | (#40887215)

Strictly speaking, yes. But in terms of the amount of effort required, they can vary. And that's what the scale is based on. e.g. you can find at least one square with one possibility. and as you start filling, others follow the suit. Then for the next level, you have cases where square 1 can have {x,y} and square 7 can have {x,y}. In that case you can't determine either's value but you can eliminate those values from other squares in the row. This allows you to proceed a little further and you can revisit sqaures 1 & 7 later.

## Re:Who cares? (2)

## Yobgod Ababua (68687) | more than 2 years ago | (#40888369)

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

## Re:Who cares? (1)

## JMJimmy (2036122) | more than 2 years ago | (#40894877)

While "pairing" maybe an over simplified way of describing it, the method I use requires that I only "place" possible numbers if they fit in 2 boxes. If they fit in 3 the possibilities are ignored. The reasons for this are as follows:

- Eliminating 1 of the 2 possibilities immediately gets a result

- Often (not always) provides straight lines which can be used to eliminate other possibilities

- When a straight line isn't available, one can "assume" the position of a number, tease out the logic, if it doesn't work out you know it's not a possibility and the other location is.

- once you have any 2 possibilities in both boxes of a possible number set you can immediately eliminate all other numbers as possibilities.

## Re:Who cares? (1)

## Anonymous Coward | more than 2 years ago | (#40889811)

you can find at least one square with one possibility

If that were the case, all Sudokus would be easy: Find that square, fill it in. You get a new Sudoku. By your assertion this new Sudoku also has one square with an unique solution, etc.

## Try this nasty Sudoku (2)

## SpaceLifeForm (228190) | more than 2 years ago | (#40888481)

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.

## Re:Try this nasty Sudoku (1)

## SpaceLifeForm (228190) | more than 2 years ago | (#40888521)

Unique rectangles and variants are actually a very powerful technique. But, they are not enough for really nasty puzzles. There are too many possibilities to keep track of.

## Re:Try this nasty Sudoku (1)

## DMUTPeregrine (612791) | more than 2 years ago | (#40889209)

642 157 389

578 963 124

467 381 592

283 579 416

159 246 738

824 615 973

795 438 261

316 792 845

Lots of "forcing chains" to solve it, no use of unique rectangles.

## Re:Try this nasty Sudoku (1)

## JMJimmy (2036122) | more than 2 years ago | (#40895333)

This was trivial.

You can quickly get the board to this state: .3182...7 ..2.....9 ....6..2. .2...59.. ..5.3.... .....2.4.

46.3.1...

2.3.7...6

1..2..6..8

This doesn't seem like much having only placed 5 numbers... but the bottom right and middle right boxes now only have two places each where 2 can go. This means that either it's a multiple solution (which you've stated is not the case) so I now know that if I tease out one solution by placing a 2 in two of those 4 boxes it will either be right or wrong. Once you get the correct 2 they fall quickly in this order: 4, 6, 5, 7, 8, 3, 1, 9

## Re:Try this nasty Sudoku (1)

## SpaceLifeForm (228190) | more than 2 years ago | (#40909651)

## Re:Who cares? (0)

## Anonymous Coward | more than 2 years ago | (#40889765)

A sudoku with more than one solution is broken. Solving a sudoku with only one method is boring. What's the point? Aren't you curious to find out new rules?

## Chaos... what? (4, Insightful)

## zippthorne (748122) | more than 2 years ago | (#40886717)

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

satisfyingto solve than a puzzle with a huge set, but they're not moredifficult.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?

## Re:Chaos... what? (0)

## Anonymous Coward | more than 2 years ago | (#40887267)

RTFA. /. editors are lazy. This is an example of HTML tag parsing gone bad and no one bothering to fix it.

To save you some pain: 0-1 is easy, 1-2 is medium, 2-3 is hard and 3.6 is hardest possible.

## Re:Chaos... what? (1)

## Anonymous Coward | more than 2 years ago | (#40890005)

The Richter scale is a log scale, 4 (10,000) is 10 time more than 3 (1000). In decimal there is thus a rather large difference between 3 and 3.6 on a log scale.....

## Re:Chaos... what? (1)

## finity (535067) | more than 2 years ago | (#40893741)

## Re:Chaos... what? (1)

## freality (324306) | more than 2 years ago | (#40901075)

So, I think the solution process for an arbitrary system of simultaneous equations actually has a *propensity* to lead to deterministic chaos. I was just looking for a paper discussing this, but came up short; but for the background see:

http://en.wikipedia.org/wiki/Iterated_function_system [wikipedia.org]

Note, the way I'm interpreting this is that *solving* the system leads to iteration of candidate systems in your head, therefore there's an (hypothetical) expected chaotic dynamic. (haven't rtfa yet.. :)

Is there something about the way sudoku systems are chosen, e.g. they're too simple, that excludes this?

## Thanks (-1, Offtopic)

## asifmushtaq38 (2648429) | more than 2 years ago | (#40886729)

## I computed my puzzle's , (-1)

## Anonymous Coward | more than 2 years ago | (#40886823)

and it was everything I imagined and even more

## Algorithms (1)

## Dan East (318230) | more than 2 years ago | (#40886837)

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

mustbe 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.## Re:Algorithms (1)

## russotto (537200) | more than 2 years ago | (#40886875)

Or you could just use a brute-force solver. It only takes 2^54 tries, max, to solve any given puzzle.

## Re:Algorithms (1)

## dalias (1978986) | more than 2 years ago | (#40887001)

## Re:Algorithms (1)

## jeremyp (130771) | more than 2 years ago | (#40893115)

It's actually much lower than that. Taking into account all the symmetries (i.e. rotations, reflections and the fact that you can swap all instances of any pair of numbers) there are only just over 40,000 different final grids.

I once wrote a brute force solver with a small amount of logic to eliminate illegal solutions i.e. if you put a 1 in the top left corner, it noted in all the there squares on the same row, column and small square, that you weren't allowed a 1. If that left a square with no possibilities, it would back track and try a different number.

I was quite surprised that my solver would solve any puzzle in less than a second.

## Re:Algorithms (1)

## russotto (537200) | more than 2 years ago | (#40897701)

You're describing a backtracking solver, which is what most people mean by a brute-force sudoku solver. I'm referring to the dumbest brute force solver -- iterate through all possible combinations of the missing numbers, checking if each is a valid grid. Number of attempts is max 64^9 (81 numbers on the grid, a minimum 17 clues, 9 possibilities for each number) = 2^54

Wikipedia claims the number of essentially distinct complete grids is 5,472,730,538. I'm not sure if you could, given a partial grid, do a lookup into a canonical set of complete grids without doing as much work as you would trying every possible rotation and permutation.

## Re:Algorithms (2)

## Frans Faase (648933) | more than 2 years ago | (#40887409)

## Re:Algorithms (1)

## e70838 (976799) | more than 2 years ago | (#40895033)

## Compute its what? (0)

## wonkey_monkey (2592601) | more than 2 years ago | (#40886859)

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 ","?

## Quote the submitter (-1)

## Anonymous Coward | more than 2 years ago | (#40886867)

"I accidentally a variable symbol"

## NEWS FLASH !! MICROSOFT ISSUING NIKE SNEAKERS !! (-1)

## Anonymous Coward | more than 2 years ago | (#40886929)

Microsoft is said to be issuing purple Nike running shoes to all employees world-wide ahead of the 26 October lauching of their mothership !!

According to those involved, this man

http://upload.wikimedia.org/wikipedia/commons/2/21/Steve_Ballmer_at_CES_2010_cropped.jpg [wikimedia.org]

is said to be in talks with the Kool-Aid people.

## Summary. (0)

## Anonymous Coward | more than 2 years ago | (#40886967)

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!

## Richter scale? (1)

## elfprince13 (1521333) | more than 2 years ago | (#40887033)

## Re:Richter scale? (2)

## icebraining (1313345) | more than 2 years ago | (#40887203)

Because that's what the authors used on their paper:

A Richter-type scale for Sudoku hardness

## Re:Richter scale? (0)

## Anonymous Coward | more than 2 years ago | (#41013579)

Maybe Moh's scale would have been more appropriate.

## plagiarism (0)

## Anonymous Coward | more than 2 years ago | (#40887049)

with no attribution to xkcd either.

http://xkcd.com/74/ [xkcd.com]

obviously violates the CC BY-NC 2.5 license

## There are no hard sudoku (2)

## leenoble_uk (698539) | more than 2 years ago | (#40889003)

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.

## Re:There are no hard sudoku (0)

## Anonymous Coward | more than 2 years ago | (#40889205)

You're approach sounds just like that taken by almost all computer algorithms. If you ask a strong human sudoku solver how they approach a difficult problem or situation or give them a problem you couldn't solve yourself you might be amazed by the deeper logical reasoning they use to avoid guesswork.

With Sudoku, Guesswork is never required. If you are guessing then the problem is too hard for you.

## Re:There are no hard sudoku (1)

## cryptizard (2629853) | more than 2 years ago | (#40889249)

## Re:There are no hard sudoku (0)

## Anonymous Coward | more than 2 years ago | (#40892979)

Indeed, the easiest way to ratchet up the difficulty of the AI player in chess is to just give it more time to match your moves up to known strategies and find a counter. Or predict play several moves out choosing the most optimal move to advance things in the AI's favor.

## Re:There are no hard sudoku (0)

## Anonymous Coward | more than 2 years ago | (#40893183)

People like you do make me laugh :) You may as well say they're all easy because if you turn to the back page the answer is there.

The ones you can do using your naive method are called "easy" sudoku. My 9-year-old can do these.

The ones you don't know how to do without guessing are called "medium" or "hard" sudoku.

What you're missing is that there are ways to solve these without guessing, and it's that which is the interesting part of sudoku, which takes skill, and which totally went over your head when you looked at this puzzle.

## Re:There are no hard sudoku (0)

## Anonymous Coward | more than 2 years ago | (#40894257)

Hey there,

I read all the way through your comment but you didn't link to pics explaining how guessing is unnecessary. Do you mind providing an example or two?

Another Anon

PS. Hey OP, please don't get down with these comments about people who have "other ways" and its "interesting" and "insightful" about how they solve the puzzles. I fill in the boxes with numbers as well as try and use "other ways," and at the end of the day everyone wrote numbers in boxes. If you want to really mess with people shoulder surfing you, fill in obviously wrong choices on purpose then yawn and set the puzzle down, it drives "real players" nuts.

## Re:There are no hard sudoku (1)

## Mirar (264502) | more than 2 years ago | (#40906807)

This puzzle,

http://www.telegraph.co.uk/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html [telegraph.co.uk]

will have you 'guess' no less than 10 times. I don't see right now how it measures in the 'richter' scale in the original article.

## Infinite tedium (0)

## Anonymous Coward | more than 2 years ago | (#40889627)

Sudoku is probably the most boring puzzle game ever. Read a book, dammit.

## Not again (1)

## uninformedLuddite (1334899) | more than 2 years ago | (#40900403)

## Re:Not again (1)

## meloneg (101248) | more than 2 years ago | (#40941117)

No. No there is not.