25,161
edits
Changes
no edit summary
Classic examples of using backtracking algorithms are solving [https://en.wikipedia.org/wiki/Exact_cover Exact cover problems] and [https://en.wikipedia.org/wiki/Tour_puzzle Tour puzzles], like the [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle], the [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour puzzle] and other [https://en.wikipedia.org/wiki/Maze Maze] or [https://en.wikipedia.org/wiki/Labyrinth Labyrinth] puzzles. [[Donald Knuth|Knuth's]] [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Algorithm X] along with [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links] finds all solutions to an exact cover problem. Backtracking is further applied to solving [https://en.wikipedia.org/wiki/Constraint_satisfaction_problem Constraint satisfaction problems], such as [https://en.wikipedia.org/wiki/Crosswords Crossword puzzles], [https://en.wikipedia.org/wiki/Sudoku Sudoku], [https://en.wikipedia.org/wiki/Pentomino Pentomino] tiling, [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem boolean satisfiability problems] and other [https://en.wikipedia.org/wiki/NP-complete NP-complete problems]. [https://en.wikipedia.org/wiki/Logic_programming Logic programming languages] such as [[Prolog]] internally use backtracking to generate answers.
==De Bruijn sequencesSequences== A further sample is to find [[De Bruijn sequenceSequence|De Bruijn sequences]], as demonstrated by the recursive [[De Bruijn Sequence Generator]]. Here early partial candidates may be discarded if the lock indicates a new six-bit number already occured before.
==Looking for Magics==
