Prolog - 拉丁方解决方案

Question

我正在尝试用 Prolog 编写一个程序来找到大小为 N 的拉丁方。

我现在有这个:

delete(X, [X|T], T).
delete(X, [H|T], [H|S]) :-
   delete(X, T, S).

permutation([], []).
permutation([H|T], R) :-
   permutation(T, X),
   delete(H, R, X).

latinSqaure([_]).
latinSquare([A,B|T], N) :-
   permutation(A,B),
   isSafe(A,B),
   latinSquare([B|T]).

isSafe([], []).
isSafe([H1|T1], [H2|T2]) :- 
   H1 =\= H2, 
   isSafe(T1, T2).

Answer 1

使用 SWI-Prolog 库:

:- module(latin_square, [latin_square/2]).
:- use_module(library(clpfd), [transpose/2]).

latin_square(N, S) :-
    numlist(1, N, Row),
    length(Rows, N),
    maplist(copy_term(Row), Rows),
    maplist(permutation, Rows, S),
    transpose(S, T),
    maplist(valid, T).

valid([X|T]) :-
    memberchk(X, T), !, fail.
valid([_|T]) :- valid(T).
valid([_]).

测试:

?- aggregate(count,S^latin_square(4,S),C).
C = 576.

编辑您的代码，一旦更正并删除拼写错误，它就是一个验证器，而不是一个生成器，但是(正如 ssBarBee 在删除的评论中指出的那样)，它存在缺陷测试不相邻的行。 这里是更正后的代码

delete(X, [X|T], T).
delete(X, [H|T], [H|S]) :-
    delete(X, T, S).

permutation([], []).
permutation([H|T], R):-
    permutation(T, X),
    delete(H, R, X).

latinSquare([_]).
latinSquare([A,B|T]) :-
    permutation(A,B),
    isSafe(A,B),
    latinSquare([B|T]).

isSafe([], []).
isSafe([H1|T1], [H2|T2]) :-
    H1 =\= H2,
    isSafe(T1, T2).

和一些测试

?- latinSquare([[1,2,3],[2,3,1],[3,2,1]]).
false.

?- latinSquare([[1,2,3],[2,3,1],[3,1,2]]).
true .

?- latinSquare([[1,2,3],[2,3,1],[1,2,3]]).
true .

注意最后一个测试是错误的，应该给 false 来代替。