java - 拼图解题方法

Question

好的，所以我正在编写一个 3 x 3 的拼图锯拼图游戏，但我被困在解决方法上。

public Piece[][] solve(int r, int c) {
    if (isSolved())
        return board;
    board[r][c] = null;
    for (Piece p : pieces) {
        if (tryInsert(p, r, c)) {
            pieces.remove(p);
            break;
        }
    }
    if (getPieceAt(r, c) != null)
        return solve(nextLoc(r, c).x, nextLoc(r, c).y);
    else {
        pieces.add(getPieceAt(prevLoc(r, c).x, prevLoc(r, c).y));
        return solve(prevLoc(r, c).x, prevLoc(r, c).y);
    }
}

我知道我没有提供太多关于这个谜题的信息，但无论具体情况如何，我的算法都应该有效。我已经测试了所有的辅助方法，pieces 是所有未使用的 Pieces 的列表，tryInsert 尝试以所有可能的方向插入 piece，如果可以插入 piece，它就会插入。不幸的是，当我测试它时，出现 StackOverflow 错误。

Answer 1

您的 DFS 样式解决方案算法永远不会将 Piece 对象重新添加到 pieces 变量。这不合理，很容易导致无限递归。

例如，假设您有一个简单的 2 block 拼图，一个 2x1 网格，其中唯一有效的 block 排列是 [2, 1]。这就是您的算法所做的:

1) 将棋子1放入槽1
2)它适合!移除这 block ，现在 block = {2}。解决 nextLoc()
3) 现在尝试将第 2 block 放入插槽 2 中……不起作用
4) 解决 prevLoc()
5) 将第2 block 放入槽1
6) 很合适!删除这 block ， block 现在是空的。解决 nextLoc()
7) 没有棋子可以尝试，所以我们失败了。解决 prevLoc()
8) 没有棋子可以尝试，所以我们失败了。解决 prevLoc()
9) 没有棋子可以尝试，所以我们失败了。解决 prevLoc()
无限重复……

不过，正如评论者所提到的，这可能只是问题的一部分。您的帖子中缺少很多关键代码，它们也可能存在错误。