0

好的，所以我有一个正在编写的 3 x 3 jig saw 益智游戏，我被困在解决方法上。

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 的 List，tryInsert 尝试以所有可能的方向插入该作品，如果可以插入该作品，它将是。不幸的是，当我测试它时，我得到了 StackOverflow 错误。

4

3 回答 3

3

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

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

1) 将第 1 件放入插槽 1
2) 它适合！删除这块，现在块 = {2}。解决 nextLoc()
3) 现在尝试将第 2 块放入插槽 2... 不起作用
4) 解决 prevLoc()
5) 将第 2 块放入插槽 1
6) 它适合！删除这块，现在是空的。在 nextLoc() 上求解
7) 没有可尝试的部分，所以我们失败了。解决 prevLoc()
8) 没有可尝试的部分，所以我们失败了。解决 prevLoc()
9) 没有可尝试的部分，所以我们失败了。解决 prevLoc()
无限重复...

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

于 2013-05-07T21:01:02.837 回答
2

我认为您需要以不同的方式构造递归。我也不确定从列表的不同位置添加和删除部分是否安全；尽管我宁愿避免在递归中分配，但创建一个列表副本可能是最安全的，或者到目前为止扫描电路板以获取同一块的实例以避免重复使用。

public Piece[][] solve(int r, int c, List<Piece> piecesLeft) {
    // Note that this check is equivalent to
    // 'have r and c gone past the last square on the board?'
    // or 'are there no pieces left?'
    if (isSolved())
        return board;

    // Try each remaining piece in this square
    for (Piece p : piecesLeft) {
        // in each rotation
        for(int orientation = 0; orientation < 4; ++orientation) {
            if (tryInsert(p, r, c, orientation)) {
                // It fits: recurse to try the next square
                // Create the new list of pieces left
                List<Piece> piecesLeft2 = new ArrayList<Piece>(piecesLeft);
                piecesLeft2.remove(p);
                // (can stop here and return success if piecesLeft2 is empty)
                // Find the next point
                Point next = nextLoc(r, c);
                // (could also stop here if this is past end of board)

                // Recurse to try next square
                Piece[][] solution = solve(next.x, next.y, piecesLeft2);
                if (solution != null) {
                    // This sequence worked - success!
                    return solution;
                }
            }
        }
    }

    // no solution with this piece
    return null;
}
于 2013-05-07T22:49:35.067 回答
1

StackOverflowError使用递归函数意味着您要么缺少有效的递归停止条件，要么您试图解决太大的问题，应该尝试使用迭代算法。包含 9 块的拼图不是太大的问题，所以第一件事必须是这样。

结束递归的条件是板子完成。您只是试图在for循环中插入一个片段，所以问题可能是该tryInsert()方法没有插入该片段或者它没有被调用。由于您确定此方法可以正常工作，我建议您break;从

if (p.equals(prev[r][c])) 
{
    System.out.println("Hello");
    break;
}

因为它是唯一可能阻止该作品被插入的东西。我仍然不确定我是否理解这个prev角色。

于 2013-05-07T20:43:31.167 回答