## The Chaos Within Sudoku - a Richter Scale of Difficulty 74

Posted
by
samzenpus

from the give-it-a-number dept.

from the give-it-a-number dept.

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 ? (Score:2, Interesting)

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: (Score:1)

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: (Score:1)

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 ? (Score:5, Funny)

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: (Score:2)

Congratulations on your job with Microsoft.

## Re: (Score:2)

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: (Score:3)

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: (Score:2)

## Re: (Score:2)

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: (Score:3)

## Huh? (Score:5, Informative)

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: (Score:2)

## Re:Huh? (Score:4, Insightful)

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: (Score:2)

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 , (Score:2, Funny)

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

## Re: (Score:2)

## Tip for editors; (Score:1)

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

## Re: (Score:1)

## Re: (Score:2)

## Who cares? (Score:1)

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.

## Re: (Score:1)

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: (Score:2)

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

## Re: (Score:3)

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: (Score:2)

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

## Re: (Score:1)

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 (Score:3)

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: (Score:2)

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: (Score:1)

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: (Score:2)

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

## Re: (Score:2)

## Chaos... what? (Score:5, Insightful)

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: (Score:1)

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: (Score:1)

## Re: (Score:2)

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

## Algorithms (Score:2)

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

## Re: (Score:2)

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

## Re: (Score:1)

## Re: (Score:2)

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 possibili

## Re: (Score:2)

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

## Re: (Score:3)

## Re: (Score:2)

## Compute its what? (Score:1)

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

## Richter scale? (Score:2)

## Re: (Score:3)

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

A Richter-type scale for Sudoku hardness

## There are no hard sudoku (Score:2)

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

## Re: (Score:2)

## Re: (Score:1)

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.

## Not again (Score:1)

## Re: (Score:2)

No. No there is not.