序言 - 拉丁方的解決方案

我現在有這個權利：使用SWI-Prolog的庫

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).

來源

2012-12-16 Izabela

：

:- 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([_]).

測試：

編輯你的代碼，一旦糾正刪除錯別字，它是一個驗證者，而不是一個生成器，但（由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代替。

來源

2012-12-16 23:03:55 CapelliC

與@CapelliC一樣，我推薦使用CLP（FD）約束，這在所有嚴重的Prolog系統中都是可用的。

事實上，考慮更廣泛地使用約束，以從約束傳播中受益。

例如：

:- use_module(library(clpfd)). 

latin_square(N, Rows, Vs) :- 
     length(Rows, N), 
     maplist(same_length(Rows), Rows), 
     maplist(all_distinct, Rows), 
     transpose(Rows, Cols), 
     maplist(all_distinct, Cols), 
     append(Rows, Vs), 
     Vs ins 1..N.

實施例，計數所有的解決方案爲N = 4：

 
?- findall(., (latin_square(4,_,Vs),labeling([ff],Vs)), Ls), length(Ls, L). 
L = 576, 
Ls = [...].

的CLP（FD）的版本比其他版本快得多。

請注意，將實際檢索的核心關係與labeling/2分開是一種好的做法。這可以讓你快看，核心關係也終止了較大N：

 
?- latin_square(20, _, _), false. 
false.

因此，我們直接看到這個終止，因此這加上labeling/2任何後續搜索是保證找到所有的解決方案。

來源

2015-10-19 09:11:45 mat

我具有更好的溶液，@CapelliC碼需要很長的時間方塊與N-長度高於5.

:- use_module(library(clpfd)). 

make_square(0,_,[]) :- !. 
make_square(I,N,[Row|Rest]) :- 
    length(Row,N), 
    I1 is I - 1, 
    make_square(I1,N,Rest). 

all_different_in_row([]) :- !. 
all_different_in_row([Row|Rest]) :- 
    all_different(Row), 
    all_different_in_row(Rest). 


all_different_in_column(Square) :- 
    transpose(Square,TSquare), 
    all_different_in_row(TSquare). 

all_different_in_column1([[]|_]) :- !. 
all_different_in_column1(Square) :- 
    maplist(column,Square,Column,Rest), 
    all_different(Column), 
    all_different_in_column1(Rest). 


    latin_square(N,Square) :- 
    make_square(N,N,Square), 
    append(Square,AllVars), 
    AllVars ins 1..N, 
    all_different_in_row(Square), 
    all_different_in_column(Square), 
    labeling([ff],AllVars).

來源

2016-01-20 10:03:18 Zwoniar

序言 - 拉丁方的解決方案

回答

相關問題