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.
-
8Think very fast?– Hot LicksJul 8, 2012 at 11:30
-
1(language==undefined)//return true;– user1432124Jul 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 )– wildplasserJul 8, 2012 at 11:39
-
use elimination: sudokublog.typepad.com/photos/uncategorized/elimstep1.png– Karoly HorvathJul 8, 2012 at 12:04
-
Can you post an example puzzle that should be doable in 1s?– uselpaOct 25, 2014 at 7:38
2 Answers
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.
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...
-
In prunning, it costs much more time to determine whether continue searching or just backtrack– PoligunJul 9, 2012 at 7:18