Prologのテスト | Codetter（こーどったー）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
% File   : queens.pl
% Updated: 14 February 2008
% Purpose: N-Queen Puzzle (posed by Franz Nauch, 1850)
main :-
    write(‘N-Queen Puzzle (posed by Franz Nauch, 1850) ‘), nl,
    write(‘N = ‘),
    flush_output,
    read(N),
    N >= 4,
    read_yn(‘All solutions (y/n)? ‘, All),
    read_yn(‘Output (y/n)? ‘, Output),
    statistics(runtime, _),
    queen_solve(N, all(All), output(Output)),
    statistics(runtime, [_,T]),
    write(‘CPU time = ‘), write(T), write(‘ msec’), nl.
read_yn(Message, YN) :-
    write(Message),
    flush_output,
    read(X),
    (X == ‘y’ -> YN = yes; YN = no).
queen_solve(N, all(X), output(Y)) :-
    queens(N, Q),
    (Y == yes -> write(Q), nl; true),
    X == no,
    !.
queen_solve(_,_,_).
queens(N,Qs) :-
    range(1,N,Ns),
    queens(Ns,[],Qs).
queens([],Qs,Qs).
queens(UnplacedQs,SafeQs,Qs) :-
    select(UnplacedQs,UnplacedQs1,Q),
    not_attack(SafeQs,Q),
    queens(UnplacedQs1,[Q|SafeQs],Qs).
not_attack(Xs,X) :-
    not_attack(Xs,X,1).
not_attack([],_,_) :- !.
not_attack([Y|Ys],X,N) :-
    X =\= Y+N, X =\= Y-N,
    N1 is N+1,
    not_attack(Ys,X,N1).
select([X|Xs],Xs,X).
select([Y|Ys],[Y|Zs],X) :- select(Ys,Zs,X).
range(N,N,[N]) :- !.
range(M,N,[M|Ns]) :-
    M < N,
    M1 is M+1,
    range(M1,N,Ns).
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
実行例 SWI-Prolog   （gprologでは失敗）
?- [queens].
% queens compiled 0.01 sec, 4,112 bytes
true.
?- main.
N-Queen Puzzle (posed by Franz Nauch, 1850) 
N = 4.
All solutions (y/n)? y.
Output (y/n)? y.
[3, 1, 4, 2]
[2, 4, 1, 3]
CPU time = 0 msec
true.
?-
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX