このディレクトリの索引
http://toro.2ch.net/test/read.cgi/tech/1276873238/771
#  【 課題 】迷路の最短経路を与えるプログラムを考えよ. 
#  壁は#, 通路は.で表されている. 
#  また迷路の外側は全て壁(即ち#)となっている. 
#  スタート地点はS, ゴール地点はGである. 
#  スタートからゴールまでの道のりを表わせ. 
#  上へ移動する場合にはu, 同様に下はd, 右はr, 左はlとせよ. 
#  最短経路が複数ある場合は, それらのうちどれかひとつを出力せよ。 
#   
#  例1) 
#  ####### 
#  #..S..# 
#  #.....# 
#  #..G..# 
#  ####### 
#  答え) 
#  dd 
#   
#  例2) 
#  ####### 
#  #.....# 
#  #.G.#.# 
#  #..#..# 
#  #.#.S.# 
#  #.....# 
#  ####### 
#  答え) 
#  ldlluuru 
# 

最短経路(_迷路文字列ならび,_最短経路) :-
        迷路の定義(_迷路文字列ならび),
        出発点(Y0,X0),
        findmin([_距離,_経路],(
                    道に迷う([[Y0,X0]],Y0,X0,_方向ならび),
                    length(_方向ならび,_距離),
                    atom_chars(_経路,_方向ならび)),
                [_,_最短経路]).

道に迷う(_,Y,X,[]) :-
        終着点(Y,X).
道に迷う(_既に通過した点ならび,Y_1,X_1,[_方向|R]) :-
        隣接点を得る(_既に通過した点ならび,Y_1,X_1,Y_2,X_2,_方向),
        道に迷う([[Y_2,X_2]|_既に通過した点ならび],Y_2,X_2,R).

隣接点を得る(_既に通過した点ならび,Y_1,X_1,Y_2,X_2,_方向) :-
        member([_方向,A,B],[[r,1,0],[l,-1,0],[d,0,1],[u,0,-1]]),
        Y_2 is Y_1 + B,
        X_2 is X_1 + A,
        道(Y_2,X_2),
        \+(member([Y_2,X_2],_既に通過した点ならび)).


迷路の定義(_行文字列ならび) :-
        append(L0,[_行文字列|R],_行文字列ならび),
        length(L0,Y),
        sub_atom(_行文字列,X,1,_,_点),
        迷路の道部分の点定義(_点,Y,X),
        R = [].

迷路の道部分の定義(_点,Y,X) :-
        '道ならば位置を定義'(_点,Y,X),
        '出発点・終着点ならば位置を定義'(_点,Y,X),!.
迷路の道部分の定義(_,_,_).

'出発点・終着点ならば位置を定義'('S',Y,X) :-
        assertz(出発点(Y,X)),!.
'出発点・終着点ならば位置を定義'('G',Y,X) :-
        assertz(終着点(Y,X)),!.

道ならば位置を定義(A,Y,X) :-
        \+(A = '#'),
        assertz(道(Y,X)).