0

我最近拿起了序言，并正在尝试制作一个程序来为著名的拼图骑士之旅找到解决方案 [在此处找到]

使用Warnsdorff算法，我试图找到可以从棋盘上的特定位置进行的所有可能的移动，然后进行移动后可能移动最少的移动，然后重复该过程，但是我有找不到所说的动作。

到目前为止，这是我的代码

possibleKnightMove(I, J, I1, J1) :- I1 is I+1, J1 is J+2.
possibleKnightMove(I, J, I1, J1) :- I1 is I+2, J1 is J+1.
possibleKnightMove(I, J, I1, J1) :- I1 is I+2, J1 is J-1.
possibleKnightMove(I, J, I1, J1) :- I1 is I+1, J1 is J-2.
possibleKnightMove(I, J, I1, J1) :- I1 is I-1, J1 is J-2.
possibleKnightMove(I, J, I1, J1) :- I1 is I-2, J1 is J+1.
possibleKnightMove(I, J, I1, J1) :- I1 is I-2, J1 is J-1.
possibleKnightMove(I, J, I1, J1) :- I1 is I-1, J1 is J+2.

possible_knight_moves(Rows, Columns, X, Y, Visited, NewX, NewY) :-
    possibleKnightMove(X, Y, NewX, NewY),
    NewX > 0, NewX =< Rows,
    NewY > 0, NewY =< Columns,
    \+ member([NewX,NewY], Visited).

possible_moves_count(Rows, Columns, X, Y, Visited, Count) :-
    findall(_, possible_knight_moves(Rows, Columns, X, Y, Visited, _NewX, _NewY), Moves),
    length(Moves, Count).

warnsdorff(Rows, Columns, X, Y, Visited, NewX, NewY, Score) :-
    possible_knight_moves(Rows, Columns, X, Y, Visited, NewX, NewY),
    possible_moves_count(Rows, Columns, NewX, NewY, [[NewX, NewY] | Visited], Score).

由于仅在找到所有可能移动的数量后才计算它们，因此我的列表未按我需要的方式排序。

例如这个输入

warnsdorff(8,8,3,5,[[1,1],[2,3],[3,5]], NewX, NewY, Score).

结果应该是

NewX = 4,
NewY = 7,
Score = 5

但是我得到

NewX = 1,
NewY = 4,
Score = 3

如果有人可以帮助我获得最低分数NewX，NewY那就太好了

4

1 回答 1

0

一个好的解决方案是将所有可能的移动表示为对 N-Spot，其中（例如）：

  • N是仍然可能的移动数Spot
  • Spot是我们可以搬到的地方。

在这样的列表中，您可以使用keysort/2对列表进行排序，使对的第一个元素处于非递减顺序。例如，该列表的第一个元素将是在进一步移动方面最受限制的点。

您已经非常接近解决方案了。我建议您首先集中评估单个可能的移动，根据这样的谓词spot_freedom(S, F)计算，对于一个点 S的自由度 F（计算仍然可能的移动数量 S）。

然后，您可以简单地执行以下操作：

findall(F-S, spot_freedom(S, F), SFs0),
keysort(SFs0, SFs)

并且在SFs候选点的keysorted列表中。然后，您可以选择（例如）此列表的第一个元素，或使用：

member(_-Target, SFs)

以增加回溯自由的顺序尝试可用的点。

请注意，您可能需要额外的参数spot_freedom，例如已移动的历史记录，以检测哪些位置已被占用。我把解决这个问题作为一个练习。

于 2016-06-10T09:17:23.457 回答