PrologでNクイーン問題

はじめに

大学の講義で前回c言語でNクイーン問題を解いてもらったのでそれを参考にPrologでNクイーン問題を解くプログラム書いてくださいという課題がだされたのでそのソースと解,思ったことを最後に書きます.何かあったらご指摘あると嬉しいです

内容

プログラム全般

swi-prologで動かしており,OSはMacです.
nqueen(Nq).
がメインの述語となり,Nqに解きたいクイーンの数を代入して最終結果を出力します

ソースコード

/*リスト内の指定した要素を取り出す述語*/
accesslist(0,[X|_],X):- !.
accesslist(N,[_|Rest],X):-
N1 is N-1,accesslist(N1,Rest,X).

/*リスト結合述語conc*/

conc([], List, List).
conc([X | L1], L2, [X | List]) :-conc(L1, L2, List).

/*リスト要素確認述語member*/

member(X,[X|_]):-!.
member(X,[_|L]):-member(X,L).

/*任意の位置に要素をリストに追加する述語*/
insert_at(0, X, Ls, [X | Ls]):- !.
insert_at(N, X, [Y | Ls], [Y | Zs]) :-
    N > 0, N1 is N - 1,insert_at(N1, X, Ls, Zs).

/*引数番目の要素Xを消去する述語remove*/
remove(0, [_ | Ls], Ls):-!.
remove(N, [X | Ls], [X | Zs]) :-
    N > 0, N1 is N - 1, remove(N1, Ls, Zs).

%-----------------------------
/*
get_confの述語の渡す引数を最小にする述語nget_conf:引数はクイーンのリスト,選んだ列,クイーンの個数,返り値
*/
nget_conf(Queens,Num,Nq,Ans):- get_conf(Queens,Num,Nq,0,0,Ans).
/*
get_conf(List,Num,Nq,Conf,Loop,Ans):List内のNum列目がいくつ衝突しているかを返す関数
*/
get_conf(Queens,Num,Nq,Conf,Loop,Ans):-     /*Confには0を渡す*/
Loop < Nq,!,
Temp is Num - Loop,
accesslist(Loop,Queens,X),  /*Queens[i]の要素を取り出す*/
accesslist(Num,Queens,Y),   /*Queens[num]の要素を取り出す*/
(Loop =\= Num,              /*loopが検索したい行列と一緒ではない*/
(X + Temp =:= Y;
X - Temp =:= Y;
X =:= Y),               /*衝突条件の3条件をorでつなぐ*/
Conf1 is Conf+1,!;      /*衝突条件があったときconfをインクリメント*/
Conf1 is Conf),         /*無い時はそのまま*/
Loop1 is Loop+1,
get_conf(Queens,Num,Nq,Conf1,Loop1,Ans);
Loop =:= Nq,Ans is Conf,true,!.

%--------------------------------
/*
init_queensの述語の渡す引数を最小にする述語ninit_queens():引数はクイーンの数,返り値
*/
ninit_queens(Nq,Ans):-init_queens([],Nq,0,Ans).

/*
init_queens(Queens,Nq,Loop,Ans):クイーンをランダムに配置する。ただし同じ行に2つ以上ンクイーンはこない.
*/
init_queens(Queens,Nq,Loop,Ans):-           /*Queensには[]空配列を渡す.答えはAnsに返す*/
Loop < Nq,!,
proccess(Queens,Nq,Temp),                   /*今までに一度も入ってない行の計算*/
conc([Temp],Queens,NewQueens),              /*queensに値を入れる*/
NewLoop is Loop + 1,                        /*イクリメント*/
init_queens(NewQueens,Nq,NewLoop,Ans);      /*ループ*/
Loop =:= Nq,Ans = Queens,true.              /*すべての配列に入力が完了したらAnsに値を返す*/

proccess(Queens,Nq,Temp):-
Temp1 is random(Nq),                    /*ランダムに数値を取得*/  
not(member(Temp1,Queens)),!,            /*今までに使われてなければTempに取得した値をいれ,関数を終了させる*/
Temp=Temp1,true;
proccess(Queens,Nq,Temp).       /*そうでない場合はもう一度行う.*/

