このディレクトリの索引
http://toro.2ch.net/test/read.cgi/tech/1361082416/727
#  [1] 授業単元: 暇つぶし 
#  [2] 問題文:迷路を解くプログラム。 
#   下記のようなテキストを入力とし、スタートからゴールまでの道を表示してください。 
#  ----- ここからテキスト ----- 
#  5 5 
#  sxrrr 
#  rxrrr 
#  rrrxr 
#  rrxgr 
#  ----- ここまでテキスト ----- 
#   テキストの1行目は順番に迷路の横幅と縦幅を表します。 
#   二行目以降は迷路を表しており、sはスタート、gはゴール、xは壁、rは道を表します。 
#   壁は通り抜けることはできず、道を通る必要があります。迷路の端は壁として扱います。 
#   表示の仕様は以下の通り。ゴールまでの道がないと判断した場合はNot Foundと表示。 
#  1 step 
#  sxrrr 
#  +xrrr 
#  rrrxr 
#  rrxgr 
#  <中略> 
#  9 step 
#  sxrrr 
#  +x+++ 
#  +++x+ 
#  rrxg+ 
#  

'問題文:迷路を解くプログラム。 
 下記のようなテキストを入力とし、スタートからゴールまでの道を表示してください。 
----- ここからテキスト ----- 
5 5 
sxrrr 
rxrrr 
rrrxr 
rrxgr 
----- ここまでテキスト ----- 
 テキストの1行目は順番に迷路の横幅と縦幅を表します。 
 二行目以降は迷路を表しており、sはスタート、gはゴール、xは壁、rは道を表します。 
 壁は通り抜けることはできず、道を通る必要があります。迷路の端は壁として扱います。 
 表示の仕様は以下の通り。ゴールまでの道がないと判断した場合はNot Foundと表示。 
1 step 
sxrrr 
+xrrr 
rrrxr 
rrxgr 
<中略> 
9 step 
sxrrr 
+x+++ 
+++x+ 
rrxg+ '(_テキスト) :-
        'テキストを入力とし、スタートからゴールまでの道を表示してください。'(_テキスト).
 
'テキストを入力とし、スタートからゴールまでの道を表示してください。'(_テキスト) :-
        テキストを入力とし(_テキスト,LL1,LL2),
        スタートからゴールまでの(LL1,LL2,_スタートからゴールまでの道順),
        '道を表示してください。'(_スタートからゴールまでの道順,LL1).

スタートからゴールまでの(LL1,LL2,_スタートからゴールまでの道順) :-
        スタートを探す(LL1,LL2,_スタートの行,_スタートの列),
        ゴールを探す(LL1,LL2,_ゴールの行,_ゴールの列),
        隣に移動する(_スタートの行,_スタートの列,_ゴールの行,_ゴールの列,LL1,LL2,[],_スタートからゴールまでの道順).

テキストを入力とし(_テキスト,LL1,LL2) :-
        get_lines(_テキスト,[_不要要素|_行ならび]),
        findall(_文字ならび,(
                    member(_一行,_行ならび),
                    atom_chars(_一行,_文字ならび)),
                LL1),
        転置(LL1,LL2).

スタートを探す(LL1,LL2,_スタートの行,_スタートの列) :-
        nth1(_スタートの行,LL1,L),
        nth1(_スタートの列,L,s).

ゴールを探す(LL1,LL2,_ゴールの行,_ゴールの列) :-
        nth1(_ゴールの行,LL1,L),
        nth1(_ゴールの列,L,g).

隣に移動する(_ゴールの行,_ゴールの列,_ゴールの行,_ゴールの列,LL1,LL2,_,[[_ゴールの行,_ゴールの列]]).
隣に移動する(_行,_列,_ゴールの行,_ゴールの列,LL1,LL2,_履歴1,[[_行,_列]|R]) :-
        移動可能な隣接点を得る(_行,_列,LL1,LL2,_隣の行,_隣の列),
        \+(member([_隣の行,_隣の列],_履歴1)),
        隣に移動する(_隣の行,_隣の列,_ゴールの行,_ゴールの列,LL1,LL2,[[_行,_列]|_履歴1],R).

移動可能な隣接点を得る(_行,_列,LL1,LL2,_行,_隣の列) :-
        行の移動可能な隣接点(_行,_列,LL1,LL2,_行,_隣の列).
移動可能な隣接点を得る(_行,_列,LL1,LL2,_行,_隣の列) :-
        列の移動可能な隣接点(_行,_列,LL1,LL2,_行,_隣の列).

行の移動可能な隣接点(_行,_列,LL1,LL2,_行,_隣の列) :-
        nth1(_行,LL1,L),
        length([_|L0],_列),
        append(L0,[_|R],L),
        移動可能な隣接点(L0,R,_隣の列).

列の移動可能な隣接点(_行,_列,LL1,LL2,_隣の行,_隣の列) :-
        nth1(_列,LL2,L),
        length([_|L0],_行),
        append(L0,[_|R],L),
        移動可能な隣接点(L0,R,_隣の行).

移動可能な隣接点(L0,R,_隣) :-
        last(L0,r),
        length(L0,_隣).
移動可能な隣接点(L0,R,_隣) :-
        R = [r|_],
        length([_,_|L0],_隣).

'道を表示してください。'(_スタートからゴールまでの道順,LL) :-
        append(LL0,[[_行,_列]|RR],_スタートからゴールまでの道順),
        length([_|LL0],_ステップ),
        write('%t\n',[_ステップ]),
        '通過点を+に置換してLLを表示する'(_行,_列,LL),
        R = [].

'通過点を+に置換してLLを表示する'(_行,_列,LL) :-
        append(L0,[L1|R],LL),
        length([_|L0],_行_1),
        列の置換(_行_1,_行,_列,L1,L2),
        ならびを文字列に変換して表示(L2),
        R = [].

列の置換(_行,_行,_列,L1,L2) :-
        length([_|L0],_列),
        append(L0,[_|R],L1),
        append(L0,[+|R],L2),!.
列の置換(_,_,_,L,L).

ならびを文字列に変換して表示(L) :-
        atomic_list_concat(L,S),
        writef('%t\n',[S]).

転置([],[],[])  :-  !.
転置([[A|R1]|R2],[R1|R3],[A|R4])  :-
        転置(R2,R3,R4).

転置([[]|_],[])  :-  !.
転置(L,[L1|R2])  :-
        転置(L,L2,L1),
        転置(L2,R2).