프롤로그 : 잘못된 결과가 계속 나타납니다.

Question

다른 기사를 먹지 않고 체스에 최대 기사를 배치 할 수있는 프로그램을 만들려고합니다. 그 방법을 찾을 수 있었지만 해결책이있는 목록을 표시하는 대신 잘못된 결과가 계속 나타납니다.

:- use_module(library(lists), [member/2]). 
:- use_module(contestlib, [for/3]). 

genere(0,[]). 
genere(N,[N|L]) :- 
    N>0, 
    N1 is N-1, 
    genere(N1,L). 

generePos(N,[(Lig,Col)]) :- 
    genere(N,L), 
    member(Lig,L), 
    member(Col,L). 

genereEchiquier(N,PlacedKnights) :- 
    findall((X,Y),(for(X,1,N),for(Y,1,N)),PlacedKnights). 

knights(N) :- 
    genereEchiquier(N,PlacedKnights), 
    generePos(N,P1), 
    knighta(P1,PlacedKnights). 

knighta([(X,Y)|_],[]) :- 
    write("No solution, next sol"). 
knighta([(X,Y)|_],[_|PlacedKnights]) :- 
    ( is_attacked(X,Y,PlacedKnights) 
    -> knights(P1,PlacedKnights) 
    ; write([(X,Y)|PlacedKnights)! 
    ). 

is_attacked(X,Y,PlacedKnights) :- 
    (NX is X - 1, NY is Y - 2 
    ; NX is X - 1, NY is Y + 2 
    ; NX is X + 1, NY is Y - 2 
    ; NX is X + 1, NY is Y + 2 
    ; NX is X - 2, NY is Y - 1 
    ; NX is X - 2, NY is Y + 1 
    ; NX is X + 2, NY is Y - 1 
    ; NX is X + 2, NY is Y + 1 
    ), 
    member((NX,NY),PlacedKnights). 

디버그 모드에서 프로그램을 실행할 때 라인 knighta(P1,PlacedKnights). 프로그램을 knighta/2에 가져 가지 않음 : 여기

knighta([(X,Y)|_],[_|PlacedKnights]) 

나는 그 이유를 모른다. 모든

Answer 1

먼저, 코드 몇 가지 문제가 있습니다 :

• 먼저 내가 코드를 들여 당신을 조언 것은;
• ! 대신 ]을 사용해야합니다.
• 가끔 knights으로 전화하십시오. knighta이어야합니다.
• is_attached의 제약 전에 먼저 member을 사용해야합니다.

아마도 전체 재 설계를 고려해야합니다. 모든

첫째, 당신은 is_attacked 조건으로 다음 사용할 수 있습니다

is_attacked(X,Y,PlacedKnights) :- 
    member((NX,NY),PlacedKnights), 
    is_attacked(X,Y,NX,NY). 

is_attacked(XA,YA,XB,YB) :- 
    DX is abs(XA-XB), 
    DY is abs(YA-YB), 
    is_attacked(DX,DY). 

is_attacked(1,2). 
is_attacked(2,1). 

당신은 이렇게 온통 이미 배치 기사를 반복하고 그 차이를 계산하고 그것이 (2,1) 또는 (1,2) 차이가 있는지 확인. 이미 주어진와

generateSolution(R,_,R). 
generateSolution(Q,N,R) :- 
    for(X,1,N), 
    for(Y,1,N), 
    \+ member((X,Y),Q), 
    \+ is_attacked(X,Y,Q), 
    generateSolution([(X,Y)|Q],N,R). 

generateSolution(L,N,R)이 L와 술어가 이미 배치 된 기사입니다

, N 보드의 크기와 R 모든 구성 :

다음은 모든 가능한 구성을 생성하기 위해 다음과 같은 조건을 사용할 수 있습니다 기사는 정확합니다 (꼭 필요한 최대 기사 수는 아닙니다).

하지만은 효율적이지의 :