%--------------------------------
/*
get_attackの述語の渡す引数を最小にする述語nget_attack,引数はクイーンのリスト,クイーンの個数,返り値
*/
nget_attack(Queens,Nq,Ans):-get_attack(Queens,Nq,[],0,Ans).

/*
各列のクイーンの衝突数を計算する述語:get_attack
*/
get_attack(Queens,Nq,Attack,Loop,FAns):-
Loop<Nq,!,
get_conf(Queens,Loop,Nq,0,0,Ans),
conc(Attack,[Ans],NewAttack),
NewLoop is Loop+1,
get_attack(Queens,Nq,NewAttack,NewLoop,FAns);
Loop=:=Nq,FAns=Attack,true.

%----------------------------------
/*
すべてのクイーンに関して衝突がないことの確認述語:check_attack
*/
check_attack([]):- !.
check_attack([First|AttackRest]):-
First =:= 0,
check_attack(AttackRest).

%----------------------------------
/*
select_move_queen()関数の作成,衝突のあるクイーンの中から1つ移動させるクイーンを選ぶ.
*/
select_move_queen(Attack,Nq,Temp):-
Temp is random(Nq),
accesslist(Temp,Attack,X),
X =\= 0,!,true;
select_move_queen(Attack,Nq,Temp).
%----------------------------------
/*渡す引数最小の述語nget_min:衝突数のデータ,クイーンの個数,返り値*/
nget_min(Data,Nq,Num):-get_min(Data,Nq,1,[0],Num).

/*
渡されたデータの中から最小のものの添字を返す
*/
get_min(Data,Nq,Loop,List,Num):-        /*Loopには1を渡す,Listには[0]を渡す*/
accesslist(0,Data,Point),
loop(Data,Nq,Loop,List,Point,Ans),      /*衝突数最小の行番号のリストを取得*/
length(Ans,AnsL),
A is random(AnsL),                      /*長さを取得しランダムに数字を選ぶ*/
accesslist(A,Ans,Num).                  /*Numに値をいれる*/
%----------------------------------
/*
get_minのための衝突数最小の行番号のリストを取得する述語
*/
loop(Data,Nq,Loop,List,Point,Ans):-     /*衝突数最小の行番号のリストを取得*/    
Loop<Nq,!,
accesslist(Loop,Data,Temp),
((Temp==Point,!,                    /*データが最小の要素であるとき*/
Point1 = Point,
conc([Loop],List,NewList));         /*その添字もリストに格納*/
(Temp < Point,!,                    /*新しいデータが今までのデータより小さいとき*/
Point1 = Temp,                              
NewList = [Loop]);                  /*リストを初期化して最小の要素を取得*/
NewList = List,                     /*データがそれよりも多い時は変えず*/
Point1 = Point),
Loop1 is Loop +1,
loop(Data,Nq,Loop1,NewList,Point1,Ans); /**/
Loop=:=Nq,Ans=List,true.                /*ループが終わった時の処理*/

%----------------------------------
/*
change_queen():Num列目について衝突数の一番少ない行にクイーンを移動させる関数
*/
change_queen(Queens,Conf,Nq,Num,LastQueens):-
nget_min(Conf,Nq,Move),
remove(Num,Queens,NewQueens),
insert_at(Num,Move,NewQueens,LastQueens).

%----------------------------------
/*
渡す引数最小の述語nset_conf,渡すのはqueens,Nq,調べる列Num
*/
nset_conf(Queens,Nq,Num,Ans):-set_conf(Queens,Nq,Num,[],0,Ans).
/*
set_conf():選択した列を行に移動した時の衝突回数を調べる述語
*/
set_conf(Queens,Nq,Num,Conf,Loop,Ans):-
Loop<Nq,!,                                  /*ここからinsertまでが値の変換*/
remove(Num,Queens,NewQueens),
insert_at(Num,Loop,NewQueens,New1Queens),
nget_conf(New1Queens,Num,Nq,Temp),          /*ここでconfの計算をする*/
conc(Conf,[Temp],NewConf),                  /*リストにconfの値を格納*/
Loop1 is Loop +1,
set_conf(Queens,Nq,Num,NewConf,Loop1,Ans);  /*ループしてnqまで*/
Loop =:= Nq,Ans = Conf,true.

