python迷宫算法

‘壹’ 使用左手法则/右手法则摸墙法（左手或右手在迷宫中始终不离开墙）写一个python程序解迷宫

下面的代码假定你的迷宫数据一定是合法的 （单一的入口和出口，不会打环，不会无解），如果数据不合法，可能导致死循环，数据合法性的检查你自己实现。

另外，我用 东南西北四个方向来代替所谓的上下左右，因为左右概念是相对的。 用python 2。

puzzle_walk 函数返回一个list, 每个元素是每次移动的路径坐标， 其第一个参数为迷宫的list数据， 第二个参数默认为 True 表示左手抹墙， False 则是右手抹墙。

简单说一下算法：首先找到入口格，设定初始面向 East ( 如果是右手抹墙则是 West），然后重复执行以下操作：

1. 如果当前格为最后一排且向南可以移动，则说明当前格为终点，结束。

2. 根据当前格的数据，找到下一步需要面向的方向， 方法是，如果当前方向上有墙，则顺时针（右手抹墙则逆时针）转身，重复这一步骤直到面向的方向上可以行走. 这里可以参考 turn 函数

3. 沿当前方向走一步， 参考 move 函数

4. 逆时针（右手抹墙则顺时针）转身一次，使当前面对方向为第3步之后的左手（或右手）方向， 然后回到步骤1

最后， 我的代码假定迷宫入口一定是从第1行的North 方向进入，出口一定是从最后一行的 South 方向出去，如果要支持从第一行的其他方向进（比如从 (0, 0) 的West进） ，最后一行的其他方向出，你需修改查找入口的代码和判断出口的代码，这个很简单， 自己去搞定吧。

N=0
E=1
S=2
W=3

classWalker(object):
def__init__(self,x,y,direction):
#coordinates
self.x=x
self.y=y
self.direction=direction

defturn(self,clockwise=True):
ifclockwise:
self.direction=(self.direction+1)%4
else:
self.direction=(self.direction+4-1)%4

defmove(self):
ifself.direction==N:
self.x-=1
elifself.direction==E:
self.y+=1
elifself.direction==S:
self.x+=1
elifself.direction==W:
self.y-=1

defget_coords(self):
return(self.x,self.y)

defget_direction(self):
returnself.direction


defpuzzle_walk(puzzle,left_touching=True):
route=[]
rows=len(puzzle)
columns=len(puzzle[0])

#locatetheentrance
coords=(-1,-1)
foryinrange(columns):
cell=puzzle[0][y]
ifcell[N]:
coords=(0,y)
break
assertcoords[0]>=0andcoords[1]>=0

walker=Walker(coords[0],coords[1],Eifleft_touchingelseW)
whileTrue:
x,y=walker.get_coords()
cell=puzzle[x][y]
route.append(tuple([x,y]))

ifx==rows-1andcell[S]:
#foundtheexit
break

#
whilenotcell[walker.get_direction()]:
walker.turn(left_touching)

#move
walker.move()

#facetothedirectionofthehand
walker.turn(notleft_touching)

returnroute


#运行结果
>>>p=[[(False,True,True,False),(True,True,False,True),(False,False,True,True)],[(True,False,True,False),(False,True,False,False),(True,False,False,True)]]
#左手抹墙
>>>puzzle_walk(p)
[(0,1),(0,2),(1,2),(1,1),(1,2),(0,2),(0,1),(0,0),(1,0)]
#右手抹墙
>>>puzzle_walk(p,False)
[(0,1),(0,0),(1,0)]

‘贰’ Python基于递归算法实现的走迷宫问题

Python基于递归算法实现的走迷宫问题
本文实例讲述了Python基于递归算法实现的走迷宫问题。分享给大家供大家参考，具体如下：
什么是递归?
简单地理解就是函数调用自身的过程就称之为递归。
什么时候用到递归？
如果一个问题可以表示为更小规模的迭代运算，就可以使用递归算法。
迷宫问题：一个由0或1构成的二维数组中，假设1是可以移动到的点，0是不能移动到的点，如何从数组中间一个值为1的点出发，每一只能朝上下左右四个方向移动一个单位，当移动到二维数组的边缘，即可得到问题的解，类似的问题都可以称为迷宫问题。
在python中可以使用list嵌套表示二维数组。假设一个6*6的迷宫,问题时从该数组坐标[3][3]出发，判断能不能成功的走出迷宫。
maze=[[1,0,0,1,0,1],
[1,1,1,0,1,0],
[0,0,1,0,1,0],
[0,1,1,1,0,0],
[0,0,0,1,0,0],
[1,0,0,0,0,0]]
针对这个迷宫问题，我们可以使用递归的思想很好的解决。对于数组中的一个点，该点的四个方向可以通过横纵坐标的加减轻松的表示，每当移动的一个可移动的点时候，整个问题又变为和初始状态一样的问题，继续搜索四个方向找可以移动的点，知道移动到数组的边缘。
所以我们可以这样编码：
# 判断坐标的有效性，如果超出数组边界或是不满足值为1的条件，说明该点无效返回False，否则返回True。
def valid(maze,x,y):
if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
return True
else:
return False
# 移步函数实现
def walk(maze,x,y):
# 如果位置是迷宫的出口，说明成功走出迷宫
if(x==0 and y==0):
print("successful!")
return True
# 递归主体实现
if valid(maze,x,y):
# print(x,y)
maze[x][y]=2 # 做标记，防止折回
# 针对四个方向依次试探，如果失败，撤销一步
if not walk(maze,x-1,y):
maze[x][y]=1
elif not walk(maze,x,y-1):
maze[x][y]=1
elif not walk(maze,x+1,y):
maze[x][y]=1
elif not walk(maze,x,y+1):
maze[x][y]=1
else:
return False # 无路可走说明，没有解
return True
walk(maze,3,3)
递归是个好东西呀！

‘叁’ python走迷宫算法题怎么解

示例：


#coding:UTF-8
globalm,n,path,minpath,pathnum
m=7
n=7
k=[0,1,2,3,4,5,6,7]#循环变量取值范围向量
a=[[0,0,1,0,0,0,0,0],
	[1,0,1,0,1,1,1,0],
	[0,0,0,0,1,0,0,0],
	[1,1,1,1,1,0,0,0],
	[0,0,0,0,0,1,1,0],
	[0,0,0,0,0,0,0,0],
	[0,0,1,1,1,1,1,1],
	[0,0,0,0,0,0,0,0]]#迷宫矩阵
b=[[1,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0]]	#状态矩阵
path=[]	
minpath=[]
min=10000
step=0
pathnum=0
#print(a)
#print(b)
defnextone(x,y):
	globalpath,minpath,m,n,min,step,pathnum
	if(x==0)and(y==0):
		path=[]
		step=0
	if(x==m)and(y==n):
		pathnum+=1
		print("step=",step)
		print("path=",path)
		ifstep<min:
			min=step
			minpath=path[:]
	else:
		if(x+1ink)and(yink):
			if(b[x+1][y]==0)and(a[x+1][y]==0):
				b[x+1][y]=1
				path.append([x+1,y])
				step+=1
				nextone(x+1,y)
				step-=1
				path.remove([x+1,y])
				b[x+1][y]=0#回溯
		if(xink)and(y+1ink):
			if(b[x][y+1]==0)and(a[x][y+1]==0):
				b[x][y+1]=1
				path.append([x,y+1])
				step+=1
				nextone(x,y+1)
				step-=1
				path.remove([x,y+1])
				b[x][y+1]=0#回溯	
		if(x-1ink)and(yink):
			if(b[x-1][y]==0)and(a[x-1][y]==0):
				b[x-1][y]=1
				path.append([x-1,y])
				step+=1
				nextone(x-1,y)
				step-=1
				path.remove([x-1,y])
				b[x-1][y]=0#回溯
		if(xink)and(y-1ink):
			if(b[x][y-1]==0)and(a[x][y-1]==0):
				b[x][y-1]=1
				path.append([x,y-1])
				step+=1
				nextone(x,y-1)
				step-=1
				path.remove([x,y-1])
				b[x][y-1]=0#回溯					
				
nextone(0,0)
print()
print("min=",min)
print("minpath=",minpath)
print("pathnum=",pathnum)
		

	

‘肆’ 少儿编程究竟学习的是什么

首先，编程作为语言类的学科，由两大核心构成：语法和词汇，如果想要顺利的使用编程编写程序，这两部分缺一不可。

现在正式的编程教育大都从大学开始，接触十分吃力。语言类学科最好的学习方法就是耳濡目染，从小学起。

就像英语，从小我们还不懂语法，可以先背单词，再慢慢拓展。而对于编程，大部分词汇来自英语，所以先让孩子接触词汇显然不明智，只能从语法入手。

那么什么是编程的语法呢？

逻辑思维，这种思维能力是编程的核心，一切程序都是通过逻辑联系起来的。

现在的少儿编程所学的也就是培养孩子的思维能力。

那少儿编程具体学些什么呢？

根据孩子年龄的不同有不同的课程，最基础的是利用scratch，一种图形化编程工具，跳过了编程中词汇一关，直接进行程序编写训练。

这种训练可以锻炼孩子的思维能力，提前熟悉编程的编写思路，对以后编程学科的学习大有裨益。

‘伍’ 深度学习，包括哪些

作为人工智能最稀缺的人才之一，深度学习工程师面临近百万的缺口，成为了各大企业竞相争夺的香饽饽，月薪大都在30K-80K之间。越来越多的程序员、院校学生开始学习深度学习算法。

可以说，如果你想要提升技能，在专业领域更上一步，《AI深度学习》可以成为你当下的选择！

‘陆’ 儿童机器人编程入门应该学什么

一、学习基础结构搭建和简单机械传动，如杠杆结构、齿轮传动等；通过超声波传感器的应用，学习基础的编程知识，如顺序结构、循环结构，培养学生编程启蒙及动手能力。

二、学习基础机械结构和传动，如连杆结构、多级传动；通过超声波传感器的应用，学习基础的编程知识，如顺序结构、循环结构、条件判断等，培养学生编程思维及分析简单问题、解决问题能力。

三、学习中等难度的机械结构和传动，如曲柄摇杆、齿轮组的多级传动结构、通过触碰、红外触感器、超声波传感器的应用，综合利用循环结构、顺序结构和分支结构完成任务，如遥控赛车、走迷宫等综合性的任务。培养学生综合分析、解决问题能力，最终达到培养学生计算思维与解决问题能力的目标。

四、让具有一定计算机编程基础的学生，从图形化编程过渡到Python语言。

在巩固基本知识的基础上，进一步学习数据结构和核心算法，包括人工智能中常用的一些算法。强调数据结构、算法及应用。对人工智能算法有深入理解，从问题“解决者”变为事物“创造者”，结合设计思维和计算思维，增强算法设计能力。

五、在孩子们有了一定的编程基础之后，他们可以根据他们不同的需要和兴趣学习C语言、C++语言、java语言、Python语言等。

‘柒’ 关于python 设计一个小游戏

应该可以的。设计一个阵列，描述墙壁和空间，通过算法使阵列可以旋转。

小球从入口进入以后，在阵列里滚动，通过计算重力和在斜面上的分力，算出小球运动的方向和速度。

到达阵列墙壁时，根据速度和方向以及墙壁的角度，计算反弹的方向和速度。直到小球滚出阵列。

我有一个Python3写的匀速运动弹球的代码，可以参考下

importturtle
defstop():
globalrunning
running=False
defmain():
globalrunning
screenx,screeny=turtle.Screen().screensize()
x,y=turtle.pos()
stepx=10
stepy=10
print(x,y,screenx,screeny)
turtle.clear()
turtle.speed(0)
#turtle.Screen().bgcolor("gray10")
#turtle.Screen().tracer(False)
turtle.up()
turtle.shape("circle")
turtle.shapesize(5,5)
turtle.left(45)
whileTrue:
ifx+5>screenx:
stepx=-stepx
turtle.left(90)
ify+5>screeny:
stepy=-stepy
turtle.left(90)
ifx+5<-screenx:
stepx=-stepx
turtle.left(90)
ify+5<-screeny:
stepy=-stepy
turtle.left(90)
turtle.fd(10)
x+=stepx
y+=stepy
if__name__=='__main__':
print(main())
turtle.done()

‘捌’ 只使用python的标准库，能做出什么有趣的东西

只用标准库是吧，不用任何第三方模块或者软件是吧，没问题，我来展示一个用 Python 写的 GIF 动态图，演示的是概率论中的 Wilson Uniform Spanning Tree算法 (也是一个迷宫生成算法)，连 tkinter, turtle 之类的发行版内置的图形库都统统不需要。

‘玖’ n皇后问题 c++

回溯法程序：
#include<iostream.h>
#include<string.h>
#include<time.h>
#define size 100
int board[size];
int ver[size];
int ru[size*2];//右上
int rd[size*2];//右下
int n,find; int rec[size];
//回溯搜索
void dfs(int t)
{
int i;
if(find) return;
if(t==n)
{
find=1;
for(i=0;i<n;i++)
{
rec[i]=board[i];
}
return;
}
for(i=0;i<n;i++)
{
if(ver[i]==1) continue;
if(ru[i-t+n]==1) continue;
if(rd[i+t]==1) continue;
ver[i]=1;
ru[i-t+n]=1;
rd[i+t]=1;
board[t]=i;
dfs(t+1);
rd[i+t]=0;
ru[i-t+n]=0;
ver[i]=0;
}
return;
}
int main()
{
int i,j,t1,t2;
cout<<"输入棋盘大小：";
cin>>n;
t1=clock();
find=0; memset(ver,0,sizeof(ver));
memset(ru,0,sizeof(ru)); memset(rd,0,sizeof(rd));
dfs(0);
t2=clock();
if(find)
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(rec[i]==j) cout<<'X';
else cout<<'+';
}
cout<<endl;
}
else
cout<<"Can't find!n";
cout<<"耗费时间："<<t2-t1<<"msn";
return 0;
}

