当用Manhatten距离启发式算法求解8个谜题时，我最终会陷入一种没有位置可移动的状态，因为我有一个包含所有以前访问过的节点的列表，并通过在选择之前比较要访问的可能节点来确保没有访问过以前访问的节点。在调试后，我可以确认最初生成的8个谜题在洗牌时是可以解决的，并且在基于最低曼哈顿距离选择下一个节点之前，每个可能的节点的曼哈顿距离都是准确计算的。此外，该问题是由这样一个事实引起的，即从空闲空间的位置访问的唯一可能的节点在已经访问的节点的列表中，这阻止了它们被访问。如何解决这一问题，同时仍然不允许访问以前访问过的节点？
import random
from tkinter import *
all_node_contents = []
def input_validation(coordinates, user_input):
global previous_coordinates #stores the previous co ordinates of the blank space, so we know the co ordinates of where we need to switch the chosen number with each time. Its global so its not disgraded when the function terminates.
global solved_puzzle #checks i the puzzle is finished
if coordinates [1] <0 or coordinates [0] <0 or coordinates [1] >2 or coordinates [0] >2: #checks if any of the passed in coordinates go over a certain range, which tells use if those co oridnate are on the grid.
pass
elif (int(user_input) == int(frame.grid_slaves(coordinates[0], coordinates[1])[0]['text'])): #if the number in one of the enterted co ordinates equals the number entered, switch the possitions of the blank space with the entered number block.
Label (frame, text = frame.grid_slaves(coordinates[0], coordinates[1])[0]['text']
).grid(row= previous_coordinates[0], column= previous_coordinates[1])
Label (frame, text = "").grid(row= coordinates[0], column= coordinates[1])
if puzzle_finished_checker() == True: #checks if the puzzle if solved to print a message
text_display.configure(text= "The puzzle has been solved", fg="red")
previous_coordinates = [coordinates[0], coordinates[1]]
solved_puzzle=True
return
else:
previous_coordinates = [coordinates[0], coordinates[1]] #stores the co cordinates for where the blank space is for the next time.
text_display.configure(text= "Input the number you want to move into the empty space n *make sure the number is next to the empty space*", fg="red")
return True
def possible_paths():
global coordinates_up #stored globally so they can be acsessed throughout each function
global coordinates_left
global coordinates_right
global coordinates_down
#Defines all the possible co ordinates around the blank space, some of these will be invalid unless the previous co ordinate was in the middle.
coordinates_up = [previous_coordinates[0]-1, previous_coordinates[1]]
coordinates_left = [previous_coordinates[0], previous_coordinates[1]-1]
coordinates_right = [previous_coordinates[0], previous_coordinates[1]+1]
coordinates_down = [previous_coordinates[0]+1,previous_coordinates[1]]
def button_click():
global text_display
global previous_coordinates
global solved_puzzle
solved_puzzle = False
possible_paths()
if solved_puzzle == False:
#checks to see if one of the surrounding co ordiantes equals the number entered, if not an error is displayed.
if (input_validation(coordinates_up, number_input.get()) == True):
pass
elif(input_validation(coordinates_left, number_input.get()) == True):
pass
elif(input_validation(coordinates_right, number_input.get()) == True):
pass
elif(input_validation(coordinates_down, number_input.get()) == True):
pass
elif (solved_puzzle == False):
text_display.configure(text="Please input a number that is surrounding the empty space")
else:
pass
#generates and arranges all the GUI elements
puzzle = Tk()
puzzle.title("Eight Puzzle")
frame = Frame(puzzle)
frame.pack()
number_input= Entry(frame, width= 20)
number_input.grid(row = 5, column =7)
text_display = Label(frame, text="Input the number you want to move into the empty space n *make sure the number is next to the empty space*", fg="red")
text_display.grid(row = 3, column = 7)
number = 1
#adds all the numbers in to all the blocks in the grid
for y in range (0,3):
for x in range (0,3):
if number != 10:
if number == 9:
Label (frame, text = " ").grid(column=x, row=y)
else:
Label (frame, text = number).grid(column=x, row=y)
number= number +1
directions=[-1,1]
space_coordinates = [2,2]
#randomly shuffles the puzzle
for _ in range (0,50):
#generates a random index value to select either -1 or 1 to randomly generate either number, as this will be added to either the x y of the previous co ordinates to generate a random co ordinate to switc
ran_direction = random.randint(0,1)
ran_direction = directions[ran_direction]
ran_x_or_y = random.randint(0,1) #randomly generates an index value to select either x or y for the ran direction to be added to.
num_test = space_coordinates[ran_x_or_y] + ran_direction #create a test varible just to check if the edited x or y co irdinate either goes below 0 or above 2, so its not invalid.
if (num_test>=0 and num_test<=2):
previous_coordinates = []
previous_coordinates.append(space_coordinates[0])
previous_coordinates.append(space_coordinates[1]) #store the current co ordiantes in the previous co ordinates varible before the co ordinates are changed, to keep track of the co ordiantes of the empty space.
space_coordinates[ran_x_or_y] = space_coordinates[ran_x_or_y] + ran_direction
Label (frame, text = frame.grid_slaves(space_coordinates[0], space_coordinates[1])[0]['text'] #switch the previous corodiante space with the randomly generate co ordiante space.
).grid(row= previous_coordinates[0], column= previous_coordinates[1])
Label (frame, text = "").grid(row= space_coordinates[0], column= space_coordinates[1])
else:
pass
nodes_coordinates = [1,2,3,4,5,6,7,8, ""]
correct_coordinates = [ [0,0], [1,0], [2,0], [0,1], [1,1], [2,1], [0,2], [1,2], [2,2]]
def puzzle_finished_checker():
global position_count
position_count = 0
for i in range(0,3):
for b in range(0,3): #itterates over all the spaces in the grid
current_node = frame.grid_slaves(i, b)[0]['text']
current_coordinates = [i, b]
if (current_coordinates == correct_coordinates[nodes_coordinates.index(current_node)]): #checks if the co ordiantes we are on equal the co ordiantes in the correct co ordiantes list from the index value of the current value (the value from the current co ordiantes palce we are one) in the nodes co ordiante list.
position_count+=1
else:
pass
if position_count == 9:
return True
else:
return False
#totals the amount of space each number will need to move from where it is to be solved
def manhatten_distance_calc():
manhatten_dist_sum = 0
for y in range(0,3):
for x in range(0,3):
current_node = frame.grid_slaves( y,x)[0]['text']
current_coordinates = [x, y]
desired_coordinate = correct_coordinates[nodes_coordinates.index(current_node)]
manhatten_dist_sum += (abs(desired_coordinate[0] - current_coordinates[0]) + abs(desired_coordinate[1] - current_coordinates[1]))
return manhatten_dist_sum
def puzzle_solve():
global previous_coordinates
global count
global next_node
global all_node_contents
count = 0
def path_checker (coordinates):
global count
global new_space
node_been_used = False
current_visited_node = []
for i in range(0,3):
for b in range(0,3):
current_node = frame.grid_slaves(i, b)[0]['text']
current_visited_node.append(current_node)
if coordinates [0] <0 or coordinates [1] <0 or coordinates [0] >2 or coordinates [1] >2:
return "null"
else:
# here we reverse what we previously did to the grid below, when working out the next grid.
if (count > 0):
Label (frame, text = frame.grid_slaves(previous_coordinates[0], previous_coordinates[1])[0]['text']
).grid(row= new_space[0], column= new_space[1])
Label (frame, text = "").grid(row= previous_coordinates[0], column= previous_coordinates[1])
puzzle.update()
Label (frame, text = frame.grid_slaves(coordinates[0], coordinates[1])[0]['text']
).grid(row= previous_coordinates[0], column= previous_coordinates[1])
Label (frame, text = "").grid(row= coordinates[0], column= coordinates[1])
new_space = [coordinates[0], coordinates[1]]
else:
count+= 1
Label (frame, text = frame.grid_slaves(coordinates[0], coordinates[1])[0]['text']
).grid(row= previous_coordinates[0], column= previous_coordinates[1])
Label (frame, text = "").grid(row= coordinates[0], column= coordinates[1])
new_space = [coordinates[0], coordinates[1]]
current_visited_node = []
for i in range(0,3):
for b in range(0,3):
current_node = frame.grid_slaves(i, b)[0]['text']
current_visited_node.append(current_node)
if current_visited_node in all_node_contents:
node_been_used = True
if node_been_used == True:
return "null"
possible_paths()
path1 = path_checker(coordinates_up)
path2 = path_checker(coordinates_left)
path3 = path_checker(coordinates_right)
path4 = path_checker(coordinates_down)
possible_nodes = [path1, path2, path3, path4]
##RESETS THE GRID
Label (frame, text = frame.grid_slaves(previous_coordinates[0], previous_coordinates[1])[0]['text']
).grid(row= new_space[0], column= new_space[1])
Label (frame, text = "").grid(row= previous_coordinates[0], column= previous_coordinates[1])
node_manhatten_distances =[]
for i in range (len(possible_nodes)):
if possible_nodes[i] == "null":
node_manhatten_distances.append(100)
else:
node_manhatten_distances.append(possible_nodes[i][0])
next_node = possible_nodes[node_manhatten_distances.index(min(node_manhatten_distances))][1]
print(possible_nodes)
Label (frame, text = frame.grid_slaves(next_node[0], next_node[1])[0]['text']
).grid(row= previous_coordinates[0], column= previous_coordinates[1])
Label (frame, text = "").grid(row= next_node[0], column= next_node[1])
previous_coordinates = next_node
visited_nodes = []
for i in range(0,3):
for b in range(0,3):
current_node = frame.grid_slaves(i, b)[0]['text']
visited_nodes.append(current_node)
all_node_contents.append(visited_nodes)
print(all_node_contents)
if puzzle_finished_checker() == True:
text_display.configure(text= "The puzzle has been solved", fg="red")
return True
def puzzle_solve_button():
while puzzle_solve() != True:
if puzzle_solve() == True:
break
button = Button(frame, text="Enter", command = button_click)
button.grid(row = 6, column = 7)
solve = Button(frame, text="Solve", command = puzzle_solve_button)
solve.grid(row = 7, column = 7)
previous_coordinates = []
previous_coordinates.append(space_coordinates[0])
previous_coordinates.append(space_coordinates[1])
puzzle.mainloop()
好的，我已经清理了很多东西。它确实疯狂地试图解决这个谜题，但最终以"；没有可能的移动"；。我已经消除了一些但不是所有的全局变量。请注意，您并不真的希望每次都创建一个新的标签小部件；只需更新现有文本的文本属性。
下面是修订版3，它现在可以正确地检测用户何时解决谜题。
下面是修订版4，它使用了一种更好的方法来编码当前状态。
你的根本问题是你没有倒退。每走一步，你最多有四个可能的动作。你只需要选择一个，但如果这导致了死胡同，你就不会回去尝试其他的。这将需要更多的返工。
import random
from tkinter import *
all_node_contents = []
def input_validation(coordinates, user_input):
global previous_coordinates #stores the previous co ordinates of the blank space, so we know the co ordinates of where we need to switch the chosen number with each time. Its global so its not disgraded when the function terminates.
global solved_puzzle #checks i the puzzle is finished
if coordinates [1] <0 or coordinates [0] <0 or coordinates [1] >2 or coordinates [0] >2: #checks if any of the passed in coordinates go over a certain range, which tells use if those co ordinate are on the grid.
pass
elif (int(user_input) == int(frame.grid_slaves(*coordinates)[0]['text'])): #if the number in one of the entered co ordinates equals the number entered, switch the positions of the blank space with the entered number block.
frame.grid_slaves(*previous_coordinates)[0]['text'] = frame.grid_slaves(*coordinates)[0]['text']
frame.grid_slaves(*coordinates)[0]['text'] = ""
previous_coordinates = coordinates[:]
if puzzle_finished_checker() == True: #checks if the puzzle if solved to print a message
text_display.configure(text= "The puzzle has been solved", fg="red")
solved_puzzle=True
return
else:
text_display.configure(text= "Input the number you want to move into the empty space n *make sure the number is next to the empty space*", fg="red")
return True
def possible_paths(was):
#Defines all the possible co ordinates around the blank space, some of these will be invalid unless the previous co ordinate was in the middle.
return (
[was[0]-1, was[1]] ,
[was[0], was[1]-1],
[was[0], was[1]+1],
[was[0]+1, was[1]]
)
def button_click():
global text_display
global previous_coordinates
global solved_puzzle
if solved_puzzle:
return
paths = possible_paths(previous_coordinates)
#checks to see if one of the surrounding co ordinates equals the number entered, if not an error is displayed.
n = number_input.get()
if not any( input_validation(i,n) for i in paths ):
text_display.configure(text="Please input a number that is surrounding the empty space")
number_input.delete(0)
if puzzle_finished_checker():
text_display.configure(text="Puzzle is solved!")
#generates and arranges all the GUI elements
puzzle = Tk()
puzzle.title("Eight Puzzle")
frame = Frame(puzzle)
frame.pack()
number_input= Entry(frame, width= 20)
number_input.grid(row = 5, column =7)
text_display = Label(frame, text="Input the number you want to move into the empty space n *make sure the number is next to the empty space*", fg="red")
text_display.grid(row = 3, column = 7)
#adds all the numbers in to all the blocks in the grid
for y in range (0,3):
for x in range (0,3):
if x==2 and y==2:
Label (frame, text = " ").grid(column=x, row=y)
else:
Label (frame, text = str(y*3+x+1)).grid(column=x, row=y)
directions=[-1,1]
space_coordinates = [2,2]
#randomly shuffles the puzzle
for _ in range(50):
#generates a random index value to select either -1 or 1 to randomly generate either number, as this will be added to either the x y of the previous co ordinates to generate a random co ordinate to switch
ran_direction = random.randint(0,1)
ran_direction = directions[ran_direction]
ran_x_or_y = random.randint(0,1) #randomly generates an index value to select either x or y for the ran direction to be added to.
num_test = space_coordinates[ran_x_or_y] + ran_direction #create a test variable just to check if the edited x or y coordinate either goes below 0 or above 2, so its not invalid.
if 0 <= num_test <=2:
previous_coordinates = space_coordinates[:]
space_coordinates[ran_x_or_y] = space_coordinates[ran_x_or_y] + ran_direction
frame.grid_slaves(*previous_coordinates)[0]['text'] = frame.grid_slaves(*space_coordinates)[0]['text']
frame.grid_slaves(*space_coordinates)[0]['text'] = ""
def get_state():
vals = ''
for i in range(0,3):
for b in range(0,3): #iterates over all the spaces in the grid
vals += frame.grid_slaves(i, b)[0]['text']
return vals
def puzzle_finished_checker():
return get_state() == "12345678 "
#totals the amount of space each number will need to move from where it is to be solved
nodes_coordinates = "12345678 "
correct_coordinates = [ [0,0], [1,0], [2,0], [0,1], [1,1], [2,1], [0,2], [1,2], [2,2]]
def manhatten_distance_calc():
manhatten_dist_sum = 0
for y in range(0,3):
for x in range(0,3):
current_node = frame.grid_slaves( y,x)[0]['text']
current_coordinates = [x, y]
desired_coordinate = correct_coordinates[nodes_coordinates.index(current_node)]
manhatten_dist_sum += (abs(desired_coordinate[0] - current_coordinates[0]) + abs(desired_coordinate[1] - current_coordinates[1]))
return manhatten_dist_sum
def puzzle_solve():
global previous_coordinates
global count
global next_node
global all_node_contents
count = 0
def path_checker (coordinates):
global count
global new_space
node_been_used = False
if coordinates [0] <0 or coordinates [1] <0 or coordinates [0] >2 or coordinates [1] >2:
return "null"
# here we reverse what we previously did to the grid below, when working out the next grid.
if count:
frame.grid_slaves(*new_space)[0]['text'] = frame.grid_slaves(*previous_coordinates)[0]['text']
frame.grid_slaves(*previous_coordinates)[0]['text'] = ' '
puzzle.update()
else:
count+= 1
frame.grid_slaves(*previous_coordinates)[0]['text'] = frame.grid_slaves(*coordinates)[0]['text']
frame.grid_slaves(*coordinates)[0]['text'] = ' '
new_space = coordinates[:]
if get_state() in all_node_contents:
node_been_used = True
return "null"
return 1, coordinates
possible_nodes = [path_checker(i) for i in possible_paths(previous_coordinates)]
##RESETS THE GRID
frame.grid_slaves(*new_space)[0]['text'] = frame.grid_slaves(*previous_coordinates)[0]['text'];
frame.grid_slaves(*previous_coordinates)[0]['text'] = ' '
node_manhatten_distances = [100 if n == 'null' else n[0] for n in possible_nodes]
next_node = possible_nodes[node_manhatten_distances.index(min(node_manhatten_distances))][1]
if not isinstance(next_node,list):
print("No possible moves???")
print(possible_nodes, node_manhatten_distances)
return True
frame.grid_slaves(*previous_coordinates)[0]['text'] = frame.grid_slaves(*next_node)[0]['text']
frame.grid_slaves(*next_node)[0]['text'] = ' '
previous_coordinates = next_node
all_node_contents.append(get_state())
if puzzle_finished_checker():
text_display.configure(text= "The puzzle has been solved", fg="red")
return True
def puzzle_solve_button():
while not puzzle_solve():
pass
solved_puzzle = False
button = Button(frame, text="Enter", command = button_click)
button.grid(row = 6, column = 7)
solve = Button(frame, text="Solve", command = puzzle_solve_button)
solve.grid(row = 7, column = 7)
previous_coordinates = space_coordinates[:]
puzzle.mainloop()