问题标签 [sliding-tile-puzzle]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
2289 浏览

algorithm - 一个很好的谜题 15 随机化器

我实施了一个谜题 15,供人们在线竞争。我当前的随机发生器通过从良好的配置开始并移动瓷砖 100 次移动(任意数)来工作

一切都很好,但是,偶尔洗牌太容易了,只需要几个动作就可以解决难题,因此对于一些人以更高的速度获得更好的分数来说,这个游戏真的很不公平。

什么是随机化初始配置的好方法,所以它不是“太容易”?

0 投票
0 回答
405 浏览

c++ - 优化存储在树结构中的 8 个谜题解决方案

我有一个广度优先搜索来找到一个 8 谜题的最佳解决方案。为了确保我不会在同一个谜题移动中执行相同的函数调用,我创建了一个树结构。它不存储拼图,只是在树中为拼图中的 9 个插槽的 9 个值创建一条路径。这是代码:

我已经在广度和深度有限的搜索中使用了它,使用递归来解决。使用这种结构来存储这些算法的所有可能解决方案需要很长时间。我相信这与分配需要时间有关。是这个原因吗?我正在考虑尝试创建一块内存,然后为节点分配该内存地址,而不是让程序来做。那将是最好的解决方案,我将如何做到这一点?(由于我已经在多次搜索中使用了它并且它们都需要很长时间才能执行,所以我没有包含该代码。)

0 投票
0 回答
105 浏览

python - 最佳优先搜索 8 平方求解器仅适用于简单案例

在我的 AI 课上,我们被分配为8 个正方形拼图编写求解器。我的程序适用于实现解决方案(最多 9 个)的情况,但远不止这些会导致无限递归。我正在存储以前的状态以防止重复相同的 2 个状态,所以我不确定出了什么问题。你们中的一个可以帮助我吗?谢谢。

已解决:代码没有问题;Python 的最大调用堆栈大小太小了。我让它迭代,它工作正常。核心问题是该程序具有指数时间复杂度,并且使其迭代(使用“while True:”)可以解决该问题。

0 投票
1 回答
78 浏览

java - 未添加到 HashMap 的对象

我正在创建一个益智游戏,现在将 8 块随机排列在 3x3 网格中,但并非所有图像都添加到 HashMap。有人知道为什么吗?

这是我用来排列拼图的代码:

这是加载时控制台打印的内容:

由于列出了 8 个点,我不明白为什么puzzle.size()不返回 8,因为 8 个点被添加到puzzle一个随机的 BufferedImage 中,然后被删除,所以我不会两次选择相同的图像。

编辑:我已经解决了这个问题。我的资产加载不正确。很抱歉浪费您的时间。

0 投票
1 回答
45 浏览

arrays - 如何从用户那里获取输入并将它们放入矩阵中?

我知道这可能是非常基本的,但我已经尝试了几个小时,仍然无法自己解决这个问题。所以现在我正在为我的 AI 课做 8 个益智游戏。我需要用户输入一系列数字,比如:“032 145 678”,我只需将其存储到一个 3x3 矩阵中,其中 0 基本上代表一个空块。所以它应该接受用户输入并将其存储为 {{032},{145},{678}},一个 3x3 矩阵。

编辑:

0 投票
1 回答
1326 浏览

java - 距离出租车几何

所以我有一个数组的初始状态,它是一个 8puzzle 和一个目标状态

我试图弄清楚初始状态和目标状态之间的距离是多少而不是对角线。谁能帮我吗?(注意:我不介意把这个数组变成一个二维数组,如果这样可以让事情变得更简单,我只想知道一切的距离是多少)。

我在网上看到的每一个地方都期望goalPuzzle 状态只是按升序排列。我的问题不是这种情况。

0 投票
1 回答
140 浏览

java - 尝试使用启发式进行 A* 搜索,但未记录状态

所以我正在开发这个 3x3 游戏,你会得到一个当前状态,例如:

1 5 6

3 7 乙

2 8 4

并且您希望达到以下目标状态:

乙 1 2

3 4 5

6 7 8

