소개

Prolog에서 한 글을 쓰는 프로그램을 썼습니다.

오일러 정리

케니히스베르크 다리의 문제는 인기입니다. 수학자 오일러는 그래프 이론에서 오일러의 정리를 입증했고 케니히스베르크의 다리 문제는 해결되었습니다. 다음의 도형은 오일러의 정리에 의하면 일필 쓰기를 할 수 있을 것입니다.


이것을 Prolog에서 풀어 즐기세요.

아이디어

정점과 변에 다음 그림과 같이 이름을 붙였습니다.



모든 면을 리스트로 해 초기값으로 합니다. 이동 가능한 경로를 root/3으로 기억하십시오.

root(a,b,ab).

이것은 정점, a, b가 변 ab에 의해 연결되는 것을 의미합니다. 이동 가능한 루트를 백트랙에 의해 섬뜩하게 조사합니다. 이 때 통과한 변은 변의 리스트로부터 삭제합니다. 가장자리 목록으로 이동하려는 정점에 가장자리가 없으면 실패합니다. 다른 루트를 맞게됩니다. 결국 모든 모서리를 통과하고 모서리 목록이 []가 되었을 때 일필 쓰기가 성공한 경우입니다. 이 때에는 그 추가해 온 정점의 리스트를 화면 출력합니다.

실행 결과

O-Prolog Ver 1.62(Chika)
| ?- ['one-stroke.pl'].
yes
| ?- run.
[c,e,a,b,c,d,e,b,d]
[c,e,a,b,c,d,b,e,d]
[c,e,a,b,d,e,b,c,d]
[c,e,a,b,d,c,b,e,d]
[c,e,a,b,e,d,b,c,d]
[c,e,a,b,e,d,c,b,d]
[c,e,b,c,d,e,a,b,d]
[c,e,b,c,d,b,a,e,d]
[c,e,b,d,e,a,b,c,d]
[c,e,b,d,c,b,a,e,d]
[c,e,b,a,e,d,b,c,d]
[c,e,b,a,e,d,c,b,d]
[c,e,d,b,e,a,b,c,d]
[c,e,d,b,a,e,b,c,d]
...
[d,c,e,d,b,a,e,b,c]
[d,c,b,d,e,a,b,e,c]
[d,c,b,d,e,b,a,e,c]
[d,c,b,e,a,b,d,e,c]
[d,c,b,e,d,b,a,e,c]
[d,c,b,a,e,b,d,e,c]
[d,c,b,a,e,d,b,e,c]
yes

d나 c로부터 스타트 하는 경우만 밖에 필필을 할 수 없는 것 같습니다. 손으로 써보고 몇 가지 확인했습니다. 전부는 확인하고 있지 않습니다만, 좋은 것 같은 느낌입니다.

코드

Prolog라면 짧은 줄 수로 쓸 수 있습니다. 이 손의 문제에 적합합니다. 이것을 C언어등으로 기술하려고 하면, 꽤 까다롭다고 생각합니다.

root/3 정점과 변의 데이터
run/0 메인 술어
node/1 모든 정점 목록
edge/1 모든 변 목록
solve/1 리스트중의 모든 정점으로부터 스타트 해 일필 쓸 수 있을지 어떨지를 조사해, 가능하면 표시한다.
solve1/3 제1 인수를 스타트 지점, 제2 인수를 변의 리스트로서, 한 필기 가능하면 표시한다. 뒤 트랙에 포함.
delete/3 첫 번째 인수 목록에서 두 번째 인수를 제거한 것을 세 번째 인수로 unify합니다. 삭제할 것이 없으면 실패합니다.

root(a,b,ab).
root(b,c,bc).
root(b,d,bd).
root(b,e,be).
root(c,e,ce).
root(c,d,cd).
root(d,e,de).
root(e,a,ae).

node([a,b,c,d,e]).
edge([ab,bc,bd,be,ce,cd,de,ae]).

run :- node(N),solve(N).

solve([]).
solve([N|Ns]) :-
   edge(E),solve1(N,E,[N]).
solve([N|Ns]) :-
  solve(Ns).

solve1(X,[],R) :- reverse(R,R1),write(R1),nl,fail.
solve1(X,E,R) :-
  root(X,Y,E1),
  delete(E,E1,E2),
  solve1(Y,E2,[Y|R]).

solve1(X,E,R) :-
  root(Y,X,E1),
  delete(E,E1,E2),
  solve1(Y,E2,[Y|R]).

delete([X|Xs],X,Xs).
delete([X|Xs],Y,[X|Z]) :-
  delete(Xs,Y,Z).