Animation: Sudoku puzzle solved by a brute force/backtracking algorithm. The algorithm started by filling the first empty cells with the values 1 - 9 until one of them created a valid board and moved on from there backtracking whenever doing this could not create a valid board. Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, das heißt, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert.
see: http://en.wikipedia.org/wiki/Backtracking Bildquelle: http://commons.wikimedia.org/wiki/Category:Sudoku?uselang=de#mediaviewer/File:Sudoku_solved_by_bactracking.gif CC BY-SA 3.0
