问Python: N难题(8个难题)解算器Heruistic:如何迭代？

EN

from math import sqrt, fabs
import copy as cp

# Trial puzzle
puzzle1 = [
    [3,5,4],
    [2,1,0],
    [6,7,8]]

# This function is used minimise typing later
def starpiece(piece):
    '''Checks the input of a *arg and returns either tuple'''
    if piece == ():
        return 0
    elif isinstance(piece[0], (str, int)) == True:
        return piece[0]
    elif isinstance(piece[0], (tuple, list)) and len(piece[0]) == 2:
        return piece[0]

# This function creates the goal puzzle layout
def goal(puzzle):
    '''Input a nested list and output an goal list'''
    n = len(puzzle) * len(puzzle)
    goal = [x for x in range(1,n)]
    goal.append(0)
    nested_goal = [goal[i:i+len(puzzle)] for i in range(0, len(goal), len(puzzle))]
    return nested_goal

# This fuction gives either the coordinates (as a tuple) of a piece in the puzzle
# or the piece in the puzzle at give coordinates 
def search(puzzle, *piece):
    '''Input a puzzle and piece value and output a tuple of coordinates. 
    If no piece is selected 0 is chosen by default. If coordinates are 
    entered the piece value at those coordinates are outputed'''
    piece = starpiece(piece)
    if isinstance(piece, (tuple, list)) == True:
        return puzzle[piece[0]][piece[1]]
    for slice1, sublist in enumerate(puzzle):
        for slice2, item in enumerate(sublist):
            if puzzle[slice1][slice2] == piece:
                x, y = slice1, slice2
    return (x, y)  

# This function gives the neighbours of a piece at a given position as a list of coordinates
def neighbours(puzzle, *piece):
    '''Input a position (as a tuple) or piece and output a list 
    of adjacent neighbours. Default are the neighbours to 0'''
    length = len(puzzle) - 1
    return_list = []
    piece = starpiece(piece)
    if isinstance(piece, tuple) != True:
        piece = search(puzzle, piece)
    if (piece[0] - 1) >= 0:
        x_minus = (piece[0] - 1)
        return_list.append((x_minus, piece[1]))
    if (piece[0] + 1) <= length:
        x_plus = (piece[0] + 1)
        return_list.append((x_plus, piece[1]))
    if (piece[1] - 1) >= 0:
        y_minus = (piece[1] - 1)
        return_list.append((piece[0], y_minus))
    if (piece[1] + 1) <= length:
        y_plus = (piece[1] + 1)
        return_list.append((piece[0], y_plus))
    return return_list

# This function swaps piece values of adjacent cells 
def swap(puzzle, cell1, *cell2):
    '''Moves two cells, if adjacent a swap occurs. Default value for cell2 is 0.
    Input either a cell value or cell cooridinates''' 
    cell2 = starpiece(cell2)
    if isinstance(cell1, (str, int)) == True:
        cell1 = search(puzzle, cell1)    
    if isinstance(cell2, (str, int)) == True:
        cell2 = search(puzzle, cell2) 
    puzzleSwap = cp.deepcopy(puzzle)
    if cell1 == cell2:
        print('Warning: no swap occured as both cell values were {}'.format(search(puzzle,cell1)))
        return puzzleSwap
    elif cell1 in neighbours(puzzleSwap, cell2):
        puzzleSwap[cell1[0]][cell1[1]], puzzleSwap[cell2[0]][cell2[1]] = puzzleSwap[cell2[0]][cell2[1]], puzzleSwap[cell1[0]][cell1[1]]
        return puzzleSwap
    else:
        print('''Warning: no swap occured as cells aren't adjacent''')
        return puzzleSwap

# This function gives true if a piece is in it's correct position
def inplace(puzzle, p):
    '''Ouputs bool on whether a piece is in it's correct position'''
    if search(puzzle, p) == search(goal(puzzle), p):
        return True
    else:
        return False

# These functions give heruistic measurements 
def heruistic(puzzle):
    '''All returns heruistic (misplaced, total distance) as a tuple. Other 
    choices are: heruistic misplaced, heruistic distance or heruistic list'''
    heruistic_misplaced = 0
    heruistic_distance = 0
    heruistic_distance_total = 0
    heruistic_list = []
    for sublist in puzzle:
        for item in sublist:
            if inplace(puzzle, item) == False:
                heruistic_misplaced += 1          
    for sublist in puzzle:
        for item in sublist:
            a = search(puzzle, item)
            b = search(goal(puzzle), item)
            heruistic_distance = int(fabs(a[0] - b[0]) + fabs(a[1] - b[1]))
            heruistic_distance_total += heruistic_distance
            heruistic_list.append(heruistic_distance)

    return (heruistic_misplaced, heruistic_distance_total, heruistic_list)

def hm(puzzle):
    '''Outputs heruistic misplaced'''
    return heruistic(puzzle)[0]

def hd(puzzle):
    '''Outputs total heruistic distance'''
    return heruistic(puzzle)[1]

def hl(puzzle):
    '''Outputs heruistic list'''
    return heruistic(puzzle)[2]

def hp(puzzle, p):
    '''Outputs heruistic distance at a given location'''
    x, y = search(puzzle, p)[0], search(puzzle, p)[1]
    return heruistic(puzzle)[2][(x * len(puzzle)) + y]

# This is supposted to iterate along a route according to heruistics but doesn't work
def iterMove(puzzle):
    state = cp.deepcopy(puzzle)
    while state != goal(puzzle):
        state_hd = hd(state)
        state_hm = hm(state)
        moves = neighbours(state)
        ok_moves = []
        good_moves = []
        for move in moves:
            maybe_state = swap(state, move)
            if hd(maybe_state) < state_hd and hm(maybe_state) < state_hm:
                good_moves.append(move)
            elif hd(maybe_state) < state_hd:
                ok_moves.append(move)
            elif hm(maybe_state) < state_hm:
                ok_moves.append(move)
        if good_moves != []:
            print(state)
            state = swap(state, good_moves[0])
        elif ok_moves != []:
            print(state)
            state = swap(state, ok_moves[0])


>> iterMove(puzzle1)
'no good moves'