John Gaughan wrote: > syamsul_bachri87 wrote: >> my teacher gave me a task to make sudoku game with C or pascal. >> i don't understand the algorithm. >> please help me!! >> > > Sudoku is a fun problem to solve using computer science. I have written > a few programs both for generating and solving these puzzles, and am > never quite satisfied. While there are some good techniques it is a very > complex problem that has no easy solution. > > I recommend googling for sudoku programs. I cannot find it now but I did > find a site that had a JavaScript solver. I converted it to C++ and used > it, but it was incomplete. Regardless, it had enough algorithms that it > could solve most medium difficulty puzzles. > > The core difficulty I saw was that unlike most problems I have > encountered, sudoku is really a collection of problems and multiple > algorithms that feed into each other. Programs look for specific > patterns in the solution space and prune out impossibilities. The thing > that really twists your brain is that to write a program that is > provably correct you will need to combine these algorithms to look for > even more complex patterns, and after a while it consumes so much memory > and time it is ridiculous.
What are you talking about? A while back I wrote a Sudoku solver that solves _any_ standard Nonomino Sudoku in under 1 second. The standard 3x3 or 4x4 Sudoku board is just a special case of Nonomino Sudoku. It only took a couple hours to author the solver too (in C++) and can handle up to 36x36 Nonomino Sudoku boards. On any given 3x3 or 4x4 puzzle there are only 2-4 points (at most) where you have to brute-force the search space (i.e. copy the board state for backtracking purposes) but incorrect choices are almost always instantly resolved. Boards are generally designed to be solved by humans which makes them even easier to be solved by a computer. In terms of memory consumption, only 3-4 depth trackers are needed - maybe 300K of memory _at most_. The only way I can envision using untold amounts of memory is to use a depth tracker every time a value is placed. However, Sudoku is well-suited for significant logical reduction at each board depth - making future depths even faster to process. -- Thomas Hruska CubicleSoft President Ph: 517-803-4197 *NEW* MyTaskFocus 1.1 Get on task. Stay on task. http://www.CubicleSoft.com/MyTaskFocus/
