Abstract: hunt the minimum steps on the Nine puzzles
The result:
Number of steps: 18
Steps: ['823146570', '823140576', '820143576', '802143576', '842103576', '842013576', '042813576', '402813576', '412803576', '412083576', '412583076', '412583706', '412503786', '412053786', '012453786', '102453786', '120453786', '123450786', '123456780']
ok
The script:
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 24 09:44:46 2015
@author: yuan
"""
import numpy as np
import pandas as pd
# 8 puzzle problem
#record a queue using circling list
class queue:
def __init__(self,arr, q_len=1):
self.size=len(arr)
if q_len==1 or q_len<self.size:
self.q=[None]*self.size
self.q_len=self.size
else:
self.q=[None]*q_len
self.q_len=q_len
self.q[0]=0
self.q[1:self.size]=arr
self.head=1 #skip the index 0
self.tail=len(arr)+1 #the index of next element of arr
#print 'Initiate queue:', self.q
def q_size(self):
#print 'Size of the queue:', self.size
return self.size
def isFull(self):
return self.tail==(self.q_len+1)
def export_arr(self):
if self.tail>self.head:
arr=self.q[self.head:self.tail]
elif self.tail==self.head:
arr=[]
else:
arr=self.q[self.head:(self.q_len+1)] + self.q[1:self.tail]
return arr
def enqueue(self, value):
if self.size<self.q_len:
#increase size
self.size +=1
#increase tail
if self.tail==(self.q_len+1):
self.tail=1
#add value
self.q[self.tail]=value
self.tail += 1
else:
print "queue is full, fail to adding", value
#print '##', self.q, self.head,self.tail
#return self.export_arr()
def dequeue(self):
#increase head
value='NA'
#print self.head, self.tail
if self.size>0:
value=self.q[self.head]
if self.head==self.q_len:
self.head=1
else:
self.head +=1
#decrease size
self.size -= 1
#print 'remove', value, self.export_arr()
return value
##################
class breadth_first_search(queue):
def __init__(self, start,end):
self.start=str(start)
self.end=str(end)
self.next=[[1,0],[-1,0],[0,1],[0,-1]]
self.flag=0
self.book={}
def export_ways(self):
if self.flag==1:
ways=[self.end]
n=0
while n==0:
child_point=ways[0]
father_point=self.book[child_point]
ways.insert(0,father_point)
print father_point
if father_point==self.start:
n=1
break
print 'Number of steps:', len(ways)-1
print 'Steps:',ways
def shortest_way(self):
#initiate
q=queue([self.start], 10000)
self.book[start]=start
#
while q.q_size()>0 and self.flag==0:
start_str=q.dequeue()
start_list2=np.array( list(start_str) ).reshape(3,3)
start_x,start_y=divmod(start_str.index('0'), 3)
#print '=', start_str, q.q_size()
#
for i in range(4):
new_x=start_x+self.next[i][0]
new_y=start_y+self.next[i][1]
#print new_x,new_y
#
if 0<=new_x<3 and 0<=new_y<3:
tmp=np.array(start_list2)
tmp[start_x][start_y], tmp[new_x][new_y]=tmp[new_x][new_y],tmp[start_x][start_y]
end_str=str("".join(tmp.ravel() ))
#print 'tmp;', end_str
if end_str not in self.book.keys():
list2=tmp
self.book[end_str]=start_str
q.enqueue(end_str)
print start_str, end_str, q.q_size()
if end_str==self.end:
self.flag=1
break
#
print "export:"
self.export_ways()
#main
if __name__ == "__main__":
#store 9 puzzles into a 9-bit number
start=823146570
end=123456780
s=breadth_first_search(start,end)
s.shortest_way()
print 'ok'
No comments:
Post a Comment