深度优先用栈解决15数码问题_Python实现

好的，以下是深度优先算法用栈解决15数码问题的Python实现：

# 定义状态类
class State:
    def __init__(self, board, moves, previous):
        self.board = board
        self.moves = moves
        self.previous = previous

    # 比较两个状态是否相同
    def __eq__(self, other):
        return self.board == other.board

# 定义15数码问题类
class FifteenPuzzle:
    def __init__(self, initial_board):
        self.initial_board = initial_board

    # 定义求解方法
    def solve(self):
        start_state = State(self.initial_board, 0, None)
        stack = [start_state]
        explored = set()
        while stack:
            current_state = stack.pop()
            if current_state.board == [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]:
                return current_state.moves
            explored.add(str(current_state.board))
            for move, new_board in self.get_successors(current_state.board):
                if str(new_board) not in explored:
                    new_state = State(new_board, current_state.moves + 1, current_state)
                    stack.append(new_state)

    # 定义获取后继状态的方法
    def get_successors(self, board):
        successors = []
        i, j = self.get_blank_position(board)
        if i > 0:
            new_board = self.get_board_copy(board)
            new_board[i][j], new_board[i-1][j] = new_board[i-1][j], new_board[i][j]
            successors.append(('up', new_board))
        if i < 3:
            new_board = self.get_board_copy(board)
            new_board[i][j], new_board[i+1][j] = new_board[i+1][j], new_board[i][j]
            successors.append(('down', new_board))
        if j > 0:
            new_board = self.get_board_copy(board)
            new_board[i][j], new_board[i][j-1] = new_board[i][j-1], new_board[i][j]
            successors.append(('left', new_board))
        if j < 3:
            new_board = self.get_board_copy(board)
            new_board[i][j], new_board[i][j+1] = new_board[i][j+1], new_board[i][j]
            successors.append(('right', new_board))
        return successors

    # 定义获取空白格位置的方法
    def get_blank_position(self, board):
        for i in range(4):
            for j in range(4):
                if board[i][j] == 0:
                    return i, j

    # 定义获取棋盘复制品的方法
    def get_board_copy(self, board):
        return [row[:] for row in board]

# 测试
initial_board = [[5, 1, 2, 4], [9, 6, 3, 8], [13, 10, 11, 12], [0, 14, 15, 7]]
puzzle = FifteenPuzzle(initial_board)
moves = puzzle.solve()
print(moves)

以上代码实现了深度优先算法用栈解决15数码问题的功能，可以通过测试数据进行验证。