从最短到最长对列表进行排序

Question

我最近学习了prolog，正试图制作一个程序来为著名的益智游戏《骑士之旅》找到解决方案[在此处找到]

使用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，那将是一个很棒的

Answer 1

一个好的解决方案是将所有可能的移动表示为对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中具有候选点的密钥排序列表。然后你可以选择(例如)这个列表的第一个元素，或者使用：

member(_-Target, SFs)

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

请注意，您可能需要spot_freedom的其他参数，例如已经进行的移动的历史记录，以检测哪些位置已经被占用。我把弄清楚这件事当作练习。