K-拼图的迭代加深搜索

以下是一个使用迭代加深搜索解决K-拼图问题的示例代码：

# 定义全局变量
goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
max_depth = 10
found_solution = False

# 检查当前状态是否为目标状态
def is_goal_state(state):
    return state == goal_state

# 检查两个状态是否相等
def is_same_state(state1, state2):
    return state1 == state2

# 获取空白格子的位置
def get_blank_position(state):
    for i in range(len(state)):
        for j in range(len(state[i])):
            if state[i][j] == 0:
                return i, j

# 移动拼图块
def move(state, blank, direction):
    i, j = blank
    new_state = [row[:] for row in state]
    if direction == 'up':
        new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
    elif direction == 'down':
        new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
    elif direction == 'left':
        new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
    elif direction == 'right':
        new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
    return new_state

# 执行迭代加深搜索
def iterative_deepening_search(state, depth):
    global found_solution
    if depth == 0:
        if is_goal_state(state):
            found_solution = True
        return
    if found_solution:
        return
    blank = get_blank_position(state)
    i, j = blank
    if i > 0:  # 向上移动
        new_state = move(state, blank, 'up')
        if not is_same_state(state, new_state):
            iterative_deepening_search(new_state, depth - 1)
            if found_solution:
                return
    if i < len(state) - 1:  # 向下移动
        new_state = move(state, blank, 'down')
        if not is_same_state(state, new_state):
            iterative_deepening_search(new_state, depth - 1)
            if found_solution:
                return
    if j > 0:  # 向左移动
        new_state = move(state, blank, 'left')
        if not is_same_state(state, new_state):
            iterative_deepening_search(new_state, depth - 1)
            if found_solution:
                return
    if j < len(state[0]) - 1:  # 向右移动
        new_state = move(state, blank, 'right')
        if not is_same_state(state, new_state):
            iterative_deepening_search(new_state, depth - 1)
            if found_solution:
                return

# 主函数
def main():
    initial_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
  
    for depth in range(max_depth):
        iterative_deepening_search(initial_state, depth)
        if found_solution:
            print("Found solution at depth", depth)
            break
    if not found_solution:
        print("No solution found within max depth limit")

# 调用主函数
if __name__ == "__main__":
    main()

在这个示例代码中，我们定义了全局变量goal_state表示目标状态，max_depth表示搜索的最大深度，以及found_solution表示是否找到解决方案。

我们首先定义了一系列辅助函数，包括is_goal_state用于检查当前状态是否为目标状态，is_same_state用于检查两个状态是否相等，get_blank_position用于获取空白格子的位置，move用于移动拼图块。

然后，我们定义了iterative_deepening_search函数来执行迭代加深搜索。该函数使用递归的方式进行搜索，通过限制搜索的深度来控制算法的执行时间。在每一步中，我们检查当前