12 posts

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

Back to Forum: Coffeehouse
• 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

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

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

It seems to be a very tough problem...

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

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

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

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

• I'll go over parallel and DNA computing.