回溯算法和递归算法

Examples where backtracking can be used to solve puzzles or problems include:

回溯可用于解决难题或问题的示例包括：

1. Puzzles such as eight queens puzzle, crosswords, verbal arithmetic, Sudoku [nb 1], and Peg Solitaire.
   诸如八个皇后难题，填字游戏，口头算术，数独[nb 1]和钉接龙等难题。
2. Combinatorial optimization problems such as parsing and the knapsack problem.
   组合优化问题，例如解析和背包问题。
3. Logic programming languages such as Icon, Planner and Prolog, which use backtracking internally to generate answers.
   逻辑编程语言(例如Icon，Planner和Prolog)在内部使用回溯来生成答案。

示例问题(骑士的旅行问题) (Example Problem (The Knight’s tour problem))

The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once.

骑士被放置在一个空棋盘的第一块上，并且根据国际象棋的规则移动，必须对每个广场精确地访问一次。

骑士走过的路覆盖了所有牢房 (Path followed by Knight to cover all the cells)

Following is chessboard with 8 x 8 cells. Numbers in cells indicate move number of Knight.

以下是带有8 x 8格的棋盘。 单元格中的数字表示骑士的移动次数。

骑士之旅的朴素算法 (Naive Algorithm for Knight’s tour)

The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints.

朴素算法是一一生成所有巡视，并检查生成的巡视是否满足约束条件。

while there are untried tours{    generate the next tour    if this tour covers all squares    {       print this path;   }}

骑士之旅的回溯算法 (Backtracking Algorithm for Knight’s tour)

Following is the Backtracking algorithm for Knight’s tour problem.

以下是骑士巡回问题的回溯算法。

If all squares are visited     print the solutionElse   a) Add one of the next moves to solution vector and recursively    check if this move leads to a solution. (A Knight can make maximum    eight moves. We choose one of the 8 moves in this step).   b) If the move chosen in the above step doesn't lead to a solution   then remove this move from the solution vector and try other    alternative moves.   c) If none of the alternatives work then return false (Returning false    will remove the previously added item in recursion and if false is    returned by the initial call of recursion then "no solution exists" )

这是给你的视频说明 (And here's a video explanation for you)

翻译自:

回溯算法和递归算法