矩阵上的元素/3查找索引返回范围

Question

我有一个矩阵

Board

，其开头为：

[](
    [](1,2,3,4,5,6),
    [](_,1,_,_,5,_),
    [](_,5,1,_,_,6),
)

该程序的目标是以数独风格解决它，其中

_

是未知数。

我应用的第一条规则是每行不能包含重复的数字：

puzzle(Board) :-
    dim(Board, [M,N]), % the board has M rows and N columns
    Board :: 1..N, % every value in the board must be between 1 and N

    ( for(I,1,M), param(Board) do
        alldifferent(Board[I,*]) % no row contains duplicate numbers
    ),

    ( for(I,2,M), param(Distance, Board, N) do
        ( for(J,1,N), param(Distance, Board, I) do
            element(J, Board[I,*], Value),
            element(IndexAbove, Board[I-1,*], Value),
            abs(IndexAbove - J) #=< 2
        )
    ).

从

Board

循环后打印

alldifferent

，我可以看到它的状态：

[](
    [](1, 2, 3, 4, 5, 6),
    [](_1536{[2 .. 4, 6]}, 1, _1550{[2 .. 4, 6]}, _1564{[2 .. 4, 6]}, 5, _1578{[2 .. 4, 6]}),
    [](_1606{[2 .. 4]}, 5, 1, _1620{[2 .. 4]}, _1634{[2 .. 4]}, 6)
)

这是有道理的，因为第二行中的值不能是 1 或 5，但所有其他数字仍然有效（与第三行类似）。 下一个循环从第二行开始，对于该行中的每个值，查找上一行中相同值的索引，并断言索引的差异不大于 2。

我的问题是，当我打印

IndexAbove

的值时，我得到

_27569{4 .. 6}

（当

I=3,J=2

时），即使我可以确认

Value=5

，所以我的索引应该是

2

，而不是一系列潜在的值（因为索引

4..6

处的值在其域中都没有 5）。我怎样才能使

IndexAbove

统一为2？

附注我不太理解矩阵表示法以及何时可以使用它（

Board[I,*]

似乎获得了

I

第行，但我无法使用它来打印该行）。我的工作基于 https://eclipseclp.org/examples/sudoku.ecl.txt

Answer 1

据我所知，您的代码工作正常：

?- Board = []( [](1,2,3,4,5,6), [](_,1,_,_,5,_), [](_,5,1,_,_,6) ),
   puzzle(Board),
   labeling(Board).
No (0.00s cpu)

该示例按预期失败，因为 5 的位置违反了您的距离约束。如果放松约束，或者改变位置，就能正确找到解。

您所做的观察涉及计算的中间状态，其中域和约束的结果已部分传播。在开发模型时，您不应该太担心这一点。 在执行过程中，有许多单独的传播/推理步骤，并且试图跟踪域的精确演变很快就会失控。唯一真正重要（并且可以保证）的是，当所有变量都被实例化时，即当标签完成时，约束得到满足。

各个约束的实现（例如element/3）有 关于推理强度和算法复杂性的多个自由度。此具体示例中的行为的原因是，element/3 约束（的此实现）仅保持与数组变量相关的边界一致性：域有孔的事实被忽略。这降低了传播步骤期间的计算复杂性，但意味着可以稍后检测到故障和域缩减。然而，这些细节只影响性能，而不影响正确性。