图解回溯算法

backtracing

---

1.骑士巡回问题

回溯是一种算法范例，尝试不同的解决方案，直到找到一个「有效」的解决方案。通常使用回溯解决的问题具有以下共同特性。这些问题只能通过尝试每种可能的配置来解决，并且每种配置只尝试一次。对于这些问题，一个简单的解决方案是尝试所有配置，并输出符合给定问题约束的配置。回溯是一种渐进式的工作方式，是对原始解决方案的优化，所有可能的配置都会生成并尝试。

例如，考虑以下骑士巡回问题

描述

给出一个N✖️N的棋盘，骑士被放在一块空棋盘的第一块上。按照象棋的规则，骑士的移动必须准确地访问每个方块一次。打印每个单元格的访问顺序。

例子

Input : 
N = 8
Output:
0  59  38  33  30  17   8  63
37  34  31  60   9  62  29  16
58   1  36  39  32  27  18   7
35  48  41  26  61  10  15  28
42  57   2  49  40  23   6  19
47  50  45  54  25  20  11  14
56  43  52   3  22  13  24   5
51  46  55  44  53   4  21  12

在一个8✖️8的棋盘上，骑士所走的点如下: