将表谓词从b-prolog转换为gprolog [英] Translating a tabled predicate from b-prolog to gprolog

问题描述

出于娱乐目的，我一直在尝试编写骑士之旅( https://zh-CN.使用Warnsdorf规则在gprolog中解析wikipedia.org/wiki/Knight%27s_tour ).

For fun I've been attempting to write a Knight's Tour (https://en.wikipedia.org/wiki/Knight%27s_tour) solver in gprolog using Warnsdorf's rule.

我发现了另一个SO帖子，询问效率，它在B-prolog中提供了解决方案: 骑士的旅行效率解决方案.

I found another SO post asking about efficiency that provided a solution in B-prolog: knight's tour efficient solution.

我的问题出现在以下部分:

My problem arises with the following section:

:- table warnsdorff(+,+,+,+,+,-,-,min).
warnsdorff(R, C, X, Y, Visits, NewX, NewY, Score) :-
    possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
    possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Score).

B-pr​​olog具有表谓词的功能，而gprolog没有.我在尝试将表部分转换为gprolog时遇到很多困难.实际上，该函数应该返回当前位置的移动，从而导致新位置的最少个可能的移动(领带是随机选择的).

B-prolog features tabled predicates and gprolog does not. I'm having a great deal of difficulty trying to translate the table section to gprolog. In practice, the function is supposed to return the move from the current position that results in the least number of possible moves from the new position (ties are chosen at random).

任何帮助将不胜感激.干杯！

Any help would be greatly appreciated. Cheers!

推荐答案

在这种情况下，制表可能是过大的.由于Visits列表已经在求解时进行，因此只需使用memberchk/2.我在SWI-Prolog中获得了此解决方案(在其中实现了顺便说一句，制表，但无法使用您链接到的原始编码解决难题):

Probably, tabling is overkill for this problem. Since the Visits lists already is carried on while solving, just use memberchk/2. I get this solution in SWI-Prolog (where, BTW, tabling is implemented, but fails to solve the puzzle using the original coding you linked to):

?- time(knight(8, 8, 1, 1, [], Path))...
% 19,973 inferences, 0.019 CPU in 0.019 seconds (100% CPU, 1047591 Lips)
[(1,1),(2,3),(1,5),(2,7),(4,8),(6,7),(8,8),(7,6),(6,8),(8,7),(7,5),(8,3),(7,1),(5,2),(3,1),(1,2),(2,4),(1,6),(2,8),(3,6),(1,7),(3,8),(5,7),(7,8),(8,6),(7,4),(8,2),(6,1),(4,2),(2,1),(1,3),(3,2),(5,1),(6,3),(8,4),(7,2),(5,3),(4,1),(2,2),(1,4),(3,3),(2,5),(4,4),(6,5),(4,6),(3,4),(5,5),(4,3),(6,2),(8,1),(7,3),(5,4),(3,5),(4,7),(2,6),(1,8),(3,7),(4,5),(6,4),(5,6),(7,7),(5,8),(6,6),(8,5)]

如果您愿意，我可以向您展示Warnsdorff规则.我已经使用setof/3来获取最小数量，并加入了possible_knight_moves/7和possible_moves_count/6.

If you want, I can show you the Warnsdorff rule. I've used setof/3, to get the minimum count, joining possible_knight_moves/7 and possible_moves_count/6.

修改

根据需要:

warnsdorff(R, C, X, Y, Visits, NewX_, NewY_) :-
    setof((Count, NewX, NewY), (
              possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
              possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Count)
          ), [(_, NewX_, NewY_)|_]).

为清楚起见，我将输出变量重命名为NewX_，NewY_，但这无关紧要-它也适用于原始命名.

For clarity, I've renamed the output variables NewX_, NewY_, but that's irrelevant - it worked with the original naming as well.

这篇关于将表谓词从b-prolog转换为gprolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！