Я написал набор функций, чтобы попытаться решить N-головоломку / 8-головоломку.
Я вполне доволен своей способностью манипулировать головоломкой, но пытаюсь найти итерацию и найти лучший путь.Мои навыки тоже не в ООП, и поэтому функции просты.
Идея, очевидно, состоит в том, чтобы уменьшить расстояние и разместить все фрагменты в нужных местах.
Я много читализ других вопросов, касающихся этой темы, но они часто более продвинуты и сфокусированы на ООП.
Когда я пытаюсь повторить, нет хороших ходов.Я не уверен, как выполнить алгоритм A *.
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'