+ 1

Knight's Tour Problem

Has anyone worked on knights tour problem?? My code works for 5X5 board but when I make the board 6X6 or 8X8(I mean higher value than 5) then it just keep on calculating forever. I know that there is no error in the code and it will work for values higher than 5 if i kept the code run for hours. Is it same with all you guys or I just have created a masterpiece. The code isnt naive solution it uses backtracking. def chk(x,r,c): if x[r][c]==0: return True return False def move_somewhere(x,r,c,t): tup=False for i in x: for j in i: if j==0: tup=True break if tup: break if not tup: global shlok shlok+=1 print() print(shlok) for i in x: print(i) return moves=[(r-2,c-1),(r-2,c+1),(r-1,c-2),(r-1,c+2),(r+2,c-1),(r+2,c+1),(r+1,c-2),(r+1,c+2)] moves2=[] for i in moves: p,q=i if (0<=p<aryan and 0<=q<aryan and chk(x,p,q)): moves2.append(i) moves=moves2 for p,q in moves: x[p][q]=t move_somewhere(x,p,q,t+1) x[p][q]=0 aryan=5#This is what determines the board size a=[] for i in range(aryan): a.append([0]*aryan) a[0][0]=1 shlok=0 move_somewhere(a,0,0,2)

2nd Sep 2021, 3:20 PM
Aryan Silswal
1 Respuesta
+ 1
cool
7th Sep 2021, 5:10 AM
Ivan Siniy
Ivan Siniy - avatar