How to solve slide puzzles and 15 puzzles

Overview

I would like to try the slide puzzle / 15 puzzle solution. The language used is python. You can play here (with a link). 10.png The purpose is to arrange the numbers in the order of 1, 2, 3, ... by moving the number cells to the vacant cells.

Completely random

Move 20 times, and if they don't match, move again. Print the current status every 100 sets.

Coordinate system

11.png

Function of class


slide.move(direction)

Move the operating mass in the direction of direction 0: Above 1: Right 2: Below 3: Left


slide.shuffle(num)

Move randomly num times

result

I turned it for about 10 minutes, but there was no match.

10105300times
[2, 7, 4, 1]
[3, 10, 8, 12]
[6, 5, 14, 15]
[0, 11, 9, 13]
10105400times
[0, 9, 2, 3]
[14, 1, 8, 7]
[13, 15, 11, 12]
[5, 10, 6, 4]
10105500times
[9, 10, 5, 6]
[15, 2, 13, 8]
[12, 7, 0, 1]
[4, 3, 11, 14]

The executable program looks like this:

import random
import numpy as np		#Numpy library

class Slide():
    """
0 is the operation mass
The origin is the upper left
Next to x
Vertically y
Tosul
    
    """
    
    def __init__(self):
        self.puzzle = [[1,2,3,4],
                  [5,6,7,8],
                  [9,10,11,12],
                  [13,14,15,0]]
        self.x = 3
        self.y = 3
    
    def shuffle(self,num):
        for i in range(num):
            j=0
            while True:
                j = random.randint(0,3)
                break
            self.move(j)
            
    def move(self,direction):
        """
           0
        3     1
           2
        """
        if direction == 0:
            if self.y != 0:
                if self.fixed[self.y-1][self.x] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y-1][self.x]
                    self.y = self.y - 1
                    self.puzzle[self.y][self.x] = 0
        if direction == 1:
            if self.x != 3:
                if self.fixed[self.y][self.x+1] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x+1]
                    self.x = self.x + 1
                    self.puzzle[self.y][self.x] = 0
        if direction == 2:
            if self.y != 3:
                if self.fixed[self.y+1][self.x] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y+1][self.x]
                    self.y = self.y + 1
                    self.puzzle[self.y][self.x] = 0
        if direction == 3:
            if self.x != 0:
                if self.fixed[self.y][self.x-1] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x-1]
                    self.x = self.x - 1
                    self.puzzle[self.y][self.x] = 0
                
    def check(self):
        for i in range(4):
            for j in range(4):
                if self.puzzle[i][j] != j+1+i*4:
                    return -1
                        
        return 0
    
    
if __name__ == '__main__' :
    hoge = Slide()
    hoge.shuffle(500)
    print(hoge.puzzle)
    
    n=0
    while True:
        hoge.shuffle(20)
        flag = hoge.check()
        if flag == 0:
            break
        n=n+1
        
        if n%100 == 0:
            print(str(n)+"times")
            print(hoge.puzzle[0])
            print(hoge.puzzle[1])
            print(hoge.puzzle[2])
            print(hoge.puzzle[3])
            
    print("find")
    print(str(n) + "times")
    print(hoge.puzzle)

While fixing the matching part ・ Random

Use the method of fixing from the square that can be moved to the correct position. However,

[1, 2, 3, 11]
[5, 6, 7, 8]
[12, 11, 10, 9]
[15, 13, 4, 0]

So, if you fix 1,2,3, you can move 4 to the correct position.

Therefore,

  1. 3 corners (because the lower right corner is empty)
  2. 2 squares between 3 corners (out if not appearing at the same time): top side, left side
  3. 2 lines
  4. 2 rows

Complete in the order of. (Turn at random, fix when established, go to the next) At this stage, there are only 4 squares in the lower left, so there are 6 ways (maybe confirmed), and you can solve this randomly.

4.png

As a result, it's pretty good.

shuffled puzzle
[11, 5, 2, 7]
[1, 6, 12, 14]
[0, 13, 9, 3]
[8, 15, 4, 10]
start analyze
3652times
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 0]

