马踏棋盘c++非递归

### 马踏棋盘问题的非递归解决方案 马踏棋盘问题是经典的回溯算法问题，目标是让“马”从棋盘上的某个位置出发，按照国际象棋中“马”的走法，遍历整个棋盘且每个格子只访问一次。以下是一个基于栈的非递归实现方案。 #### 1. 栈的使用 为了实现非递归版本的马踏棋盘问题，可以使用栈来模拟递归调用的过程。栈是一种后进先出（LIFO）的数据结构，能够很好地支持回溯操作[^2]。 #### 2. 算法实现 以下是完整的C++代码实现： ```cpp #include <iostream> #include <stack> #include <vector> using namespace std; const int N = 8; // 棋盘大小 int s[N][N] = {0}; // 棋盘状态数组 bool visited[N][N] = {false}; // 访问标记数组 vector<pair<int, int>> moves = { {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1} }; // 八个方向 struct State { int x, y; // 当前位置 int count; // 当前步数 int dir; // 当前方向索引 }; // 判断是否越界 bool isValid(int x, int y) { return x >= 0 && x < N && y >= 0 && y < N && !visited[x][y]; } // 输出解 void output_solution() { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cout << setw(3) << s[i][j]; } cout << endl; } } int main() { stack<State> stk; State start = {0, 0, 1, 0}; // 起点为(0, 0) s[0][0] = 1; visited[0][0] = true; stk.push(start); while (!stk.empty()) { State current = stk.top(); stk.pop(); if (current.count > N * N) { output_solution(); // 找到解 break; } bool found = false; for (int i = current.dir; i < moves.size(); ++i) { int tx = current.x + moves[i].first; int ty = current.y + moves[i].second; if (isValid(tx, ty)) { State next = {tx, ty, current.count + 1, 0}; s[tx][ty] = current.count + 1; visited[tx][ty] = true; stk.push(State{current.x, current.y, current.count, i + 1}); // 保存当前状态 stk.push(next); // 推入下一个状态 found = true; break; } } if (!found) { // 回溯 visited[current.x][current.y] = false; s[current.x][current.y] = 0; } } return 0; } ``` #### 3. 关键点解释 - **栈的作用**：栈用于保存当前状态以及可能的下一步状态。通过栈的操作，避免了递归调用带来的函数栈开销。 - **回溯机制**：当某个方向无法继续时，弹出栈顶元素并重新搜索其他方向[^2]。 - **状态表示**：`State`结构体包含当前位置、当前步数以及当前方向索引，便于在栈中保存和恢复状态。 #### 4. 时间复杂度与空间复杂度 - **时间复杂度**：由于需要尝试所有可能的路径，最坏情况下时间复杂度为 \(O(N^2 \times 8^N)\)，其中 \(N\) 为棋盘边长。 - **空间复杂度**：主要由栈的空间决定，最坏情况下为 \(O(N^2)\)。