?- generateSolution([],4,R),length(R,4). 
R = [ (1, 4), (1, 3), (1, 2), (1, 1)] ; <- duplicate of 
R = [ (2, 2), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 1), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 2), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 3), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 4), (1, 3), (1, 2), (1, 1)] ; 
R = [ (1, 3), (1, 4), (1, 2), (1, 1)] ; <- this one 
R = [ (2, 1), (1, 4), (1, 2), (1, 1)] ; 
R = [ (3, 4), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 1), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 2), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 3), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 4), (1, 4), (1, 2), (1, 1)] ; 
R = [ (1, 4), (2, 1), (1, 2), (1, 1)] ; 
R = [ (2, 2), (2, 1), (1, 2), (1, 1)] ; 
R = [ (3, 4), (2, 1), (1, 2), (1, 1)] ; 

당신은 단지 (X,Y)을 증가시킬 수있다라는 제약 조건을 적용하여이 문제를 개선 할 수 있습니다 : 당신은 중복을 많이 생성하여을 깨는 대칭을 수행하지 않습니다 좌표 :

% Any solution is a solution. 
generateSolution(R,_,R). 
% If no knight is placed on the board, select one with arbitrary `X` and `Y`. 
generateSolution([],N,R) :- 
    for(X,1,N), 
    for(Y,1,N), 
    generateSolution([(X,Y)],N,R). 
% If already placed one, fetch that solution, and propose a position (X,Y) with the same X and larger Y 
generateSolution([(XL,YL)|T],N,R) :- 
    YL1 is YL+1, 
    for(Y,YL1,N), 
    \+ is_attacked(XL,Y,[(XL,YL)|T]), 
    generateSolution([(XL,Y),(XL,YL)|T],N,R). 
% Or generate one with a larger X 
generateSolution([(XL,YL)|T],N,R) :- 
    XL1 is XL+1, 
    for(X,XL1,N), 
    for(Y,1,N), 
    \+ is_attacked(X,Y,[(XL,YL)|T]), 
    generateSolution([(X,Y),(XL,YL)|T],N,R). 

여기

, 또는 Y 이전 Y보다 커야합니다, 또는 X가 커야합니다.

?- generateSolution([],4,R),length(R,4). 
R = [ (1, 4), (1, 3), (1, 2), (1, 1)] ; 
R = [ (2, 1), (1, 3), (1, 2), (1, 1)] ; 
R = [ (2, 2), (1, 3), (1, 2), (1, 1)] ; 
R = [ (3, 4), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 1), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 2), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 3), (1, 3), (1, 2), (1, 1)] ; 
R = [ (4, 4), (1, 3), (1, 2), (1, 1)] ; 
R = [ (2, 1), (1, 4), (1, 2), (1, 1)] ; 
R = [ (2, 2), (1, 4), (1, 2), (1, 1)] ; 
R = [ (3, 4), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 1), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 2), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 3), (1, 4), (1, 2), (1, 1)] ; 
R = [ (4, 4), (1, 4), (1, 2), (1, 1)] ; 
R = [ (2, 2), (2, 1), (1, 2), (1, 1)] ; 
R = [ (3, 4), (2, 1), (1, 2), (1, 1)] ; 
R = [ (4, 1), (2, 1), (1, 2), (1, 1)] ; 
R = [ (4, 2), (2, 1), (1, 2), (1, 1)] ; 
R = [ (4, 3), (2, 1), (1, 2), (1, 1)] ; 
R = [ (4, 4), (2, 1), (1, 2), (1, 1)] ; 
R = [ (3, 4), (2, 2), (1, 2), (1, 1)] ; 
R = [ (4, 1), (2, 2), (1, 2), (1, 1)] ; 

이제 기사의 최대 개수를 찾기 위해, 당신이 할 수있는 부트 스트랩 :

술어가로 작동

bootstrap(N,Sol) :- 
    once(bootstrap(N,[],0,Sol)). 

bootstrap(N,_,I,S) :- 
    once((generateSolution([],N,R),length(R,K),K > I)), 
    !, 
    bootstrap(N,R,K,S). 
bootstrap(_,S,_,S). 

은 다음과 같습니다 : 쿼리 따라서 더 이상 중복 고려하지 첫 번째 해결 방법으로 사용을하면 [] (항상 성공하는 빈 목록)을 사용하십시오. 다음 당신은 더 많은 기사와 구성에 대한 검색을 시작 : 기사 K의 수와 같은 솔루션 R이 발견