%----------------------------------
/*
solve_queen():check_attackが0となるまでNクイーン問題を解く述語
今回はMAX_LOOPは10000とする
*/
solve_queen(Queens,Nq,Loop,Attack):-
Loop < 10000,!,
((check_attack(Attack),!,                   /*check_attackを通ればそれは解なので出力して終了*/
write(Queens),nl,write(Loop),write(回),nl,
printqueen(Queens,0,Nq));
select_move_queen(Attack,Nq,Num),           /*移動するクイーンの選択*/
nset_conf(Queens,Nq,Num,Conf),              /*列の衝突を調べる*/
change_queen(Queens,Conf,Nq,Num,LQueens),   /*クイーンの交換*/
nget_attack(LQueens,Nq,NewAttacked),        /*新しくした盤面での衝突数の更新*/
Loop1 is Loop +1,
solve_queen(LQueens,Nq,Loop1,NewAttacked)); /*ループ*/
Loop =:= 10000,write(notsolve),true.        /*マックス回数超えた時の処理*/
%----------------------------------
/*
main関数の述語化
*/
nqueen(Nq):-
ninit_queens(Nq,Queens),            /*盤面の配置(ランダム)*/
nget_attack(Queens,Nq,Attacked),    /*衝突数を計算*/
solve_queen(Queens,Nq,0,Attacked).  /*あとは解く*/
%----------------------------------

printqueen(Queens,Loop,Nq):-
Loop<Nq,!,
(print2queen(Queens,0,Loop,Nq),
Loop1 is Loop +1,
printqueen(Queens,Loop1,Nq));
Loop =:= Nq,true.

print2queen(Queens,Loop,Temp,Nq):-
Loop < Nq,!,
(accesslist(Temp,Queens,X),
(X =:= Loop,!,put(124),put(81);
put(124),put(45)),
Loop1 is Loop + 1,
print2queen(Queens,Loop1,Temp,Nq));
Loop =:= Nq,put(124),nl,true.

実行例

コマンドライン

?- nqueen(12).

実行結果

[8,3,1,10,2,6,9,11,4,0,7,5]
60回
|-|-|-|-|-|-|-|-|Q|-|-|-|
|-|-|-|Q|-|-|-|-|-|-|-|-|
|-|Q|-|-|-|-|-|-|-|-|-|-|
|-|-|-|-|-|-|-|-|-|-|Q|-|
|-|-|Q|-|-|-|-|-|-|-|-|-|
|-|-|-|-|-|-|Q|-|-|-|-|-|
|-|-|-|-|-|-|-|-|-|Q|-|-|
|-|-|-|-|-|-|-|-|-|-|-|Q|
|-|-|-|-|Q|-|-|-|-|-|-|-|
|Q|-|-|-|-|-|-|-|-|-|-|-|
|-|-|-|-|-|-|-|Q|-|-|-|-|
|-|-|-|-|-|Q|-|-|-|-|-|-|
true.

最後に

今回このプログラムはC言語から直すということをもとにやっているのでif文だったりfor文だったりを相当書いています.そのときに共通に使っている手法があるのでそれを備忘録的な意味でも書いておきます

for文

まずはfor文のcとprologの互換について例えば以下のcのプログラムがあったとします

for(int i = 0;i<n;i++){
    A;
}

このプログラムをprologにしてみます

for(I,N):-
I < N,!,
(A,
I1 is I + 1,
for(I1));
I=:=n,true.

Aには複数の実行文をいれてもprolog側ではそれに対応する述語を「,」でつなぐ形にすれば問題ないかと思います.

if文

続いてif文の互換について同様に以下のようなcのプログラムがあるとします

if(X){
    A
}else if(Y){
   B
}

このプログラムをprologにしてみます

((X,!,A);
(Y,!,B)).

とすれば変換できると思います.全てをかこっている括弧がif文全体の節という認識,その中にある小さな括弧がif文の条件による制御一つ一つという認識でいいかと思います.