1

I've tried dancing links and some other search algorithms but it won't work within the given time limit of 1 second. For a sudoku game with about 1 million solutions it takes about 10 seconds to count all solutions.

6
  • 8
    Think very fast?
    – Hot Licks
    Jul 8, 2012 at 11:30
  • 1
    (language==undefined)//return true;
    – user1432124
    Jul 8, 2012 at 11:34
  • 1 second for 1 million results leaves you ~1000 operations per result. With lean&mean coding that should be doable, if you don't waste too much time on the non-results. ( --> pruning ) Jul 8, 2012 at 11:39
  • Can you post an example puzzle that should be doable in 1s?
    – uselpa
    Oct 25, 2014 at 7:38

2 Answers 2

2

1M results sounds a bit scary, but for fast solving basically you have to use process of elimination / constraint propagation and exhaustive search on fields with the least possible values.

An excellent article from Peter Norvig: Solving Every Sudoku Puzzle.

0

Standard solving algorithms for Sudoku (all solutions) use backtracking. Classic variant of Sudoku has only one solution (or at least should have), so there you might use human-like techniques, but this is in the case not possible. So backtracking will be probably the only way.

But you might want to use several tricks

  • Prunning of the tree (extend basic prunnign strategy of backtracking algorithm with more sophisticated conditions)
  • Massive parallelism (I think that that you might benefit of superlinear accelaration of the solution, because some sub-problems might be the same, hence solvable only once, or might prune some branches of other threads)
  • Use symmetry and some special properties of your setting, this is probably the best strategy, if you have some implicit knowledge
  • You might try some blackbox approaches - for example constraint (logic) programming, which are highly optimized in searching in massive search space...
1
  • In prunning, it costs much more time to determine whether continue searching or just backtrack
    – Poligun
    Jul 9, 2012 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.