当使用Manhatten距离启发法解决8个谜题时,即使谜题未解决,也没有位置可移动

2024-03-29 09:49:02 发布

您现在位置:Python中文网/ 问答频道 /正文

当用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()


Tags: thetotextinnodenumberifspace
1条回答
网友
1楼 · 发布于 2024-03-29 09:49:02

好的,我已经清理了很多东西。它确实疯狂地试图解决这个难题,但最终以“不可能的行动”而停止。我已经淘汰了一些但不是所有的全球选手。请注意,您并不想每次都创建一个新的标签小部件;只需更新其中的文本属性

这里是第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()

相关问题 更多 >