It was completed with 3652 sets (3652 * 20 moves). If it is completely random, it will not be completed even if it exceeds 10105500 sets, so I think it is quite good. I've done it several times and it takes less than a second, but the number of sets is sparse.

(Addition) I changed it because I got a better program in the comments. Thank you very much.

import random


class Slide:

    def __init__(self):
        self.puzzle = [
            [ 1,  2,  3,  4],
            [ 5,  6,  7,  8],
            [ 9, 10, 11, 12],
            [13, 14, 15,  0],
        ]
        self.x = 3
        self.y = 3
        self.fixed = [False] * 16

    def __iter__(self):
        return iter(self.puzzle)

    def shuffle(self, num):
        DIRS = (0, -1), (1, 0), (0, 1), (-1, 0)
        for _ in range(num):
            dx, dy = random.choice(DIRS)
            x = self.x + dx
            y = self.y + dy
            if 0 <= x <= 3 and 0 <= y <= 3 and not self.fixed[y * 4 + x]:
                self.puzzle[self.y][self.x] = self.puzzle[y][x]
                self.x = x
                self.y = y
        self.puzzle[self.y][self.x] = 0

    def fix(self, numbers):
        if all(self.fixed[number - 1] for number in numbers):
            return True
        if any(self.puzzle[(number - 1) // 4][(number - 1) % 4] != number
               for number in numbers):
            return False
        for number in numbers:
            self.fixed[number - 1] = True
        return True


def solve(puzzle):
    CORNER = 1, 4, 13
    UPPERSIDE = 2, 3
    LEFTSIDE = 5, 9
    ROW2 = 6, 7, 8
    COL2 = 6, 10, 14
    RIGHTLOWER = 11, 12, 15

    n = 0
    while not puzzle.fix(CORNER):
        puzzle.shuffle(20)
        n += 1
    while not puzzle.fix(UPPERSIDE) or not puzzle.fix(LEFTSIDE):
        puzzle.shuffle(20)
        n += 1
    while not puzzle.fix(ROW2) or not puzzle.fix(COL2):
        puzzle.shuffle(20)
        n += 1
    while not puzzle.fix(RIGHTLOWER):
        puzzle.shuffle(20)
        n += 1
    return n


def main():
    puzzle = Slide()
    puzzle.shuffle(500)
    print("shuffled puzzle")
    print(*puzzle, sep='\n')
    print("start analyze")
    n = solve(puzzle)
    print(n, "times")
    print(*puzzle, sep='\n')

if __name__ == '__main__':
    main()

Move to the target position by calculation, not randomly

Consider how to create a procedure to move the "number" in any place A to any place B. To move A to the left, move the operation cell (0 cell) to the left of A and move the operation cell to the right.

1.png 2.png

The route to move the operating cell is solved by the A * algorithm so as not to move A or the fixed cell. Finally, I will paste the created A * algorithm.

Astar(goal_x,goal_y,start_x,start_y,obstacle)

If is given, the shortest route is returned. Based on this route, attach the operation cell next to the cell you want to move and move it up, down, left, and right. This function allows you to move A anywhere.

Next, decide from which square you want to confirm. 5.png

  1. 1
  2. 2
  3. 4 and 3: If 3 is fixed, 4 will not fit.
  4. 5
  5. 9 and 13 6.6 (From here on, you can solve it by searching the game tree, I want to implement it later)
  6. 7 and 8
  7. 10 and 14
  8. 11 and 12 and 15: Here, if you move 0 to the lower right corner, there are only three ways:

6.png Therefore, it will be completed if you divide each pattern into cases.

Shows the algorithm for two locations that need to be filled at the same time (3, 4, etc.). 7.png

As an exception, if 3 was moved to the upper right corner when 4 was placed next to 2. 8.png

Considering the replacement procedure, it is as follows. 9.png The procedure is to move 3 farther and then make a vertical row of 4-3.

Now you can solve it completely. The number of steps is about 200 to 50. I used about 80,000 at random while fixing it, so I think it's a considerable improvement.

If you program the above


# -*- coding: utf-8 -*-
"""
Created on Mon Jun 29 13:35:47 2020

@author: kisim
"""

"""
Find a solution to a slide puzzle

Ultimately, I want to apply it to Puzzle & Dragons. And aim for 10 combo
"""
"""
Move while avoiding fixed by Astar algorithm
Case classification is troublesome due to the cause of the error


"""
import random
import numpy as np		#Numpy library
import copy

import Astar as As

class Slide():
    """
0 is the operation mass
The origin is the upper left
Next to x
Vertically y
Tosul
    
    """
    
    def __init__(self):
        self.puzzle = [[1,2,3,4],
                  [5,6,7,8],
                  [9,10,11,12],
                  [13,14,15,0]]
        self.x = 3   #Location of operation mass 0
        self.y = 3
        
        self.fixed = np.zeros((4,4))
        self.route = [[self.x,self.y]]
        
    def route_clear(self):
        self.route = [[self.x,self.y]]
        
    def shuffle(self,num):
        for i in range(num):
            j=0
            while True:
                j = random.randint(0,3)
                break
            self.move(j)
            
    def move(self,direction):
        """
           0
        3     1
           2
           
If you fail to move-1
If it moves, 0
        """
        if direction == 0:
            if self.y != 0:
                if self.fixed[self.y-1][self.x] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y-1][self.x]
                    self.y = self.y - 1
                    self.puzzle[self.y][self.x] = 0
                    self.route.append([self.x,self.y])
                    return 0
                else:
                    return -1
        if direction == 1:
            if self.x != 3:
                if self.fixed[self.y][self.x+1] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x+1]
                    self.x = self.x + 1
                    self.puzzle[self.y][self.x] = 0
                    self.route.append([self.x,self.y])
                    return 0
                else:
                    return -1
        if direction == 2:
            if self.y != 3:
                if self.fixed[self.y+1][self.x] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y+1][self.x]
                    self.y = self.y + 1
                    self.puzzle[self.y][self.x] = 0
                    self.route.append([self.x,self.y])
                    return 0
                else:
                    return -1
        if direction == 3:
            if self.x != 0:
                if self.fixed[self.y][self.x-1] == 0:
                    self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x-1]
                    self.x = self.x - 1
                    self.puzzle[self.y][self.x] = 0
                    self.route.append([self.x,self.y])
                    return 0
                else:
                    return -1
        return -1
  
    
    def move_0(self,x,y):
        """
Operation mass("0"trout)X,Move to y
       
Think about the route first, and then move after you know that you won't get caught in the fix.
This is a kind of maze.
A to solve the maze with another function*Implement the algorithm and use it to solve
           
        """
    
        hoge = As.Astar(x,y,self.x,self.y,self.fixed)
        result = hoge.explore()
        route = []
        if result == 0:
           route = hoge.route
        else:
            return -1
        
       
        for i in range(len(route)-1):
            if route[i][0] <  route[i+1][0]:
                self.move(1)
            elif route[i+1][0] <  route[i][0]:
                self.move(3)
            elif route[i+1][1] <  route[i][1]:
                self.move(0)
            elif route[i+1][1] >  route[i][1]:
                self.move(2)
                
        if self.x !=x or self.y != y:
            return -1
        else:
            return 0

    def move_any(self,position,direction):
        x=position[0]
        y=position[1]
        """
any"number"(x,y)Move in the direction of direction
           0
        3     1
           2
           
If you fail to move-1
If it moves, 0
        """
        if direction == 0:    #Move up Attach the operation cell on top
            self.fixed[y][x] = 1
            hoge = self.move_0(x,y-1)
            self.fixed[y][x] = 0
            if hoge == -1:
                return -1
            else:
                self.move_0(x,y)           
                return 0
                            
        elif direction == 2:  #Move down
            self.fixed[y][x] = 1
            hoge = self.move_0(x,y+1)
            self.fixed[y][x] = 0
            if hoge == -1:
                return -1
            else:
                self.move_0(x,y)           
                return 0
                            
        elif direction == 1:  #Move to the right
            self.fixed[y][x] = 1
            hoge = self.move_0(x+1,y)
            self.fixed[y][x] = 0
            if hoge == -1:
                return -1
            else:
                self.move_0(x,y)           
                return 0
                            
        elif direction == 3:  #Move to the left
            self.fixed[y][x] = 1
            hoge = self.move_0(x-1,y)
            self.fixed[y][x] = 0
            if hoge == -1:
                return -1
            else:
                self.move_0(x,y)           
                return 0    
                                
    def find_position(self,num):
        for i in range(4):
            for j in range(4):
                if self.puzzle[i][j] == num:
                    return (j,i)
                
    def move_x(self,number,position):
        target_x = position[0]
        target_y = position[1]
        """
        def move_any(self,position,direction):
any"number"(x,y)Move in the direction of direction
           0
        3     1
           2
           
If you fail to move-1
If it moves, 0
        """
        position2 = self.find_position(number)
        now_x = position2[0]
        now_y = position2[1]
        """
Find the number route with the Astar algorithm
Follow the route and move_Move with any
However, it will not be established unless the road is wide, so move_any can fail
        ->Astar ,Deal with the order of fixing
        """        
        hoge = As.Astar(target_x,target_y,now_x,now_y,self.fixed)
        result = hoge.explore()
        route = []
        if result == 0:
           route = hoge.route
        else:
            return -1
        
        for i in range(len(route)-1):
            position2 = self.find_position(number)
            now_x = position2[0]
            now_y = position2[1]
            if route[i][0] <  route[i+1][0]:
                result = self.move_any((now_x,now_y),1)
                if result == -1:
                    return -1
                
            elif route[i+1][0] <  route[i][0]:
                result = self.move_any((now_x,now_y),3)
                if result == -1:
                    return -1
                
            elif route[i+1][1] <  route[i][1]:
                result = self.move_any((now_x,now_y),0)
                if result == -1:
                    return -1
                
            elif route[i+1][1] >  route[i][1]:
                result = self.move_any((now_x,now_y),2)
                if result == -1:
                    return -1
              
        position2 = self.find_position(number)
        now_x = position2[0]
        now_y = position2[1]
        if target_x != now_x or target_y != now_y:
            return -1
        else:
            return 0
    def exchange_row(self):
        """
        4 3
        x 0
        y z
Replace with
        """
        self.move(0)
        self.move(3)
        """
        0 4
        x 3
        y z       
        """
        self.move(2)
        self.move(2)
        self.move(1)
        """
        x 4
        y 3
        z 0        
        """
        self.move(0)
        """
        x 4
        y 0
        z 3       
        """
        self.move(3)
        self.move(0)
        self.move(1)
        """
        4 0
        x y
        z 3       
        """
        
    def exchange_line(self):
        """
        13 0 y
        9  x z
        """
        self.move(3)
        self.move(2)
        """
        9 13 y
        0  x z
        """
        self.move(1)
        self.move(1)
        self.move(0)
        """
        9 13 0
        x y z
        """
        self.move(3)
        """
        9 0 13
        x y z
        """
        self.move(2)
        self.move(3)
        self.move(0)
        """
        0 y 13
        9 x z
        """
    
