I've tried to use BFS to solve Tower of Hanoi (with smallest step) with 10 disks and you can put the disk wherever you want but it takes way too long and take so much memory. Do you guys have any suggestion?
Which algorithms should i use for this 10 disks cases and the disk are randomly initiated and you can put the disk wherever you want in the solving process?
My code:
class Node():
def __init__(self,matrix,parent):
self.matrix = matrix
self.parent = parent
def CreateNode(matrix,parent) -> Node:
new_mat = [nested[:] for nested in matrix]
newnode = Node(matrix,parent)
return newnode
def appender(matrix,i,query,gone,solution):
if matrix[i] != []:
for j in range(3):
if j != i:
temp = [nested[:] for nested in matrix]
temp[j].append(temp[i].pop(-1))
if ''.join(map(str,temp)) not in gone:
gone.add(''.join(map(str,temp)))
sub_solution = CreateNode(temp,solution)
query.append(sub_solution)
def printMatrix(mat):
for i in mat:
for j in i:
print(j,end=" ")
print()
print("#")
def PrintSolution(root):
if root == None:
return
PrintSolution(root.parent)
printMatrix(root.matrix)
def solver(A,list):
gone = set()
query = []
root = Node(A,None)
query.append(root)
while query:
solution = query.pop(0)
if solution.matrix[-1] == list:
PrintSolution(solution)
return
for i in range(3):
appender(solution.matrix,i,query,gone,solution)
A = []
for i in range(3):
arr = [int(i) for i in input().split()]
A.append(arr)
maxi = max(max(A))
list = []
for i in range(maxi,-1,-1):
list.append(i)
solver(A,list)
Example input :
6 9 0 1 2
4 7
3 5 8
Output:
6 9 0 1 2
4 7
3 5 8
#
6 9 0 1 2
4 7 8
3 5
#
6 9 0 1
4 7 8
3 5 2
#
etc until solved
