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