回溯算法和遞歸算法

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 solution
Elsea) 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 solutionthen 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)

翻譯自: https://www.freecodecamp.org/news/backtracking-algorithms-recursive-search/

回溯算法和遞歸算法