问题标签 [knights-tour]

我必须从 [0,0] 开始并访问所有广场然后返回/坐在 [0,0]

图片来自我的董事会

这是我尝试过的代码：

我的问题是 truepath 变量总是为空，我不能给出三元组

我使用 Haskell 为 Knight's tour 实现了一个递归解决方案。我的算法基本上是基于 Warnsdorff 的规则。

例子：

• 棋盘尺寸：5x5
• 起始位置：(3,3)

基于这个例子的基本思想：

(1) 计算从当前点 (3,3)
=> (1,2),(1,4),(2,1),(2,5),(4,1),(4,5)允许的移动),(5,2),(5,4)

(2) 对于这些点中的每一个，计算到达该点可以执行的移动次数（“入口”数）
=> ((1,2),2),((1,4),2) ,((2,1),2),((2,5),2),((4,1),2),((4,5),2),((5,2),2) ,((5,4),2)

(3) 如果所有点的入口数量相同，则找到入口最少的点或第一个点
=> (1,2)

(4) 调用与确定点相同的函数（开始递归）

这样我就可以确定解决问题的方法。但现在我需要确定起始位置的所有其他可能解决方案（在示例 (3,3) 中）。不幸的是，我真的不知道如何实现这一目标。

想法非常感谢。

这是我当前的 Haskell 代码（为指定的起始位置提供一种解决方案）：

我正在学习骑士的巡回算法。我使用递归精细实现，但它需要很长时间，而且几乎不是封闭的旅行。

现在，我目前正在寻找一种快速算法来查找封闭式游览。有人可以推荐我一些算法吗？

更新：我在某处读过一个启发式，可以找到像这样的封闭骑士之旅：下一步的位置是Min[F(x, y)]哪里F(x,y) is a set of f(x,y)=Min(x-1, n-x) + Min(y-1, n-y)，是棋盘的大小。但是我该如何使用这种启发式方法呢？(x, y)n

我必须提到这是我第一次在这个网站上发帖，如果我不遵守这个网站的发球指南，请原谅我。

我的问题可能很简单，但我无法理解。我的骑士之旅算法递归地找到骑士的路径。它适用于索引 [0,0]，它完美地遍历数组的空间......但是，除了索引 [0,0] 之外的任何东西，程序都会挂起看起来像是永恒的东西。这是我的代码：

所以，简而言之，我正在研究骑士的巡回演出。如果你不知道那是什么，马就会被放到棋盘上，你必须将它移动到棋盘上的每个位置恰好一次。我正在使用递归函数，但无法让我的回溯工作。我可以在 5x5 板上完成 22 步，但程序不会备份并尝试不同的路径。我只发布了我的代码的递归部分（抱歉它有点长）任何见解都会非常有帮助。非常感谢！

我是编程新手，想解决 Knights Tour 问题作为练习。所以我试了一下。我刚刚学习了递归的概念，并试图用它来解决 4X4 板的这个问题。我的代码是：

现在，当我运行它时，我得到以下输出：

这使我按照访问顺序在板上的框位置。我的问题是：

1. 点 0,0 到 3,1，倒数第二个点是 1,0 从那个点到 0,3。它不应该那样做，我试图弄清楚但我做不到。任何人都可以帮我解决这个问题，并告诉我这是如何发生的以及为什么会发生。

2. 这甚至可以像这样解决吗？我的意思是我确信有许多复杂和更复杂的算法，但我只是想要一些东西来练习递归。我学习了 DFS 算法，有点感觉，这需要同样的东西。万一它不能，可以任何人都指出我正确的方向（一个简单的方法来让它工作，它不需要针对速度或任何东西进行优化）。

谢谢。

我正在用 C# 编写一个简单的 C# 游戏 Knights Tour 程序，这是学习所有 C# 的艰难方法。我有一个棋盘和一个骑士片，骑士是一个带有骑士图片的定制面板。

我试图做的是允许用户在运行时单击并拖动骑士块控件（正是您可以在设计时移动控件以放置它的方式），但无论出于何种原因，我得到了一些非常不希望的结果。

我看不出这段代码不会做同样事情的真正原因，但我显然遗漏了一些东西。当我点击骑士并移动它时，它的移动速度与鼠标的速度不同，它的移动速度要慢得多。当它移动到你看不到的地方时，它也会消失。

我如何使骑士棋子以与表单设计器中相同的方式移动，以使棋子在棋盘上移动是有意义的？

任何帮助将不胜感激。

我稍微更新了代码，它似乎确实有所帮助，但是它的动画方面仍然很不稳定，并且面板在移动和放置时会拾取一些背景。

它是如何在表单设计器中如此顺利地完成的？

我正在尝试为Knight's Tour编写代码：

骑士之旅是一个骑士在棋盘上的一系列移动，这样骑士恰好访问每个方格一次。

我一直在尝试更改其他人的代码，但回溯似乎无法正常工作——它永远找不到解决方案。当骑士从 0、0 开始时，它工作得非常好，但如果它从 2D 网格上的任何其他位置开始，程序就会永远运行下去。

这段代码的错误在哪里？

我最近玩了一个名为Just A Trim Please的小 Flash 游戏，我非常喜欢整个概念。

游戏的基本目标是通过每个方格一次修剪整个草坪。您的割草机从瓷砖开始，您可以从那里向各个方向移动（除了有墙挡住您的地方）。如果您多次在草地瓷砖上奔跑，它会恶化并且您将失去关卡。您只能向左、向右、向上或向下移动。但是，当您完成游戏时，会添加更多图块：

• 您只能修剪一次的瓷砖（草）。
• 在恶化之前可以运行两次的瓷砖（更高的草）。
• 一条你可以随心所欲地翻越的领带（混凝土）。
• 一块你不能翻过的瓷砖（一堵墙）。

如果你不明白我的意思，去玩游戏，你会明白的。

我设法编写了一个蛮力算法，它可以只用第一种瓷砖来解决难题（这基本上是骑士巡回赛问题的变体）。然而，这不是最佳的，只适用于只能运行一次的拼图。我完全不知道如何处理额外的瓷砖。

给定一个起点和一个瓦片图，有没有办法或算法来找到解决关卡的路径（如果可以解决的话）？我不在乎效率，这只是我想到的一个问题。我很好奇你必须如何去解决它。

我不是在寻找代码，只是在寻找指导方针，或者如果可能的话，是对该过程的纯文本解释。但是，如果您确实有伪代码，请分享！:)

（另外，我不完全确定这是否与寻路有关，但这是我最好的猜测。）

我使用Backtracking方法在 C++ 中编写了Knight's tour算法。但是对于 n > 7（大于 7 x 7 棋盘），它似乎太慢或陷入无限循环。

问题是：这个算法的时间复杂度是多少，我该如何优化它？！

骑士之旅问题可以表述如下：

给定一个有 n × n 个方格的棋盘，为骑士找到一条恰好访问每个方格一次的路径。

这是我的代码：

上面示例 (n = 7) 的输出如下所示：