0

我正在尝试编写一个简单的程序来检查输入数独板当前是否不正确；即它在一行、一列或“框”中有两个相同的数字。我在行和列部分没有遇到任何问题 - 一个相当简单的任务，我使用以下代码完成（应该注意，'0' 表示尚未填充的正方形）：

:- use_module(library(clpfd)).

%Takes a matrix, determines if any row has repeating numbers
check([H|T]):-
    all_diff(H),
    check(T).
check([]).

%takes a list, checks if it contains repetitions other than '0'.
all_diff([]).
all_diff([X|Xs]) :-
    ( X = 0 ->
    all_diff(Xs)
        ;
        \+memberchk(X, Xs),
      all_diff(Xs)

    ).

consistent(Rows):-
    check(Rows),                %verify rows are free of repeats
    transpose(Rows,Columns),    %L1 represents columns
    check(Columns),         %verify all columns are free of repeats
        [H|T] = Rows,
        length(H,M),
    K is integer(sqrt(M)).     %this will give me dimensions of each box (KxK)

但是，我不太清楚如何生成将代表 KxK“框”的列表（其中 K 是行长的平方根）。我得到了 K 的值，我想我想按照将 row1 划分为 K 个子列表的方式做一些事情，然后将 row2 的 K 个子列表附加到 row1 的子列表的末尾，直到我到达 row(K*K)。

不幸的是，我真的不知道如何去做这件事？有没有我可以使用的 BIP 来做一些事情，比如获取一个列表并将其分解为 X 列表，每个列表长度为 Y？

否则，有什么想法吗？我知道一个很小但关于dowhile循环的东西，我想它们可以在这里实现，但我也不确定我会怎么做？非常感谢你的帮忙！

4

1 回答 1

1

一种简单但效率不高的方法可以使用索引算术和循环：

...
    Sq = 3,
    findall(B, (between(1, Sq, R),
            between(1, Sq, C),
            block(M, Sq, R, C, B)), Bs).

cell(M, R,C, V) :-
    nth1(R,M,Row), nth1(C,Row,V).

block(M, Sq, R,C, B) :-
    findall(V, (between(1, Sq, X),
            between(1, Sq, Y),
            I is (R-1) * Sq + X,
            J is (C-1) * Sq + Y,
            cell(M, I, J, V)), B).

在library(clpfd) 的文档中，有一种更有效的方法，仅限于已知的标准尺寸。您可以尝试概括该代码。

编辑这里是我的测试用例：请注意它是假的矩阵，只是为了便于理解块在哪里。

q(Bs) :-
    M = [[1,2,3,4,5,6,7,8,9],
         [a,b,c,d,_,3,_,8,5],
         [x,y,z,_,2,_,_,_,_],
         [u,v,z,e,t,y,_,_,_],
         [b,b,b,e,t,y,1,_,_],
         [c,c,c,e,t,y,_,_,_],
         [5,_,_,_,_,_,_,7,3],
         [_,_,2,_,1,_,_,_,_],
         [_,_,_,_,4,_,_,_,9]],

    Sq = 3,
    findall(B, (between(1, Sq, R),
            between(1, Sq, C),
            block(M, Sq, R, C, B)), Bs).

cell(M, R,C, V) :-
    nth1(R,M,Row), nth1(C,Row,V).

block(M, Sq, R,C, B) :-
    findall(V, (between(1, Sq, X),
            between(1, Sq, Y),
            I is (R-1) * Sq + X,
            J is (C-1) * Sq + Y,
            cell(M, I, J, V)), B).

并使用以下命令进行测试：

?- q(Bs),maplist(writeln,Bs).
[1,2,3,a,b,c,x,y,z]
[4,5,6,d,_G928,3,_G934,2,_G940]
[7,8,9,_G895,8,5,_G904,_G907,_G910]
[u,v,z,b,b,b,c,c,c]
[e,t,y,e,t,y,e,t,y]
[_G796,_G799,_G802,1,_G808,_G811,_G814,_G817,_G820]
[5,_G769,_G772,_G775,_G778,2,_G784,_G787,_G790]
[_G736,_G739,_G742,_G745,1,_G751,_G754,4,_G760]
[_G706,7,3,_G715,_G718,_G721,_G724,_G727,9]
Bs = [[1, 2, 3, a, b, c, x, y|...], [4, 5, 6, d, _G928, 3, _G934|...], [7, 8, 9, _G895, 8, 5|...], [u, v, z, b, b|...], [e, t, y, e|...], [_G796, _G799, _G802|...], [5, _G769|...], [_G736|...], [...|...]].
于 2012-04-18T16:15:03.043 回答