问题标签 [knights-tour]

我想解决骑士巡回赛的难题。当我搜索它时，我知道有很多方法可以解决它。事实上，解决它的非常有效和快速的算法包括 Warnsdoff 规则。但实际上我从来不想复制它们中的任何一个。然后我在纸上看到了一个描述解决这个问题的方法的视频。视频的链接是 www.youtube.com%2Fwatch%3Fv%3DdWM5pKYZCHw&b=28 我不知道这种方法是否已经使用，但我决定遵循. 这是算法的链接。首先，我将解释解决骑士巡回赛的方法。我们假设我们有一个 8*8 的棋盘，并且我们已经给出了马的起始位置。现在我将板子细分为 4 个系统的盒子。左菱形系统，右菱形系统，左方系统，右方系统。首先，我将检查骑士在哪个系统中启动。然后我将首先填充该系统，然后我将进入下一个系统。为了填充该系统，我将首先进入当前块。整个板子被细分为 4 个块（每个块是（4*4），正如您从视频中看到的那样。填充该块后，我将移动到下一个块，依此类推。填充所有块后，我将移动到下一个系统。现在我几乎做到了。我已经做了一些功能，用于查找当前块，当前系统，移动是否可能，骑士在块中的下一步移动，块转移，最后是系统转移。现在我正在使用3D 数组，用于存储有关每个框的一些重要信息。数组大小为 [8][8][2]。在每个框的第一个元素中，我存储系统编号 i。e 我已经为四个系统中的每一个分配了特定的编号，以便以后识别它们。左菱形系统=1，右菱形系统=2，左方系统=3，右方系统=4。在每个盒子的下一个元素中，我存储了关于盒子的信息，无论我是否已经搬进了它。一开始这些都是零，但随着我的进步，我会将它们设为 1 我移动了哪个盒子。现在我处于预测试模式，并且在 nextmove 函数中遇到了一些逻辑问题。其余功能运行良好。我在这里给出了编码，但我只给出了代码中重要的选定部分。我忘记的一件事是我将骑士的当前位置存储在一个名为当前位置的数组中，并且我将在移动时更改当前位置。在整个代码中，m代表骑士的当前行，k代表当前列。这是代码

此外，movepossible 功能也运行良好。现在的问题是，当我调用下一个移动函数时，它会正确移动第一和第二移动，但不会在块中移动第三移动。事实上，一个特定系统的一个块中总共有三个移动，换句话说，它不会移动到块中的最后一个框。它不依赖于起始位置，对于每个起始位置，它的行为都是这样的。现在我花了很多时间来寻找问题所在，但没有找到。所以请告诉我问题出在哪里。另外，如果您有任何改进逻辑和代码的建议。当我进入起始位置（4,3）时，代码的输出是这样的

但输出应该是这样的（仅适用于（4,3））

我一直在编写代码来解决骑士的旅行问题。我写了这段代码，现在我有点困惑。我重新阅读并分析了好几次，但无法找到导致问题的错误。我将不胜感激。

例如对于 i_kinghtour(0,0,1) 我得到：
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0
0 0 0
0 0 0

我应该得到：
1 20 17 12 3
16 11 2 7 18
21 24 19 4 13
10 15 6 23 8
25 22 9 14 5

我在做这个家庭作业时遇到了一些问题。它应该使用一个骑士棋子并由用户在棋盘上的起始位置，看看它是否可以触及棋盘上的每个位置。我的教授已经对电路板进行了编程，所以应该没问题。我们应该编写 takeStep() 和 runTour() 代码。我只是不知道如何让它运行。任何见解都会有所帮助，所以谢谢。

我正在使用回溯在 C++ 中开发骑士之旅的程序这是我的代码：

问题是，这个应用程序只适用于第一步，我的堆栈在结束游戏之前变空了。没找到错在哪里？！

问题可能是什么？

所以我必须编写这个算法（这个版本不需要在骑士开始的同一个地方结束），我让它工作，但它太慢了。它适用于 size=8 的起始位置 x=0 和 y=0，但如果我尝试将 x 和 y 操作为例如 2 和 4，它不会在几分钟后结束。任何人都可以帮忙吗？

我试图解决骑士巡回赛的问题，而我刚刚做到了。现在我想改进它。它采用起始值，然后输出逐步指令移动（在命令行输出中）。

现在我使用的技术是，首先我根据视频中给出的解决方案将电路板分成 4 个块（此处为 www.youtube.com%2Fwatch%3Fv%3DdWM5pKYZCHw&b=28），并将整个电路板分成 4盒子系统。

在解决方案中，我必须做很多回溯来决定两种不同的可能性，这大大降低了速度。有没有办法减少或不回溯来决定两种可能性。以及任何其他改进技术的建议。这是代码的一部分（使骑士全面移动的功能）

要查看此技术的详细信息，请查看我之前的问题 Solving knight tour with c++

如果可能的话，我如何更改它以获得 n*n 谜题的解决方案。

我正在尝试使用 java 中的回溯和递归来解决 4x4 板上的骑士之旅问题，并且在输出中我得到以下步骤序列：

1 13 16 15
10 7 4 14
5 2 11 8
12 9 6 3

在右上角，14、15和16相邻，这是不可能的，因为骑士在棋盘上移动成L形。如果有人可以帮助我解决这个问题，我将不胜感激。

编码：

在 8x8 板上回溯解决骑士巡回赛问题需要多长时间？因为我的算法已经以某种方式计算得太长了，而且看起来，它不会完成。但是当我尝试 6x6 或 5x5 板时，它成功完成。

编码：

代码对我来说似乎很好，但是输出太短了，当它应该是肯定的时候答案是否定的（从 a,0 开始，骑士应该能够游览整个棋盘）

顺便说一句，我的positionsVisted数组是 [9][9] 的原因是因为我希望值是 1-8，以匹配输出。

这是程序的输出：

我在序言中构建了一个代码，以找到一系列合法的动作，其中骑士恰好落在棋盘的每个方格（8x8）上一次。

我使用了如下逻辑：有 8 种类型的骑士动作：

• 右 1 下 2
• 左 1 下 2
• 右 2 下 1
• 左 2 下 1
• 右 1 上 2
• 左 1 上 2
• 右 2 上 1
• 左 2 上 1

右 1 下 2 步：

这对所有 8 种类型的动作都重复

问题是我的代码效率不高，找到正确的路径需要太多步骤。有谁知道解决这个问题的有效方法？