如何在 prolog 中追踪 clpfd 的回溯? [英] How to trace backtracks of clpfd in prolog?

问题描述

我正在使用 clpfd 库 制作带有 prolog 的 sudoku 求解器.我必须跟踪回溯和每个标有行和列的方块以及它以下列形式获得的数字:

I am making a sudoku solver with prolog using clpfd library. I have to trace the backtracks and every squares labeled with row and column and the number it gets in the following form:

(1 ,1 ,1)              
(9 ,2 ,1)              
BT
(5 ,2 ,1)              

我的问题是如何从算法中获取上述信息?

My question is how can I get the above information from the algorithm?

另一个问题:算法是否自己遵守arc-consistency规则?

Another question: Does the algorithm observe arc-consistency rules by itself?

推荐答案

我不认为这是一个特别好的主意，但这里有一些使用 SWI-Prolog 的属性变量的东西，它在任何时候打印一组变量的绑定他们中的一个被绑定了:

I don't think this is a particularly good idea, but here is something using SWI-Prolog's attributed variables that prints the bindings of a set of variables whenever one of them becomes bound:

:- use_module(library(clpfd)).

% Vars is a list of Name-Variable pairs where Variable is a free variable
% and Name is an atom or some other identifier for the variable.
trace_vars(Vars) :-
    maplist(trace_var(Vars), Vars).

trace_var(Vars, Id-V) :-
    when(ground(V), print_new_binding(Vars, Id-V)).

print_new_binding(Vars, Id-V) :-
    format('new binding ~w, all bindings now: ~w~n', [Id-V, Vars]).

从某种意义上说，您可以使用它来跟踪"事物:

You can use this to "trace" things, in a sense:

?- Vars = [a-A,b-B,c-C], trace_vars(Vars), [A,B,C] ins 0..1, A #< B, B #< C.
new binding a-0, all bindings now: [a-0,b-_G211,c-_G217]
new binding b-1, all bindings now: [a-0,b-1,c-_G217]
false.

这只会打印新的绑定，包括之前绑定的变量，但它不会不打印变量在回溯时解除绑定的时刻.该信息是隐含的(并且需要丑陋的黑客才能变得明确):

This only prints new bindings, including for variables that were bound before, but it does not print the moment when variables become unbound on backtracking. That information is implicit (and would need ugly hacks to become explicit):

?- Vars = [a-A,b-B,c-C], trace_vars(Vars), [A,B,C] ins 0..1, labeling([], [A,B,C]).
new binding a-0, all bindings now: [a-0,b-_G208,c-_G214]
new binding b-0, all bindings now: [a-0,b-0,c-_G214]
new binding c-0, all bindings now: [a-0,b-0,c-0]
Vars = [a-0, b-0, c-0],
A = B, B = C, C = 0 ;
new binding c-1, all bindings now: [a-0,b-0,c-1]
Vars = [a-0, b-0, c-1],
A = B, B = 0,
C = 1 ;
new binding b-1, all bindings now: [a-0,b-1,c-_G214]
new binding c-0, all bindings now: [a-0,b-1,c-0]
Vars = [a-0, b-1, c-0],
A = C, C = 0,
B = 1 ;
new binding c-1, all bindings now: [a-0,b-1,c-1]
Vars = [a-0, b-1, c-1],
A = 0,
B = C, C = 1 ;
new binding a-1, all bindings now: [a-1,b-_G208,c-_G214]
...

对于您的用例，使用坐标作为 Vars 列表中的标识符，例如，[(1,1)-Var11, (1,2)-Var12, ...].

For your use case, use coordinates as identifiers in the Vars list, e.g., [(1,1)-Var11, (1,2)-Var12, ...].

不过，我不认为以这种方式观看 clpfd 会启发您.

I don't think watching clpfd at work in this way will enlighten you, though.

正如 mat 在评论中指出的那样，在 print_new_binding/2 中添加一个 failing 第二个子句允许您重新访问之前的变量它的绑定被撤销:

As mat points out in the comments, adding a failing second clause to print_new_binding/2 allows you to revisit a variable before its binding is undone:

print_new_binding(_Vars, Id-_V) :-
    format('undo binding for ~w~n', [Id]),
    false.

这篇关于如何在 prolog 中追踪 clpfd 的回溯?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！