python广度搜索解决八数码难题

—— 八数码难题 ——

1.题目描述

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始状态转变成目标状态的移动棋子步数最少的移动步骤。

代码

使用算法：广度搜索算法

python

import numpy as np

class State:
 def __init__(self, state, directionFlag=None, parent=None):
 self.state = state
 self.direction = ['up', 'down', 'right', 'left']
 if directionFlag:
  self.direction.remove(directionFlag)
 self.parent = parent
 self.symbol = ' '

 def getDirection(self):
 return self.direction

 def showInfo(self):
 for i in range(3):
  for j in range(3):
  print(self.state[i, j], end=' ')
  print("\n")
 print('->\n')
 return

 def getEmptyPos(self):
 postion = np.where(self.state == self.symbol)
 return postion

 def generateSubStates(self):
 if not self.direction:
  return []
 subStates = []
 boarder = len(self.state) - 1
 row, col = self.getEmptyPos()
 if 'left' in self.direction and col > 0:
  s = self.state.copy()
  temp = s.copy()
  s[row, col] = s[row, col-1]
  s[row, col-1] = temp[row, col]
  news = State(s, directionFlag='right', parent=self)
  subStates.append(news)
 if 'up' in self.direction and row > 0:
  s = self.state.copy()
  temp = s.copy()
  s[row, col] = s[row-1, col]
  s[row-1, col] = temp[row, col]
  news = State(s, directionFlag='down', parent=self)
  subStates.append(news)
 if 'down' in self.direction and row < boarder:
  s = self.state.copy()
  temp = s.copy()
  s[row, col] = s[row+1, col]
  s[row+1, col] = temp[row, col]
  news = State(s, directionFlag='up', parent=self)
  subStates.append(news)
 if self.direction.count('right') and col < boarder:
  s = self.state.copy()
  temp = s.copy()
  s[row, col] = s[row, col+1]
  s[row, col+1] = temp[row, col]
  news = State(s, directionFlag='left', parent=self)
  subStates.append(news)
 return subStates

 def solve(self):
 openTable = []
 closeTable = []
 openTable.append(self)
 steps = 1
 while len(openTable) > 0:
  n = openTable.pop(0)
  closeTable.append(n)
  subStates = n.generateSubStates()
  path = []
  for s in subStates:
  if (s.state == s.answer).all():
   while s.parent and s.parent != originState:
   path.append(s.parent)
   s = s.parent
   path.reverse()
   return path, steps+1
  openTable.extend(subStates)
  steps += 1
 else:
  return None, None

if __name__ == '__main__':
 symbolOfEmpty = ' '
 State.symbol = symbolOfEmpty
 originState = State(np.array([[2, 8, 3], [1, 6 , 4], [7, symbolOfEmpty, 5]]))
 State.answer = np.array([[1, 2, 3], [8, State.symbol, 4], [7, 6, 5]])
 s1 = State(state=originState.state)
 path, steps = s1.solve()
 if path:
 for node in path:
  node.showInfo()
 print(State.answer)
 print("Total steps is %d" % steps)