def route_test(slide,route):
    if route == []:
        return -1
    else:
        for i in range(len(route)-1):
            if route[i][0] <  route[i+1][0]:
                slide.move(1)
            elif route[i+1][0] <  route[i][0]:
                slide.move(3)
            elif route[i+1][1] <  route[i][1]:
                slide.move(0)
            elif route[i+1][1] >  route[i][1]:
                slide.move(2)
    
    return slide
        
                        
            
        
if __name__ == '__main__' :
    hoge = Slide()
    hoge.shuffle(600)
    hoge.route_clear()
    print(hoge.puzzle[0])
    print(hoge.puzzle[1])
    print(hoge.puzzle[2])
    print(hoge.puzzle[3])
    
    #For test
    hoge2 = Slide()
    hoge2.puzzle = copy.deepcopy(hoge.puzzle)
    hoge2.x = hoge.x
    hoge2.y = hoge.y
    
    
    #1
    hoge.move_x(1,(0,0))
    hoge.fixed[0][0] =1
    #2
    hoge.move_x(2,(1,0))
    hoge.fixed[0][1] =1
    #3,4
    hoge.move_x(4,(2,0))
    hoge.fixed[0][2] =1
    
    if hoge.x == 3 and hoge.y == 0 and hoge.puzzle[1][3] == 3:
        hoge.move(2)
    if hoge.puzzle[0][3] == 3:
        hoge.fixed[0][2] = 0
        hoge.move_0(3,1)
        hoge.exchange_row()
        print("errored 3-4")
    
    hoge.move_x(3,(2,1))
    hoge.fixed[1][2] = 1
    hoge.move_0(3,0)
    hoge.fixed[1][2] = 0
    hoge.fixed[0][2] = 0
    hoge.move(3)
    hoge.move(2)
    
    hoge.fixed[0][2] = 1
    hoge.fixed[0][3] = 1
    
        
    #5
    hoge.move_x(5,(0,1))
    hoge.fixed[1][0] =1
    #9,13
    hoge.move_x(9,(0,3))
    hoge.fixed[3][0] =1

    if hoge.x == 0 and hoge.y == 2 and hoge.puzzle[2][1] == 13:
        hoge.move(1)
    if hoge.puzzle[2][0] == 13:
        hoge.fixed[3][0] = 0
        hoge.move_0(1,2)
        hoge.exchange_line()
        print("error 9-13")
        hoge.fixed[3][0] = 1

    hoge.move_x(13,(1,3))
    hoge.fixed[3][1] = 1
    hoge.move_0(0,2)
    hoge.fixed[3][1] = 0
    hoge.fixed[3][0] = 0
    hoge.move(2)
    hoge.move(1)
    
    hoge.fixed[2][0] = 1
    hoge.fixed[3][0] = 1
    
    #6
    hoge.move_x(6,(1,1))
    hoge.fixed[1][1] =1
    
    #7,8
    hoge.move_x(8,(2,1))
    hoge.fixed[1][2] =1
    if hoge.x == 3 and hoge.y == 1 and hoge.puzzle[2][3] == 7:
        hoge.move(2)
    if hoge.puzzle[1][3] == 7:
        hoge.fixed[1][2] = 0
        hoge.move_0(3,2)
        hoge.exchange_row()
        print("error 7-8")
    
    hoge.move_x(7,(2,2))
    hoge.fixed[2][2] = 1
    hoge.move_0(3,1)
    hoge.fixed[2][2] = 0
    hoge.fixed[1][2] = 0
    hoge.move(3)
    hoge.move(2)
    
    hoge.fixed[1][3] = 1
    hoge.fixed[1][2] = 1
    
    #Since it is 6 squares, can it be solved by searching for a game tree?
    #10,14
    result = hoge.move_x(10,(1,3))
    print(str(result)+"result")

    hoge.fixed[3][1] =1
    if hoge.x == 1 and hoge.y == 2 and hoge.puzzle[2][2] == 14:
        hoge.move(1)
    if hoge.puzzle[2][1] == 14:
        hoge.fixed[3][1] = 0
        hoge.move_0(2,2)
        hoge.exchange_line()
        print("error10-14")
        hoge.fixed[3][1] = 1
        
    
    hoge.move_x(14,(2,3))
    hoge.fixed[3][2] = 1
    hoge.move_0(1,2)
    hoge.fixed[3][2] = 0
    hoge.fixed[3][1] = 0
    hoge.move(2)
    hoge.move(1)
    
    hoge.fixed[2][1] = 1
    hoge.fixed[3][1] = 1

    
    #I thought I could go with this, but it was a little different
    hoge.move_0(3,3)
    
    print("a")
    print(hoge.puzzle[0])
    print(hoge.puzzle[1])
    print(hoge.puzzle[2])
    print(hoge.puzzle[3])
    print(hoge.fixed[0])
    print(hoge.fixed[1])
    print(hoge.fixed[2])
    print(hoge.fixed[3])
    
    if hoge.puzzle[3][2] == 11:
        #Around counterclockwise
        hoge.move(0)
        hoge.move(3)
        hoge.move(2)
        hoge.move(1)
    elif hoge.puzzle[3][2] == 12:
        #Around clockwise
        hoge.move(3)
        hoge.move(0)
        hoge.move(1)
        hoge.move(2)
        
    print(hoge.puzzle[0])
    print(hoge.puzzle[1])
    print(hoge.puzzle[2])
    print(hoge.puzzle[3])

    
    print(len(hoge.route))
    
    hoge2 = route_test(hoge2,hoge.route)
    if hoge2 == -1:
        print("error")
    else:
        print(hoge2.puzzle[0])
        print(hoge2.puzzle[1])
        print(hoge2.puzzle[2])
        print(hoge2.puzzle[3])
    
    
    

    

