c++ - 国际象棋骑士巡回赛遇到困难
问题描述
我尝试使用回溯为骑士之旅问题编写代码。我的代码适用于 4x4 矩阵,但对于 8x8 矩阵,它没有在输出屏幕上显示任何内容。
我不知道我做错了什么。
这就是我的代码的工作方式:
如果所有方块都被访问
print the solution
别的
将接下来的移动之一添加到解决方案向量并递归检查此移动是否导致解决方案。(一个骑士最多可以走八步。我们在这一步中选择八步中的一个)。
如果在上述步骤中选择的移动没有导致解决方案,则从解决方案向量中删除该移动并尝试其他替代移动。
如果没有任何替代方法起作用,则返回 false(返回 false 将删除以前在递归中添加的项目,如果初始调用递归返回 false,则“不存在解决方案”)
这是我写的代码:
#include<iostream>
using namespace std;
#define n 8
int safe(int c[n][n],int i, int j)
{
if((i>=0&&i<n)&&(j>=0&&j<n))
{
if(c[i][j])
return 0;
else
return 1;
}
return 0;
}
int knightstour(int c[n][n],int i,int j,int k)
{
if(k==n*n)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}
return 1;
}
else
{
c[i][j]=k;
if(safe(c,i+2,j+1))
{
if(knightstour(c,i+2,j+1,k+1))
return 1;
}
if(safe(c,i+2,j-1))
{
if(knightstour(c,i+2,j-1,k+1))
return 1;
}
if(safe(c,i-2,j+1))
{
if(knightstour(c,i-2,j+1,k+1))
return 1;
}
if(safe(c,i-2,j-1))
{
if(knightstour(c,i-2,j-1,k+1))
return 1;
}
if(safe(c,i+1,j+2))
{
if(knightstour(c,i+1,j+2,k+1))
return 1;
}
if(safe(c,i-1,j+2))
{
if(knightstour(c,i-1,j+2,k+1))
return 1;
}
if(safe(c,i+1,j-2))
{
if(knightstour(c,i+1,j-2,k+1))
return 1;
}
if(safe(c,i-1,j-2))
{
if(knightstour(c,i-1,j-2,k+1))
return 1;
}
c[i][j]=0;
return 0;
}
}
int main()
{
int c[n][n]={0};
if(!knightstour(c,0,0,0))
cout<<"solution doesn't exist";
return 1;
}
解决方案
让我们暂时假设您的算法是正确的,因为它似乎至少产生了一些有用的东西n == 6
:
0 13 20 23 34 11
21 30 35 12 19 24
14 1 22 31 10 33
29 4 7 16 25 18
6 15 2 27 32 9
3 28 5 8 17 26
以下是使用各种值运行代码的时钟时间结果n
:
===== 1 0m 0.001s
===== 2 0m 0.001s
===== 3 0m 0.003s
===== 4 0m 0.002s
===== 5 0m 0.070s
===== 6 0m 35.997s
===== 7 ...
你会注意到我还没有那个数字n = 7
,它还在继续,在 5.5 小时并且还在计数:-)
由于它至少会持续那么长时间(大约 330 分钟),我们可能可以使用回归分析计算尺寸 8 的最小数字(使用仅使用尺寸 5、6 和不完整 7 的数据的二次多项式)(一)。根据这些计算,这个最小数字约为 16.5 小时。
但是,即使它不是二次的,对于 6x6 板它跳到 36 秒和对于 7x7 跳到(至少)5.5 小时这一事实意味着您使用的算法不能很好地扩展。所以你可能会发现它正在工作,你可能只需要等待一段时间。可能很长一段时间:-)
(a)如果您有兴趣(或想检查/批评我的方法),这是我的分析。警告:前面的数学...
我们有数据集:
x (value of n) y (seconds taken)
-------------- -----------------
5 0.07
6 36.00
7 600.00 (when it had been running ten minutes)
使用公式:
y = ax^2 + bx + c
我们最终得到联立方程:
0.07 = 25a + 5b + c (1)
36 = 36a + 6b + c (2)
600 = 49a + 7b + c (3)
减去对给我们:
(2) - (1): 35.93 = 11a + b (4)
(3) - (2): 564 = 13a + b (5)
(5) - (4): 528.07 = 2a
所以a = 264.035
。将其代入 to(5)
给我们,并将b = -2868.455
其代入给我们。将这三个值放入方程中,并为我们提供预期值。a
b
(3)
c = 7741.47
(1)
(2)
(3)
这是使用的方法(从我的高中时代开始),但当然,最好使用快速而肮脏的 Python 程序来完成,该程序在600
图形发生变化时可以快速运行:
import sys
y5 = 0.07 ; y6 = 36 ; y7 = int(sys.argv[1]) * 60
a = ((y7 - y6) - (y6 - y5)) / 2
b = (y7 - y6) - 13 * a
c = y7 - 49 * a - 7 * b
y8 = 64 * a + 8 * b + c
print(y8, y8 / 3600)
您可以运行它,提供大小 7 的当前值,它将推出最小数字(以秒和小时为单位)。
推荐阅读
- visualization - turicreate 可视化决策树
- java - Spring Hibernate,GET Query,Hibernate Query 已成功形成,我能够从 DB 获取数据,但是当我从浏览器中点击它时,它会抛出 404
- google-apps-script - 自定义 Google Data Studio 连接器的数据类型 DURATION 失败
- memory - CUDA 合并和全局内存
- function - 要运行的数据:必须将哪些数据传递给 minikanren 才能获得评估?
- java - Android 自定义属性返回 null
- python - 我将如何扭转这一局面?蟒蛇 3.8
- entity-framework - 在实体框架身份中查询客户端评估
- javascript - 如何在具有管理员权限的 Firebase 中初始化应用程序
- javascript - 在随机位置用 0 填充数组