I am trying to implement knight tour using iteration method. I have already wrote a program using recursion and its working fine, now instead of recursion I am using iteration method with stack to implement knight tour, I have wrote the below code. and here I can not backtrack when I reached to a dead end, could you please check my code and give me some solution.
class knightTour:
def __init__(self,size):
self.size = size
self.board = [[0 for x in range(self.size)] for y in range(self.size)]
def is_valid_move(self,row ,col):
if (row<0 or row>self.size-1 or col<0 or col>self.size-1 or self.board[row][col]!=0):
return False
return True
def display(self):
print
for x in range(self.size):
for y in range(self.size):
print self.board[x][y],
print
print
def solve(self,row,col,count,stack):
self.board[row][col] = count
count +=1
stack.push(row)
stack.push(col)
while count < self.size*self.size:
if (self.is_valid_move(row+2,col+1)):
row+=2
col+=1
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row+1,col+2)):
row+=1
col+=2
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row-1,col+2)):
row-=1
col+=2
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row-2,col+1)):
row-=2
col+=1
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row-2,col-1)):
row-=2
col-=1
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row-1,col-2)):
row-=1
col-=2
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row+1,col-2)):
row+=1
col-=2
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
elif (self.is_valid_move(row+2,col-1)):
row+=2
col-=1
self.board[row][col] = count
count+=1
stack.push(row)
stack.push(col)
else:
# " Backtrack " // how to do backtracking here ?
self.board[row][col] = 0
count-=1
stack.pop()
stack.pop()
col = stack.pop()
row = stack.pop()
stack.push(row)
stack.push(col)
stack = stack()
d = knightTour(8)
d.solve(0,0,1,stack)
d.display()
Advertisement
Answer
def solve(self,row,col,count,stack):
self.board[row][col] = count
count +=1
stack.append(row)
stack.append(col)
org=0
origin=[]
while count < self.size*self.size:
if (self.is_valid_move(row+2,col+1) and org<1):
row+=2
col+=1
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(1) //Origin to get hold values which will be used in iteration
org=0 //Helps in backtracking
elif (self.is_valid_move(row+1,col+2) and org<2): //Checks if the org is less than 2
row+=1
col+=2
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(2)
org=0
elif (self.is_valid_move(row-1,col+2) and org<3):
row-=1
col+=2
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(3)
org=0
elif (self.is_valid_move(row-2,col+1) and org<4):
row-=2
col+=1
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(4)
org=0
elif (self.is_valid_move(row-2,col-1) and org<5):
row-=2
col-=1
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(5)
org=0
elif (self.is_valid_move(row-1,col-2) and org<6):
row-=1
col-=2
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(6)
org=0
elif (self.is_valid_move(row+1,col-2) and org<7):
row+=1
col-=2
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(7)
org=0
elif (self.is_valid_move(row+2,col-1) and org<8):
row+=2
col-=1
self.board[row][col] = count
count+=1
stack.append(row)
stack.append(col)
origin.append(8)
org=0
else:
self.board[row][col] = 0
count-=1
stack.pop()
stack.pop()
col = stack.pop()
row = stack.pop()
stack.append(row)
stack.append(col)
org=origin.pop()
This is a toughie. I checked for 5*5 board and 6*6 please check for 7 and 8