A * algorithm

Aster.py


import numpy as np		#Numpy library
import random
import copy

class Node():
    def __init__(self,x,y,cost,parent,num):
        self.x = x
        self.y = y
        self.state = 1   # 0:none 1:open 2:closed
        self.score = 0
        self.cost = cost
        self.parent = parent
        self.expect_cost =  0
        self.num = num
        self.calculated = 0

    
    def close(self):
        self.state = 2
        
        
    

class Astar():
    def __init__(self,g_x,g_y,s_x,s_y,obstacle):
        self.width = obstacle.shape[1]
        self.height = obstacle.shape[0]
        self.g_x = g_x
        self.g_y = g_y
        self.s_x = s_x
        self.s_y = s_y
        self.x = s_x
        self.y = s_y
        self.obstacle_list = copy.deepcopy(obstacle)
        self.maked_list = []
        self.num = 0
        
        start = Node(s_x,s_y,0,-1,self.num)
        self.Node_list = [start]
        self.num = self.num + 1
        self.now = start           #Current node
        self.route = []
        self.goal = -1            #gaal node
        self.finished = 0         #Whether you did the goal
        
        if g_x == s_x and g_y == s_y:
            self.finished == 1
            self.goal = start
            self.route = [[s_x,s_y]]
            
        
    def open(self):
        self.now.close()
        #Open around
        """
Cannot open when there is a wall / obstacle-> obstacle_list
Haven't you made it already? -> Maded_list 
        """
        cost = self.now.cost
        parent = self.now.num
        if self.x!=0:
            if self.maked_list.count([self.x-1,self.y]) == 0 and  self.obstacle_list[self.y][self.x-1] == 0 :
                 self.Node_list.append(Node(self.x-1,self.y,cost+1,parent,self.num))
                 self.num = self.num + 1
                 self.maked_list.append([self.x-1,self.y])
        if self.x!=self.width-1:
            if self.maked_list.count([self.x+1,self.y]) == 0 and  self.obstacle_list[self.y][self.x+1] == 0 :
                 self.Node_list.append(Node(self.x+1,self.y,cost+1,parent,self.num))
                 self.num = self.num + 1
                 self.maked_list.append([self.x+1,self.y])
        if self.y!=0:
            if self.maked_list.count([self.x,self.y-1]) == 0 and  self.obstacle_list[self.y-1][self.x] == 0 :
                 self.Node_list.append(Node(self.x,self.y-1,cost+1,parent,self.num))
                 self.num = self.num + 1
                 self.maked_list.append([self.x,self.y-1])
        if self.y!=self.height-1:
            if self.maked_list.count([self.x,self.y+1]) == 0 and  self.obstacle_list[self.y+1][self.x] == 0 :
                 self.Node_list.append(Node(self.x,self.y+1,cost+1,parent,self.num))
                 self.num = self.num + 1
                 self.maked_list.append([self.x,self.y+1])
        
        """
        #debug
        print("test")
        for i in self.Node_list:
            print(i.state)
        """ 
            
        #Calculate what is open
        for i in self.Node_list:
            if i.state == 1 and i.calculated == 0:
                i.calculated = 1
                i.expect_cost = abs(i.x - self.g_x)+abs(i.y-self.g_y)
                i.score = i.cost + i.expect_cost
            
        #List the ones that are open and have the lowest score
        min_cost  = 100
        min_cost_list = []
        for i in self.Node_list:
            if i.state == 1:
                if i.cost < min_cost:
                    min_cost = i.cost
                    min_cost_list = [i]
                elif i.cost == min_cost:
                    min_cost_list.append(i)
        
        if min_cost_list != []:
            self.now = min_cost_list[random.randint(0,len(min_cost_list)-1)]
            self.x = self.now.x
            self.y = self.now.y
        else:
            print("none min")
            return -1
                
        if self.now.x == self.g_x and self.now.y == self.g_y:
            return 1
        else:
            return 0
        
        
    
    def explore(self):
        """
        0 :goal
        -1:goal can't
        """
        if self.finished == 1:
            return 0
        else:
            while True:
                hoge = self.open()
                if hoge == 1:
                    #print("goal!")
                    self.goal = self.now
                    self.finished = 1
                    self.Route()
                    return 0
                elif hoge == -1:
                    return -1
                
    
    def Route(self):
        if self.finished == 1:
            while True:
                self.route.append((self.now.x,self.now.y))
                if self.now.parent == -1:
                    break
                else:
                    self.now = self.Node_list[self.now.parent]
            
            self.route.reverse()
            #print(self.route)
            
    def Express(self):
        if self.finished == 1:
            if self.route ==[]:
                print("not goaled")
            else:
                graph    =  self.obstacle_list
                for i in self.route:
                    graph[i[1]][i[0]] = 2
                    
                print(graph)
                
            
        
        
