欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

八数码宽度优先极简版

程序员文章站 2022-06-22 09:25:38
这个三数码,八数码十六数码都能查。import numpy as npimport copyfrom 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,le...
这个三数码,八数码十六数码都能查。
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)

本文地址:https://blog.csdn.net/qq_46295527/article/details/109256571