既然是回溯法，楼主可以看看回溯法
---------2 回溯法：如果在第i行无论如何放置皇后，都和前面i-1行的皇后互相攻击的话，说明i-1行的皇后位置不合理，于是就回退一行，重新计算。这类似于走迷宫，如果在某个路口实在不下去了，只好退后一步重新选择。在退后一步重新选择的时候，显然可以排除已经尝过的路线。

下面重点分析回溯法解决N皇后问题。

很容易想到，在同一行上只能放置一个皇后，因此nxn的棋盘上放n个皇后的方案必然是每一行上放一个皇后。这样的话，我们可以使用一个一维数组q[n]来保存最后的方案，其中q[i]的含义是第i行上皇后的位置。比如q[3]=5，则表示第三行上的皇后在第5格。

上面无论哪种方法，都要解决一个问题：如何量化的判断两个皇后是否相互攻击？有了数组q的定义，我们很容易发现如下的规律：

对于两个皇后q[i]和q[j]，互相不攻击的条件是：
1 i != j，即不在同一行。
2 q[i] != q[j]，即不再同一列。
3 |q[i] - q[j]| != |i - j|，即不在一个对角线上。

根据前面的分析，我们假设前面的i-1行的皇后已经布好，即互不攻击，则在第i行上的皇后位置为q[i]，那么我们可以把q[i]依次和前面的i-1行比较，如果q[i]和前面的i-1行互不攻击的话，则说明第i行的皇后q[i]就是一个合理的位置，则继续寻找i+1行的皇后合理位置。如果第i行的皇后和前面的i-1行的某个皇后有攻击，则第i行的皇后需要右移一格，重新和前面的i-1行进行比较。

在进行具体处理时，要注意边界条件，即回退到棋盘第一行以及皇后已经右移到棋盘的最后一行的最后一格的情况，都意味着当前皇后位置使得N皇后问题无解。

下面是算法：

PROCEDURE QUEEN(n)
FOR i = 1 TO n DO q[i] = 1
i = 1
loop:
IF(q[i] <= n) THEN
{
k = 1
WHILE((k < i) and ((q[k] - q[i])) * (|q[k] - q[i]| - |k - i| ) != 0)
DO k = k + 1

IF(k < i) THEN q[i] = q[i] + 1
ELSE
{
i = i + 1
IF(i > n) THEN
{
OUTPUT q[i] (i = 1,2,...,n)
q[n] = q[n] + 1
i = n
}
}
}
ELSE
{
q[i] = 1
i = i - 1
IF(i < 1) THEN RETURN
q[i] = q[i] + 1
}

TOGO loop
RETURN