if __name__ == '__main__' :
    width = 5
    height = 5
    obstacle    =np.zeros((height,width))
    """
    obstacle[2][1] = 1
    obstacle[2][2] = 1
    obstacle[1][2] = 1
    obstacle[3][2] = 1
    """
    obstacle[1][0] = 1
    print(obstacle)
    g_x = 0
    g_y = 2
    s_x = 0
    s_y = 0
    
    hoge = Astar(g_x,g_y,s_x,s_y,obstacle)  
    result = hoge.explore()
    if result == 0:
        hoge.Express()
    

Recommended Posts

How to solve slide puzzles and 15 puzzles
How to install and use Tesseract-OCR
How to solve simultaneous linear equations
How to install and configure blackbird
How to use .bash_profile and .bashrc
How to install CUDA and nvidia-driver
How to package and distribute Python scripts
How to split and save a DataFrame
How to install and use pandas_datareader [Python]
How to solve the bin packing problem
python: How to use locals () and globals ()
[Python] How to calculate MAE and RMSE
How to use Python zip and enumerate
How to use is and == in Python
How to use pandas Timestamp and date_range
How to install fabric and basic usage
How to write pydoc and multi-line comments
How to use lists, tuples, dictionaries, and sets
Conformity and recall-Understanding how to evaluate classification performance ①-
Introducing Sinatra-style frameworks and how to use them
How to generate permutations in Python and C ++
How to create explanatory variables and objective functions
How to switch between Linux and Mac shells
Data cleaning How to handle missing and outliers
How to write async and await in Vue.js
How to install Cascade detector and how to use it
How to plot autocorrelation and partial autocorrelation in python
How to use xml.etree.ElementTree
How to use Python-shell
How to use tf.data
How to use virtualenv
[Python] [Django] How to use ChoiceField and how to add options
Scraping 2 How to scrape
How to use Seaboan
How to use image-match
How to use shogun
How to install Python
How to use Pandas 2
How to read PyPI
How to install pip
Beginners! Basic Linux commands and how to use them!
How to define Decorator and Decomaker in one function
How to use numpy.vectorize
How to install archlinux
How to use pytest_report_header
How to solve the recursive function that solved abc115-D
How to restart gunicorn
How to install Git GUI and Gitk on CentOS
How to install python
How to virtual host
How to debug selenium
How to use partial
How to use Bio.Phylo
How to read JSON
How to share folders with Docker and Windows with tensorflow
How to use SymPy
How to use x-means
How to use WikiExtractor.py
How to update Spyder
How to use IPython
How to install BayesOpt