java - 拼图解法

好的，所以我有一个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);
    }
}

我知道我没有提供很多关于这个谜题的信息，但是我的算法应该可以工作，不管细节如何我已经测试了所有的helper方法，pieces是所有未使用的pieces的列表，tryinsert尝试在所有可能的方向插入piece，如果可以插入，它将是。不幸的是，当我测试它时，我得到stackoverflow错误。

最佳答案

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

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;
}

关于java - 拼图解法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16428145/