Backtracking is an algorithmic technique for finding solutions to some computational problems. This technique is basically used in constraint satisfaction problems.
A backtracking algorithm tries to build a solution to a computational problem incrementally. Whenever the algorithm needs to decide between two alternatives to the next component of the solution, it simply tries both options recursively.
An Application of Backtracking
There are many problems, which are solved by this technique, such as Sudoku, crosswords, etc. Moreover, backtracking is the basis of many programming languages, such as Prolog, Icon etc.
Eight queens puzzle is the most common example, which is solved by backtracking technique. In this problem, eight number of queens are placed on a chessboard in such a way that none of them is able to attack any other queen.
In this approach, a partial candidate is created with k number of queens in the first k number of rows of the chess board. If none of them is able to attack any other queen, the algorithm tries to place the next queen. Otherwise, the previous arrangement of k queens is rejected.
This technique is faster than brute force, because this technique eliminates significant number of candidates in every test. This technique proceeds in incremental way.
In this technique, a potential search tree is generated, where each partial candidates are considered as nodes. In every level candidates are extended and they differ by one step. Hence, the leaves of the formed tree are not extendable.
This tree is traversed recursively downwards starting from the root (following DFS). At each node of the tree, the algorithm verifies whether the goal can be achieved using this child. Otherwise the subtree is skipped.
Posts
No comments:
Post a Comment