?馬走日字問題，在n*m的棋盤中，馬只能走"日"字。馬從位置(x,y)出發，把棋盤的每一格都走一次且只走一次。找出所有路徑。?

　　這個問題可以用回溯法解，每一步都有八種可能的走法，設馬當前在(x,y)點，則它的可能走到：

　　(x+1,x+2),(x+1,x-2),(x-1,x+2),(x-1,x-2),(x+2,x+1),(x+2,x-1),(x-2,x+1),(x-2,x-1)

　　對每一種可能的走法試一遍，如果出界了或者已經走過了，則不用走了。試探一遍后，回溯。

　　python實現：

''' horse rides sun problem use backtracking algorithm author:ztp create at:2015/1/19 15:06 '''class HorseRides:def __init__(self, n, m, x, y):self.row = nself.column = mself.startx = xself.starty = yself.chessboard = [[0]*self.column for r in range(self.row+1)]self.sunx = [1, 1, 2, 2,-1,-1,-2,-2]self.suny = [2,-2, 1,-1, 2,-2, 1,-1]self.chessboard[self.startx][self.starty] = 1;self.count = 0;def check(self, x, y):if x >= self.row or y >= self.column or x < 0 or y < 0 or self.chessboard[x][y] != 0:return 0;return 1;def ride(self, x, y, step):for i in range(8):xx = x + self.sunx[i]yy = y + self.suny[i]if self.check(xx, yy) == 1:self.chessboard[xx][yy] = step;if step == self.row*self.column:self.output();else:self.ride(xx, yy, step+1)self.chessboard[xx][yy] = 0def output(self):self.count = self.count + 1print "count = %d" % self.countfor i in range(self.row):print self.chessboard[i]def getCount(self):return self.countif __name__ == "__main__":horseride = HorseRides(5,4,0,0)horseride.ride(0, 0, 2)print "total path: %d" % horseride.getCount()

　　

轉載于:https://www.cnblogs.com/zhutianpeng/p/3438978.html

總結

以上是生活随笔為你收集整理的马走日字--回溯法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。