马踏棋盘问题 — 深搜和贪心算法

同学面试阿里，被问到了马踏棋盘的问题，作为非计算机专业的门外汉，完全没有听说过，只听说过马踏飞燕。抓紧去搜了一下，发现还是个经典算法，题目是这样的：

国际象棋的棋盘为8*8的方格棋盘。现将”马”放在任意指定的方格中，按照”马”走棋的规则将”马”进行移动。要求每个方格只能进入一次，最终使得”马”走遍棋盘的64个方格。

这个问题一般有两种思路来解决，一种就是用深度优先搜索，采用递归+回溯的方式，一个棋盘可以看成有64层深度的一棵树，每一个节点最多有8个子节点，采用深搜可以很方便的解决这个问题，但是深搜这个方法时间复杂度太高了，最多要搜8^64次（实际存在边界和已经访问的标记，虽然不会这么多次，也是很大），太过盲目；

还有一种方式就是采用贪心算法，每次选择下一步的时候，不像深搜那样，每次都沿着一圈8个方向顺序搜，瞎眼走到黑，而是采用贪心算法，选择眼前认为最优的点。这里什么是最优的点，就是选择后续节点最少的那一个，哪一个点的下一步少，就选哪一个。基于贪心算法可以快速的得搜索到结果，效率提高很多。

下面是自己调试的代码，采用递归的深搜算法和在此基础上改进的贪心算法：

#include <iostream> #include <vector> using namespace std; int move_x[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; int move_y[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; void Judge(vector<vector<int>>& pan, vector<vector<int>>& flag, vector<vector<int>>& path, int m, int n, int& edge, int count, int& found) { if (found) //设定找到一次就可以退出了 return; if (count >= edge*edge) //当记录次数等于8*8=64次，说明马已经踏过了所有棋盘 { found += 1; //把记录的路径保存在path中 for (int i = 0; i < edge; i++) { for (int j = 0; j < edge; j++) path[i][j] = flag[i][j]; } return; } if (m > edge-1 || n > edge-1 || m < 0 || n < 0 || flag[m][n] != 0) //边界条件，出了边界就退回，悬崖勒马 return; count++; //满足在边界之内，没有被访问过，计数加1 flag[m][n] = count; //对应节点记录访问顺序，第几次被访问的 for (int i = 0; i < 8;i++)//八个方向顺序搜索 Judge(pan, flag, path, m + move_x[i], n + move_y[i], edge, count, found); //采用递归，进行下一步的搜索 flag[m][n] = 0; //回溯，对应节点标记清零 } int main() { int m,n; int edge; int found = 0; cin >> edge>> m >> n; vector<vector<int>> pan(edge, vector<int>(edge, 0)); vector<vector<int>> flag(edge, vector<int>(edge, 0)); vector<vector<int>> path(edge, vector<int>(edge, 0)); Judge(pan, flag, path, m, n, edge, 0, found); cout << found<<endl; for (int i = 0; i < edge; i++) { for (int j = 0; j < edge; j++) cout << path[i][j] << " "; cout << endl; } system("pause"); return 0; }

在深搜的基础上加入贪心算法，在选择下一步时候加入了判断

#include <iostream> #include <vector> using namespace std; int move_x[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; int move_y[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; void Judge(vector<vector<int>>& pan, vector<vector<int>>& flag, vector<vector<int>>& path, int m, int n, int& edge, int count, int& found) { if (found) //设定找到一次就可以退出了 return; if (count >= edge*edge) //当记录次数等于8*8=64次，说明马已经踏过了所有棋盘 { found += 1; //把记录的路径保存在path中 for (int i = 0; i < edge; i++) { for (int j = 0; j < edge; j++) path[i][j] = flag[i][j]; } return; } if (m > edge-1 || n > edge-1 || m < 0 || n < 0 || flag[m][n] != 0) //边界条件，出了边界就退回，悬崖勒马 return; count++; //满足在边界之内，没有被访问过，计数加1 flag[m][n] = count; //对应节点记录访问顺序，第几次被访问的 /*贪心算法,确定下一次的方向*/ int count_next[8] = {-1,-1,-1,-1,-1,-1,-1,-1}; for (int i = 0; i < edge; i++) { int m_next = m + move_x[i]; int n_next = n + move_y[i]; if (m_next < edge && n_next < edge && m_next >= 0 && n_next >= 0 && flag[m_next][n_next] == 0) { count_next[i] ++; for (int j = 0; j < edge; j++) { int m_next_next = m_next + move_x[j]; int n_next_next = n_next + move_y[j]; if (m_next_next < edge && n_next_next < edge && m_next_next >= 0 && n_next_next >= 0 && flag[m_next_next][n_next_next] == 0) count_next[i]++; } } } int opt_direct = 0; //记录下一步的方向 for (int i = 0; i < edge; i++) { if (count_next[opt_direct] == -1) opt_direct = i; if ((count_next[i] < count_next[opt_direct]) && count_next[i] != -1) { opt_direct = i; } } Judge(pan, flag, path, m + move_x[opt_direct], n + move_y[opt_direct], edge, count, found); //采用递归，进行下一步的搜索 flag[m][n] = 0; //回溯，对应节点标记清零 } int main() { int m,n; int edge; int found = 0; cin >> edge>> m >> n; vector<vector<int>> pan(edge, vector<int>(edge, 0)); vector<vector<int>> flag(edge, vector<int>(edge, 0)); vector<vector<int>> path(edge, vector<int>(edge, 0)); Judge(pan, flag, path, m, n, edge, 0, found); cout << found<<endl; for (int i = 0; i < edge; i++) { for (int j = 0; j < edge; j++) cout << path[i][j] << " "; cout << endl; } system("pause"); return 0; }

实践证明，当棋盘是8*8的时候，*把马儿放在任何一个初始位置，都可以走完全部棋盘，当棋盘是5*5的时候，只有部分初始位置才能走完全部棋盘。