Coffeehouse Thread

12 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

Does anyone know any efficient algorithm for solving "SUDOKU?"

Back to Forum: Coffeehouse
  • User profile image
    iStation

    Does anyone know any efficient algorithm for solving "SUDOKU" on a large scale?
    More than 9x9... [C]

    TIME Puzzles: Brain Calisthenics (2)
    http://www.time.com/time/covers/20060116/puzzles/2.html

  • User profile image
    JohnAskew

    I think there's a 12 step program for that.

  • User profile image
    DoomBringer

    I think brute force is the only way.  A DFS or BFS might do the trick.

  • User profile image
    iStation

    I found this article.
    It seems to be a very tough problem... Perplexed 

    IEEE Spectrum: Sudoku Science
    http://spectrum.ieee.org/feb06/2809

  • User profile image
    Maurits

    Though this is NP-complete, it's highly parallelizable.  A good candidate for DNA computing or a large botnet.

  • User profile image
    Sven Groot

    The article wrote:
    "The idea is, basically, you run your program, and if it's taking too long you restart it" with a new ordering, Gomes says, "because your computer may end up getting into an unlucky run, and hopefully the next run will be a lucky one."

    They needed to do research to find this out? I discovered the exact same thing not too long ago. I wanted to make a clone of Troyis for the PocketPC, and I needed more insight in how to generate levels, and as part of figuring the game out, I also wrote a solver. One of the very important things I needed to know was whether it's always possible to complete a field without stepping on the same square twice. This turned out to be the case, but I also discovered that just exhaustively seeking such a path using a fixed order might take extremely long, because the amount of possible non-optimal paths it needs to consider before finding the optimal one is insane. And so, I did what the article suggests: do it randomly, if it takes too long, restart in hopes of getting a more lucky run.

    (I'm still debating with myself whether or not I should make this clone available (for free, open source), since it is a direct clone of their game, same levels, same timing, same scoring, I even used the same image for the knight, so I don't know if I might get in trouble about IP and stuff, on the other hand since they don't provide a PDA version I'm not competing with them directly).

  • User profile image
    Sven Groot

    Maurits wrote:
    DNA computing

    Interesting proposition, but I doubt it would be possible. Even if possible, the DNA block design would be insane, and reading out the solution very difficult (checking whether there is a solution isn't too hard using gel electrophorasis, but what it is exactly is; I did this type of thing with a simple shortest path in a directed graph algorithm, and even there we could only tell the length of the shortest path, not what the path actually was). It also wouldn't be very fast, since DNA computing never is (the exact time depends on how many times you need to heat and anneal, even the short path experiment took a few hours of lab time).

    Unless you meant genetic algorithms, in which case you're probably right. Smiley

  • User profile image
    iStation

    I'll go over parallel and DNA computing.
    Thanks for advices! Cool

  • User profile image
    Jason Cox

    You could probaly get something to figure it out in .NET, shouldnt be too difficult, just alot of if/then and error checking.

  • User profile image
    Maurits
  • User profile image
    dcoolidge99​508

    Wikipedia says Dancing Links is the current algo.

  • User profile image
    iStation

    dcoolidge99508 wrote:
    Wikipedia says Dancing Links is the current algo.

    Wow, thanks for the nice link! Big Smile

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.