Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Math Games

The Chaos Within Sudoku - a Richter Scale of Difficulty 74

Posted by samzenpus 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)."
This discussion has been archived. No new comments can be posted.

The Chaos Within Sudoku - a Richter Scale of Difficulty More

The Chaos Within Sudoku - a Richter Scale of Difficulty

Comments Filter:

  • Infinite Hardness ? (Score:2, Interesting)

    by mbone ( 558574 )

    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 ?

    • Re: (Score:1)

      by gl4ss ( 559668 )

      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 ?

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

      by dmomo ( 256005 )

      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?

      • It is easy to define a Soduku with more than one solution. Just take a Soduko and remove some hints. Great chance it will now have multiple solutions.

      • Re: (Score:2)

        by gl4ss ( 559668 )

        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)

      by AK Marc ( 707885 )
      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.

  • Huh? (Score:5, Informative)

    by Pieroxy ( 222434 ) on Sunday August 05, 2012 @12:14PM (#40886639) Homepage

    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)

      by 1u3hr ( 530656 )
      Especially since the "measure" is an invisible "eta". See TFA to discover the Greek letters and mathematical symbols that these idiots lost when they pasted it into Slashdot.

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

      by ThatsMyNick ( 2004126 ) on Sunday August 05, 2012 @01:57PM (#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.

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

    by Anonymous Coward

    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
    • My fault - there is a missing greek (I always think that should be geek) letter before the comma and I didn't see that the gt lt signs had been removed.

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

      by Anonymous Coward

      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.

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

    • I am guessing you are referring to unique rectangles and variants.

      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.

      .318....7
      ........9
      ....6..2.
      46...1...
      ..3.7...6
      1..2....8
      .2...59..
      ..5.3....
      .....2.4.

      .318....7........9....6..2.46...1.....3.7...61..2....8.2...59....5.3.........2.4.

      Good luck.

      • Sorry, s/techniques will not work/techniques will not always work/

        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.

        • 931 824 657
          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.

      • This was trivial.

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

        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

        • Got it. I misread what you were saying. Basically, you are doing two simultaneous guesses. Cool, will look for this more often.

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

    by zippthorne ( 748122 ) on Sunday August 05, 2012 @12:21PM (#40886717) Journal

    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?

    • Re: (Score:1)

      by Anonymous Coward

      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)

      by finity ( 535067 )
      There are a lot of ways to look at hard, somewhat generic problems, like Sudoku. Have you seen the SAT problem? http://en.m.wikipedia.org/wiki/Boolean_satisfiability_problem [wikipedia.org] One way to consider it is like you describe - a set of simultaneous equations. Another way to consider it is to use the equations and some rules to draw a graph, then perform graph operations. NP problems are an active area of academic interest. It's generally not possible to know how hard these problems are before solving them, s

    • 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

  • 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

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

      • Re: (Score:1)

        by dalias ( 1978986 )
        Only?

      • Re: (Score:2)

        by jeremyp ( 130771 )

        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

        • 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

    • 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 bac

      • Re: (Score:2)

        by e70838 ( 976799 )
        Sudoku is very efficiently solved using DLX (dancing links). It solves thousands of sudoku per second whatever the level of difficulty.

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

  • On a "News for Nerds" site, I have to question why we're calling it a "Richter scale" instead of simply a "log-scale".

  • 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

  • Is there anything that mathematicians can't do?

Slashdot Top Deals

THEGODDESSOFTHENETHASTWISTINGFINGERSANDHERVOICEISLIKEAJAVELININTHENIGHTDUDE

Close