因此,我在下面发布的代码中编写了所有其他方法。我现在遇到的问题是我实际的 A* 搜索。我想使用两种启发式方法,一种检查有多少块在错误的位置(例如,启发式函数将显示当前状态有 H=8 块在错误的位置),另一种启发式方法将计算多远总和是(所以对于我目前的状态,第一块是 1 移动,第二块是 3 移动,等等。所有这些的总和将是我的 H 值)。所以我把我的记录gameBoard在一个字符串数组中。

所以现在我的实际问题。除了我的 A* 之外的所有东西现在都在工作,如下所示。

首先,我调用setFinalGoalState()which 生成变量finalGoalState,以便我可以将当​​前状态与目标状态进行比较。

然后我制作一个priorityQueue应该是ArrayLists的一个Node,其中每个节点都有一个 G 值(G 是它在树中的距离)、H 值、对父级的引用和当前状态。

所以首先我调用一个初始huesticOneHValue()值来获取我的第一个状态的 H 值。然后我为“h1”运行一个if语句(这只是我的第一个启发式方法,我说过我稍后会添加另一个)。然后它应该创建一个初始节点Root,这将是我在树中的第一个节点,并将其添加到优先级队列中。

然后它应该通过优先级队列。它将当前节点作为 中的第一个元素priorityQueue,然后将其从队列中删除。它将我的实际设置为与当前节点gameBoard相同的状态。gameBoard然后它会创建一个ArrayList可能的移动(这会调用isValidMoves(),它会检查您是否真的可以向上、向下、向左或向右移动,然后将其放入列表中)。然后我创建一个 for 循环来遍历我可能移动的大小,然后通过调用该move()方法进行实际移动(所以第一次调用int i = 0将调用 move “up”,因为你可以在我当前的状态下将 b 向上移动)然后它应该创建一个Node包含gValue我在哪里(它应该等于 1),新的 H 值(在某些情况下这可能保持不变,但它应该努力降低 H 值),它的父级(我认为应该只是currentNode?),然后的状态currentNode(板子的样子)。

然后下一个 for 循环检查它应该将它放在优先级队列中的哪个位置。具有较小g+h值的节点应该排在队列的前面,因为我们想先检查它们是否达到目标状态。所以我设置了一个初始条件,如果队列为空,则将其添加到前面,否则它检查priorityQueueatj是否大于g+h子项,如果是,则将子项添加到j(以及其他所有内容)的索引中我认为应该转移过去吗?)最后,在所有移动完成后,它会检查priorityQueue' 的前端节点的状态是否等于我们的目标状态,如果不是,它会返回到 while 循环的前面并再次运行。

我认为最终我用我的节点搞砸了一些东西。当我运行调试时,我发现每次创建一个子节点时,父节点的状态都会更新为子节点的状态,这不应该发生,因为子节点应该是父节点的某个移动(向上,向下,向左,或对)。我想我搞砸了一些东西,要么是我的节点类,要么是我创建节点并将它们添加到队列中的方式。当我尝试将我的孩子添加到priorityQueueat

我的其余代码如下:

八拼图班

节点类

0 投票
0 回答
877 浏览

java - 8拼图迭代深度搜索实现

我已经为 Java 中的 8 个难题问题实现了深度优先搜索(递归):

我不知道我必须改变什么才能将其转换为迭代加深深度搜索。我知道深度没有限制,因为它在每一轮中都会增加。试过这个:

有谁知道如何将其更改为所需的IDS?先感谢您!

0 投票
1 回答
109 浏览

python-3.x - 寻路:一颗星从 A 到 B 的长度与从 B 到 A 的长度不同

我正在为 8 谜题实现具有曼哈顿距离的 A 星算法。[解决方案是螺旋形式]

在某些情况下,从 A 到 B 的步数与从 B 到 A 的步数不同。

我认为这是因为当它们具有相同的成本时,它不会在打开列表中选择相同的状态,因此不会扩展相同的节点。

两者使用曼哈顿距离具有相同的值。我应该探索所有具有相同价值的路径吗?还是我应该改变启发式以进行某种决胜局?

这是代码的相关部分

0 投票
2 回答
116 浏览

java - 开始 8 个谜题

给定起始节点的任何 x 和 y 坐标,我将如何创建板。例如,如果 x=3 和 y=2,板应该喜欢:

java 或伪代码中的示例将非常有用。