八數碼寬度優先極簡版

2020-10-25 12:00:36
這個三數碼,八數碼十六數碼都能查。
import numpy as np
import copy
from datetime import datetime
#定位元素0的位置
def local(S0):
    a = np.array(S0)
    i,j = np.where(a == 0)
    return i[0],j[0]
def right_(S0):
    i,j =  local(S0)
    arr = copy.deepcopy(S0)
    if j in (0,len(S0)-2):
        arr[i][j], arr[i][j+1] = arr[i][j+1],arr[i][j]
        return arr
def left_(S0):
    i,j =  local(S0)
    arr = copy.deepcopy(S0)
    if j in (1,len(S0)-1):
        arr[i][j],arr[i][j-1] = arr[i][j-1],arr[i][j]
    return arr
def up_(S0):
    i,j =  local(S0)
    arr = copy.deepcopy(S0)
    if i in (1,len(S0)-1):
        arr[i][j],arr[i-1][j] = arr[i-1][j],arr[i][j]       
        return arr
def down_(S0):
    i,j =  local(S0)
    arr = copy.deepcopy(S0)
    if i in (0,len(S0)-2):
        arr[i][j],arr[i+1][j] = arr[i+1][j],arr[i][j]
        return arr
# S1 = [[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]]
# Sg = [[4,1,2,3],[0,5,6,7],[8,9,10,11],[12,13,14,15]]

S1 = [[0,1],[2,3]]
Sg = [[3,1],[2,0]]

# S1 = [[0,1,3],[4,2,5],[7,8,6]]
# Sg = [[4,1,3],[7,0,5],[8,2,6]]
open_ = [S1]
close = []
start = datetime.now()
while len(open_) > 0:
    n = open_.pop(0)
    close.append(n)
    if n == Sg:
        print( n,'true','搜尋完畢!')
        break
    else:
        local(n)
        Up = up_(n)
        if Up not in open_ and Up not in close and Up is not None:
            open_.append(Up)
            #print("上移 : ",Up)
        Down = down_(n)
        if Down not in open_ and Down not in close and Down is not None:
            open_.append(Down)
            #print("下移 : ",Down)
        Left = left_(n)
        if Left not in open_ and Left not in close and Left is not None:
            open_.append(Left)
            #print("左移 : ",Left)
        Right = right_(n)
        if Right not in open_ and Right not in close and Right is not None:
            open_.append(Right)
            #print("右移 : ",Right)
        open_ = list(filter(None, open_))
        print(n)
end = datetime.now()
print('共耗時:', end - start)