このディレクトリの索引
このディレクトリの索引

% 
% http://pc12.2ch.net/test/read.cgi/tech/1242655611/809
% 
% <問題>>
% http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/9353.txt
% 
%  バックトラッキング法
% 
% 問題を解く過程が段階的に分かれており、各段階で次に進む選択肢が複数あるという問題は多々ある。各段階で判定を下すときは、
% 適当に選びずっと先の段階まで行って、その時の選択が間違っていたことが判って時点で、この段階まで逆戻りして異なる選択をする。
% 囲碁将棋の「待った」である。このような方法で正しい解を見つけるやり方をバックトラッキング法
% という。この解決の実装にはスタックが用いられることが多い。
% 
% そこで今回は2題問題を挙げる。
% 
% 題1 騎士の巡回問題
%    
%    西洋のチェスは8×8枡の盤にいろいろな駒が置かれている。騎士の駒は日本の将棋の斜め前に進む桂馬に似ているが、斜め後ろにも
%    戻れるところは異なっている。盤のKの位置に騎士いるときに、次に進むことができる位置は、図の0のところどれでも良い。
% 
% 
% 
%    
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  |  |  |  |  |  |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  |  |  O |  | O |  |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  | O |  |  |  | O |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  |  |  | K |  |  |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  | O |  |  |  | O |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  |  | O |  | O |   |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        |  |  |  |  |  |  |  |  |
%        +−−+−−+−−+−−+−−+−−+−−+−−+
%        
%      問題はある位置から出発してすべての位置を一回だけ訪れる方法が何種類あるかを求めること。つまり、一筆書きで全ての升目を通る方法が何回あるか。
% 
%    この問題を8×8枡でやると解がとてつもなくあるので盤を5×5枡に制限し、最初の位置をAとします。
% 
% 
% 
% 
%        +−−+−−+−−+−−+−−+
%        | A |  |  |  |  |
%        +−−+−−+−−+−−+−−+
%        |  |  |   |  |  | 
%        +−−+−−+−−+−−+−−+
%        |  |   |  |  |  | 
%        +−−+−−+−−+−−+−−+
%        |  |  |  |   |  |
%        +−−+−−+−−+−−+−−+
%        |  |   |  |  |  | 
%        +−−+−−+−−+−−+−−+
% 
%      最後に求まった盤の状況(訪れた順に番号を入れる)を印字し、全部の解答数を報告すること。
% 
% 
% 
% 
%  題2 再帰法による解法
%      おなじ問題をスタックを用いずに再帰プログラムで書きなさい。
% 
% 

可能経路数(_桝,_開始点_X,_開始点_Y,_経路の数) :-
        findall(1,駒の動き(_桝,_開始点_X,_開始点_Y,_),L),
        length(L,_経路の数).

駒の動き(_桝,_開始点_X,_開始点_Y,_経路) :-
        駒の動き(_桝,_開始点_X,_開始点_Y,[[_開始点_X,_開始点_Y]],_経路).

駒の動き(_桝,X,Y,L,_経路) :-
        移動可能点(_桝,X,Y,X2,Y2),
        \+(member([X2,Y2],L)),
        駒の動き(_桝,X2,Y2,[[X2,Y2]|L],_経路).
駒の動き(_桝,X,Y,L,_経路) :-
        _桝2 is _桝 * _桝,
        length(L,_桝2),
        reverse(L,_経路).

変位(2,1).
変位(1,2).
変位(-1,2).
変位(-2,1).
変位(-2,-1).
変位(-1,-2).
変位(1,-2).
変位(2,-1).

移動可能点(_桝,I,J,X,Y) :-
        変位(U,W),
        X is I+U,
        Y is J+W,
        X > 0,
        X =< _桝,
        Y > 0,
        Y =< _桝.