问题:
给定一个N * N棋盘,骑士位于空棋盘的第一块。按照国际象棋的规则,骑士必须访问每个方格一次。打印每个方格被访问的顺序。
- 我使用了回溯,但没有得到任何输出**
#include <bits/stdc++.h>
using namespace std;
bool valid(int a, int b)
{
//check validity
if (a < 0 || a > 7 || b < 0 || b > 7)
return false;
return true;
}
bool backtrack(vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j)
{
//ans found
if (chess[i][j] == 63)
return true;
else
{
bool flag = false;
for (int k = 0; k < moves.size(); k++)
{
int a = i + moves[k].first, b = j + moves[k].second;
//if valid.. and not already visited
if (valid(a, b) && chess[a][b] == -1)
{
chess[a][b] = chess[i][j] + 1;
//recurse for next moves
flag = backtrack(chess, moves, a, b);
//if solution not found..backtrack
if (!flag)
chess[a][b] = -1;
//break..return ans
else
break;
}
}
return flag;
}
}
int main()
{
vector<vector<int>> chess(8, vector<int>(8, -1));
vector<pair<int, int>> moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};
chess[0][0] = 0;
backtrack(chess, moves, 0, 0);
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
cout << chess[i][j] << " ";
}
cout << endl;
}
return 0;
}
3条答案
按热度按时间tcomlyy61#
将移动的顺序更改为(较不纠结的)
它会起作用的,很快
有多种可能的解决方案。也有其他策略来选择搜索顺序,这可能会改善事情。
这里是一个替代版本,让您发挥与董事会的大小:
jtjikinw2#
我没有发现任何无限循环,但是你的代码从来没有到达打印行,因为你使用的是一个蛮力搜索算法,而且你使用的电路板尺寸太大,不可能在合理的时间内用蛮力计算出来。
维基百科上说,在一个8x8棋盘上有“26,534,728,821,064个封闭的图尔斯”,基本上这意味着你可以为该棋盘找到的解的数量。
用蛮力搜索马的路线在最小的棋盘上是不切实际的,例如,在一个8 × 8的棋盘上有大约4×1051个可能的移动序列,这远远超出了现代计算机的能力(或计算机网络)来对如此大的集合执行操作。然而,这个数字的大小并不表明问题的难度,这个问题可以“通过人类的洞察力和聪明才智......不费吹灰之力”解决。-维基百科(骑士之旅-暴力算法)
这意味着在这么大的空间里找到其中一个解的可能性非常低。
您需要使用另一个运行时更快的算法,例如分治算法或该页上列出的其他算法。
wbrvyc0a3#
你的代码中没有bug。简单地说,算法必须稍微改进才能更快。
一个技巧是首先选择那些没有太多未来邻居的细胞。
在下面的代码中,
经过这样的修改,我几乎是瞬间就得到了结果,即使N = 20。