once((generateSolution([],N,R),length(R,K),K > I)), 

후에는, 현재의 솔루션으로 새로운 솔루션을 기사의 수를 설정하고 검색 시작 더 많은 기사가있는 솔루션. 결국 실패하면 마지막 현재 솔루션을 반환합니다.

예 :

?- bootstrap(1,S),write(S). 
[ (1,1)] 
S = [ (1, 1)]. 

?- bootstrap(2,S),write(S). 
[ (2,2), (2,1), (1,2), (1,1)] 
S = [ (2, 2), (2, 1), (1, 2), (1, 1)]. 

?- bootstrap(3,S),write(S). 
[ (3,3), (3,1), (2,2), (1,3), (1,1)] 
S = [ (3, 3), (3, 1), (2, 2), (1, 3), (1, 1)]. 

?- bootstrap(4,S),write(S). 
[ (4,4), (4,3), (4,2), (4,1), (1,4), (1,3), (1,2), (1,1)] 
S = [ (4, 4), (4, 3), (4, 2), (4, 1), (1, 4), (1, 3), (1, 2), (1, 1)]. 

?- bootstrap(5,S),write(S). 
[ (5,5), (5,3), (5,1), (4,4), (4,2), (3,5), (3,3), (3,1), (2,4), (2,2), (1,5), (1,3), (1,1)] 
S = [ (5, 5), (5, 3), (5, 1), (4, 4), (4, 2), (3, 5), (3, 3), (3, 1), (..., ...)|...]. 

?- bootstrap(6,S),write(S). 

전체 코드

: 기사가 공격을 깨는 추가 대칭을가할지 여부를

bootstrap(N,Sol) :- 
    once(bootstrap(N,[],0,Sol)). 

bootstrap(N,_,I,S) :- 
    once((generateSolution([],N,R),length(R,K),K > I)), 
    !, 
    bootstrap(N,R,K,S). 
bootstrap(_,S,_,S). 

generateSolution(R,_,R). 
generateSolution([],N,R) :- 
    for(X,1,N), 
    for(Y,1,N), 
    generateSolution([(X,Y)],N,R). 
generateSolution([(XL,YL)|T],N,R) :- 
    YL1 is YL+1, 
    for(Y,YL1,N), 
    \+ is_attacked(XL,Y,[(XL,YL)|T]), 
    generateSolution([(XL,Y),(XL,YL)|T],N,R). 
generateSolution([(XL,YL)|T],N,R) :- 
    XL1 is XL+1, 
    for(X,XL1,N), 
    for(Y,1,N), 
    \+ is_attacked(X,Y,[(XL,YL)|T]), 
    generateSolution([(X,Y),(XL,YL)|T],N,R). 

is_attacked(X,Y,PlacedKnights) :- 
    member((NX,NY),PlacedKnights), 
    is_attacked(X,Y,NX,NY). 

is_attacked(XA,YA,XB,YB) :- 
    DX is abs(XA-XB), 
    DY is abs(YA-YB), 
    is_attacked(DX,DY). 

is_attacked(1,2). 
is_attacked(2,1). 

주 더 똑똑한 기술이 존재, 예를 많은 시간에 대한 유효성 검사가 낭비된다 방법뿐만 아니라 generateSolution으로 기사 수가 적은 솔루션을 반환하지 못하게하는 방법에 대해 설명합니다. 이것은 단지 원시 스케치입니다. 당신이 알 수 있듯이

---

비 되돌아 최적의 솔루션

거의 모든 결과는 패턴에 따라 :

1: 
+-+ 
|x| 
+-+ 
2: 
+-+-+ 
|x|x| 
+-+-+ 
|x|x| 
+-+-+ 
3: 
+-+-+-+ 
|x| |x| 
+-+-+-+ 
| |x| | 
+-+-+-+ 
|x| |x| 
+-+-+-+ 
4: 
+-+-+-+-+ 
|x| |x| | 
+-+-+-+-+ 
| |x| |x| 
+-+-+-+-+ 
|x| |x| | 
+-+-+-+-+ 
| |x| |x| 
+-+-+-+-+ 