以上就是python广度搜索解决八数码难题的详细内容，更多关于python广度搜索八数码的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • python广度优先搜索得到两点间最短路径

    python广度优先搜索得到两点间最短路径

    前言 之前一直写不出来,这周周日花了一下午终于弄懂了, 顺便放博客里,方便以后忘记了再看看. 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径. 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索: 比如下图: 从0结点开始搜索的话,一开始是0.将0加入队列中: 然后

  • python 递归深度优先搜索与广度优先搜索算法模拟实现

     一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设

  • Python数据结构与算法之图的广度优先与深度优先搜索算法示例

    本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法.分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从队列弹出一个结点 将该节点的所有相连结点放入队列,并标记已被发现 通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处 """ procedure BFS(G,v) is let Q be a queue Q.enqueue(v) lab

  • python深度优先搜索和广度优先搜索

    1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似. 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到. 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止. 显然,深度优先搜索是一个递归的过程. 2. 广度优先搜索介绍 广度优先搜索算法(Breadt

  • python实现广度优先搜索过程解析

    广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索: 代码 from collections import deque #解决从你的人际关系网中找到芒果销售商的问题 #使用字典表示映射关系 graph = {} graph["you"] = ["alice&quo

  • python广度搜索解决八数码难题

    -- 八数码难题 -- 1.题目描述 八数码问题也称为九宫问题.在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同.棋盘上还有一个空格,与空格相邻的棋子可以移到空格中.要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始状态转变成目标状态的移动棋子步数最少的移动步骤. 代码 使用算法:广度搜索算法 python import numpy as np class State: def __init__(self, state, directionFl

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • Python解决八皇后问题示例

    Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • python 使用递归回溯完美解决八皇后的问题

    八皇后问题描述:在一个8✖️8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法. 规则分析: 任意两个棋子不能在同一行比较好办,设置一个队列,队列里的每个元素代表一行,就能达到要求 任意两个棋子不能在同一列也比较好处理,设置的队列里每个元素的数值代表着每行棋子的列号,比如(0,7,3),表示第一行的棋子放在第一列,第二行的棋子放在第8列,第3行的棋子放在第4列(从0开始计算列号) 任意两个棋子不能在同一斜线上,可以把整个棋盘当作是一个XOY平面,原点在

  • 利用C++求解八数码问题实例代码

    目录 问题描述: 内容提要: 实验步骤: 实验步骤 分析说明(包括核心代码及解释) 总结心得 问题描述: 八数码,在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移.空格右移.空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态.(注:图片给的例子无解.) 内容提要: 分别用广度优先搜索策略.深度优先搜索策略和启发式搜索算法(至少两种)求解八数码问题:分析估价函数对启发式搜索算法的影响:探究讨论各个搜索算法的特点. 实验步骤: 1.随

  • 利用JavaScript在网页实现八数码启发式A*算法动画效果

    利用JavaScript在网页实现八数码启发式A*算法动画效果

    最近人工智能课老师布置了一个八数码实验,网上看到很多八数码的启发式A*算法,但是大多数都是利用C或者C++在控制台实现的,于是我用js在网页中做了一个类似的. 首先八数码就是一个九宫格,其中有一个空格,其他八个对应数字1-8, 移动空格,使得最后状态为有序,如下图 启发式算法是指在求解时,利用启发函数将不符合规则的解节点去掉,从而缩小问题的解空间. A*算法是利用评价函数的启发式算法,在本例中,利用当前节点状态与最终节点状态所不同的格子数来评估节点的优劣,将优越节点储存并在之后展开,将劣质节点抛

  • C++基于回溯法解决八皇后问题示例

    C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • Python模块搜索路径代码详解

    简述 由于某些原因,在使用 import 时,Python 找不到相应的模块.这时,解释器就会发牢骚 - ImportError. 那么,Python 如何知道在哪里搜索模块的路径呢? 模块搜索路径 当导入名为 hello 的模块时,解释器首先搜索具有该名称的内置模块.如果没有找到,将在变量 sys.path 给出的目录列表中搜索名为 hello.py 的文件. sys.path 从这些位置初始化: 包含输入脚本的目录(或当前目录,当没有指定文件时) PYTHONPATH(目录名列表,与 she

  • Pycharm如何导入python文件及解决报错问题

    导入py文件 1.进入pycharm之后,点击File,点击点击Open 2.根据存放路劲找到.py文件,点击ok 解决报错问题 我们在导入自己写的.py文件时,可能会出现报错,如下是解决办法 点击File->Settings 2.进入Settings后,找到Build,Execution,Deployment,点击Console->Python Console->勾选Add source roots to PYTHONPYTH,点击OK. 3.接下来,选中你的工程,右键,点击Mark

  • python 非递归解决n皇后问题的方法

    复杂度可能高了点- - 也没太注意 我想了好久 也找了好久 没看到什么能够用python解决n皇后问题而且不调用递归的 因为我不太能理解递归(尤其是到n层时) 智商受限- - import copy def check(A,x,y): B=[] flag=True for i in range(len(A)): for j in range(len(A)): if A[i][j]==1: B.append([i,j]) for m in range(len(B)): p = B[m][0] q

随机推荐