拼图求解方法 [英] Jigsaw Puzzle Solver Method

问题描述

好了，我有一个3×3曲线锯解谜游戏，我写，我被困在了解决的方法。

Ok, so I have a 3 x 3 jig saw puzzle game that I am writing and I am stuck on the solution method.

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

我知道我没有提供很多信息的难题，但我的算法应该考虑的具体情况。我测试过的所有辅助方法，是件全部未使用作品的一个目录，tryInsert试图插入件在所有可能的方向，如果可以插一块，这将是。不幸的是，当我测试它，我得到StackOverflow的错误。

I know I haven't provided much info on the puzzle, but my algorithm should work regardless of the specifics. I've tested all helper methods, pieces is a List of all the unused Pieces, tryInsert attempts to insert the piece in all possible orientations, and if the piece can be inserted, it will be. Unfortunately, when I test it, I get StackOverflow Error.

推荐答案

我想你需要你的递归不同的结构。我也不能确定添加和删除列表中的不同的地方是件安全的;虽然我宁愿避免分配中的递归这可能是最安全的创建列表复印或扫描板 迄今为同一块的实例，以避免重新使用。

I think you need to structure your recursion differently. I'm also not sure adding and removing pieces from different places of the list is safe; much as I'd rather avoid allocation in the recursion it might be safest to create a list copy, or scan the board so far for instances of the same piece to avoid re-use.

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

这篇关于拼图求解方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！