순간 N에서 발생하는 패턴이보다 큰

또는 N에 해당하는 기사는 (0,0)에 기사를 배치하고 모든 (i,i+2*j)에 i과 j intege를 rs (j은 0보다 작을 수 있음). 이것은 보장 된 최대 값입니다.

당신은 따라서 이것을 생성 할 수 있습니다

solution(1,[(1,1)]). 
solution(2,[(2,2),(2,1),(1,2),(1,1)]). 
solution(N,L) :- 
    N > 2, 
    solution([],N,1,1,L). 

solution(L,N,I,_,L) :- 
    I > N, 
    !. 
solution(L,N,I,J,S) :- 
    JN is J+2, 
    JN =< N, 
    !, 
    solution([(I,J)|L],N,I,JN,S). 
solution(L,N,I,J,S) :- 
    IN is I+1, 
    JN is (I mod 2)+1, 
    IN =< N, 
    !, 
    solution([(I,J)|L],N,IN,JN,S). 
solution(L,N,I,J,[(I,J)|L]). 

예 :

?- solution(20,L),write(L). 
[ (20,20), (20,18), (20,16), (20,14), (20,12), (20,10), (20,8), (20,6), (20,4), (20,2), (19,19), (19,17), (19,15), (19,13), (19,11), (19,9), (19,7), (19,5), (19,3), (19,1), (18,20), (18,18), (18,16), (18,14), (18,12), (18,10), (18,8), (18,6), (18,4), (18,2), (17,19), (17,17), (17,15), (17,13), (17,11), (17,9), (17,7), (17,5), (17,3), (17,1), (16,20), (16,18), (16,16), (16,14), (16,12), (16,10), (16,8), (16,6), (16,4), (16,2), (15,19), (15,17), (15,15), (15,13), (15,11), (15,9), (15,7), (15,5), (15,3), (15,1), (14,20), (14,18), (14,16), (14,14), (14,12), (14,10), (14,8), (14,6), (14,4), (14,2), (13,19), (13,17), (13,15), (13,13), (13,11), (13,9), (13,7), (13,5), (13,3), (13,1), (12,20), (12,18), (12,16), (12,14), (12,12), (12,10), (12,8), (12,6), (12,4), (12,2), (11,19), (11,17), (11,15), (11,13), (11,11), (11,9), (11,7), (11,5), (11,3), (11,1), (10,20), (10,18), (10,16), (10,14), (10,12), (10,10), (10,8), (10,6), (10,4), (10,2), (9,19), (9,17), (9,15), (9,13), (9,11), (9,9), (9,7), (9,5), (9,3), (9,1), (8,20), (8,18), (8,16), (8,14), (8,12), (8,10), (8,8), (8,6), (8,4), (8,2), (7,19), (7,17), (7,15), (7,13), (7,11), (7,9), (7,7), (7,5), (7,3), (7,1), (6,20), (6,18), (6,16), (6,14), (6,12), (6,10), (6,8), (6,6), (6,4), (6,2), (5,19), (5,17), (5,15), (5,13), (5,11), (5,9), (5,7), (5,5), (5,3), (5,1), (4,20), (4,18), (4,16), (4,14), (4,12), (4,10), (4,8), (4,6), (4,4), (4,2), (3,19), (3,17), (3,15), (3,13), (3,11), (3,9), (3,7), (3,5), (3,3), (3,1), (2,20), (2,18), (2,16), (2,14), (2,12), (2,10), (2,8), (2,6), (2,4), (2,2), (1,19), (1,17), (1,15), (1,13), (1,11), (1,9), (1,7), (1,5), (1,3), (1,1)] 
L = [ (20, 20), (20, 18), (20, 16), (20, 14), (20, 12), (20, 10), (20, 8), (20, 6), (..., ...)|...]. 

또는 그래픽 표현 :

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
| |x| |x| |x| |x| |x| |x| |x| |x| |x| |x| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|x| |x| |x| |x| |x| |x| |x| |x| |x| |x| | 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+