c++ - Knights Tour 中使用回溯的问题
问题描述
当我尝试使用回溯运行 Knights Tour 问题的解决方案时,我遇到了一个无限循环
我的解决方案代码:链接:https ://ideone.com/Ud92vF 代码:
#include <bits/stdc++.h>
using namespace std;
bool valid(int arr[8][8],int r,int c)
{
if(r>=0 and r<8 and c>=0 and c<8 and arr[r][c]== -1)
return true;
return false;
}
void fun(int arr[8][8],int r,int c,int x)
{
if(x==64){
cout<<"***********************ARRAY FOUND***********************\n";
for(int i=0;i<8;i++){
for(int j=0;j<8;j++)
cout<<arr[i][j]<<" ";
cout<<"\n";
}
return;
}
if(!valid(arr,r,c))
return;
arr[r][c] = x;
fun(arr,r-2,c+1,x+1); fun(arr,r-2,c-1,x+1);
fun(arr,r-2,c+2,x+1); fun(arr,r-2,c-2,x+1);
fun(arr,r+2,c+1,x+1); fun(arr,r+2,c-1,x+1);
fun(arr,r+1,c+2,x+1); fun(arr,r+1,c-2,x+1);
arr[r][c] = -1;
}
int main()
{
int arr[8][8] ;
for(int i=0;i<8;i++){
for(int j=0;j<8;j++)
arr[i][j] = -1;
}
int r=0,c=0,x=0; fun(arr,r,c,x);
}
解决方案
确保你的移动数组是正确的:
fun(arr,r-2,c-1,x+1); fun(arr,r-2,c+1,x+1);
fun(arr,r-1,c-2,x+1); fun(arr,r-1,c+2,x+1);
fun(arr,r+1,c-2,x+1); fun(arr,r+1,c+2,x+1);
fun(arr,r+2,c-1,x+1); fun(arr,r+2,c+1,x+1);
有了这个,我得到了正确的答案:
***********************ARRAY FOUND***********************
0 11 8 5 2 13 16 19
9 6 1 12 17 20 3 14
30 27 10 7 4 15 18 21
63 24 31 28 35 22 47 44
32 29 26 23 48 45 36 57
25 62 51 34 39 56 43 46
52 33 60 49 54 41 58 37
61 50 53 40 59 38 55 42
请注意,当您使用第 65 步来验证您的答案时,您将连续获得 8 个相同的正确答案。然后是另一个 8. 等等。您可以通过在第 64 次移动后打印来解决此问题:
void fun(int arr[8][8],int r,int c,int x)
{
if(!valid(arr,r,c))
return;
arr[r][c] = x;
if(x==63){
cout<<"***********************ARRAY FOUND***********************\n";
for(int i=0;i<8;i++){
for(int j=0;j<8;j++)
cout<<arr[i][j]<<" ";
cout<<"\n";
}
}
else
{
fun(arr,r-2,c-1,x+1); fun(arr,r-2,c+1,x+1);
fun(arr,r-1,c-2,x+1); fun(arr,r-1,c+2,x+1);
fun(arr,r+1,c-2,x+1); fun(arr,r+1,c+2,x+1);
fun(arr,r+2,c-1,x+1); fun(arr,r+2,c+1,x+1);
}
arr[r][c] = -1;
}
最后一个问题是您只能从 {0,0} 开始,因此您只会发现从该广场开始的骑士之旅。你真的想从每一个方格开始寻找所有可能的骑士之旅。或者,如果您觉得自己很聪明,您只需要检查起始方块的子集并使用对称性来生成其他方块。
推荐阅读
- javascript - 从 promise.then / promise.catch 中获取原始函数名
- ios - 如何自动快速记录电话?
- r - 向饼图添加值和百分比
- java - 在控制器中返回错误时,Spring MVC ResponseEntity 始终为空
- html - 如何使下拉菜单看起来好像是从按钮后面出来的?
- api - 在构建 Java GraphQL API 时,如何避免从数据库中过度获取(即仅获取查询中指定的字段)?
- headless - 导航图标在 layout.html 中加载,但不在撇号无头 api 的片段中
- android - 微调器数组列表
- java - 如何解决?我对java非常陌生
- c# - C# 我可以延迟将数据库中的项目添加到 get 属性中吗?