0

Below is the code I am using to test backtracking algo to solve knight's tour, and it's not able to solve for odd board sizes. I would really appreciate if someone could point out the error in the code.

The code works fine for boards of even size, but it fails to find a solution for boards of odd sizes. 

def get_valid_moves_warnsdorff(moves, x, y, size):
    valid_moves = [(valid_move, len(get_valid_moves(moves, x + valid_move[0], y + valid_move[1], size))) for valid_move in get_valid_moves(moves, x, y, size)]
    sorted_moves = sorted(valid_moves, key=lambda w: w[1], reverse=False)
    return [move[0] for move in sorted_moves]
4

1 回答 1

0

您的代码要求您的游览已关闭（即，必须可以从最后一个方格移回第一个方格）。

这样的旅行并不总是适用于所有板尺寸。特别是对于一个M x N棋盘来说，如果两者M都是N奇数，就不会有封闭游。

要放宽代码的要求以便接受开放式游览，只需去掉这些行：

origin_touchers = get_valid_moves(moves, 0, 0, size)
if (x, y) not in origin_touchers and -1 not in [grid[origin_toucher[0]][origin_toucher[1]] for origin_toucher in origin_touchers]:
    return False

如果您确实想保留封闭式游览要求，则可以将该长条件简化为if not origin_touchers:. 不需要检查x,y（因为如果你在最后一步，你已经返回True）也不需要-1检查网格（因为get_valid_moves已经确保它返回的所有坐标都-1在网格上）。

于 2018-01-18T05:35:05.490 回答