八数码难题python

以下是使用Python解决八数码难题的示例代码：

from queue import Queue

# 定义目标状态
target = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# 定义移动方向
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

# 判断状态是否合法
def isValid(state):
    count = 0
    for i in range(8):
        for j in range(i + 1, 9):
            if state[i] != 0 and state[j] != 0 and state[i] > state[j]:
                count += 1
    return count % 2 == 0

# 获取空格的位置
def getBlankIndex(state):
    return state.index(0)

# 移动状态
def move(state, direction, blankIndex):
    newState = state[:]
    x = blankIndex // 3
    y = blankIndex % 3
    newX = x + direction[0]
    newY = y + direction[1]
    newBlankIndex = newX * 3 + newY
    newState[blankIndex], newState[newBlankIndex] = newState[newBlankIndex], newState[blankIndex]
    return newState

# 广度优先搜索
def bfs(startState):
    if not isValid(startState):
        return "无解"
    visited = set()
    q = Queue()
    q.put((startState, 0))
    visited.add(tuple(startState))
    while not q.empty():
        state, step = q.get()
        if state == target:
            return step
        blankIndex = getBlankIndex(state)
        x = blankIndex // 3
        y = blankIndex % 3
        for direction in directions:
            newX = x + direction[0]
            newY = y + direction[1]
            if 0 <= newX < 3 and 0 <= newY < 3:
                newState = move(state, direction, blankIndex)
                if tuple(newState) not in visited:
                    q.put((newState, step + 1))
                    visited.add(tuple(newState))
    return "无解"

# 测试
startState = [2, 8, 3, 1, 6, 4, 7, 0, 5]
steps = bfs(startState)
print("需要的最少步数为:", steps)