このディレクトリの索引

% % C/C++の宿題片付けます 126代目 #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,_経路の数) :- 開始点は桝の中にある(_桝,_開始点_X,_開始点_Y), 度数(全ての桝を通過する駒の動き(_桝,_開始点_X,_開始点_Y,_),_経路の数). 開始点は桝の中にある(_桝,_開始点_X,_開始点_Y) :- between(1,_桝,_開始点_X), between(1,_桝,_開始点_Y). 全ての桝を通過する駒の動き(_桝,_開始点_X,_開始点_Y,_経路) :- 記録をとりながら全ての桝を通過する駒の動き(_桝,_開始点_X,_開始点_Y,[[_開始点_X,_開始点_Y]],_逆順経路), reverse(_逆順経路,_経路). 記録をとりながら全ての桝を通過する駒の動き(_桝,X,Y,L,_経路) :- 新しい移動可能点を得て全ての升目が埋まるまで駒の動きを続ける(_桝,X,Y,L,_経路). 記録をとりながら全ての桝を通過する駒の動き(_桝,X,Y,_経路,_経路) :- 全ての升目を通過した(_桝,_経路). 新しい移動可能点を得て全ての升目が埋まるまで駒の動きを続ける(_桝,X,Y,L,_経路) :- 新しい移動可能点を得る(_桝,X,Y,L,X2,Y2), 記録をとりながら全ての桝を通過する駒の動き(_桝,X2,Y2,[[X2,Y2]|L],_経路). 新しい移動可能点を得る(_桝,X,Y,L,X2,Y2) :- 移動可能点(_桝,X,Y,X2,Y2), 'X2,Y2は未だ通過していない'(L,X2,Y2). 'X2,Y2は未だ通過していない'(L,X2,Y2) :- \+(member([X2,Y2],L)). 変位(2,1). 変位(1,2). 変位(-1,2). 変位(-2,1). 変位(-2,-1). 変位(-1,-2). 変位(1,-2). 変位(2,-1). 移動可能点(_桝,I,J,X,Y) :- 変位を適用して移動可能点を得る(I,J,X,Y), 'X,Yは盤面上'(_桝,X,Y). 変位を適用して移動可能点を得る(I,J,X,Y) :- 変位(_x軸方向変位,_y軸方向変位), 移動可能点を得る(I,J,_x軸方向変位,_y軸方向変位,X,Y). 移動可能点を得る(I,J,_x軸方向変位,_y軸方向変位,X,Y) :- X is I + _x軸方向変位, Y is J + _y軸方向変位. 'X,Yは盤面上'(_桝,X,Y) :- between(1,_桝,X), between(1,_桝,Y). 全ての升目を通過した(_桝,_経路) :- _全ての升目数 is _桝 * _桝, length(_経路,_全ての升目数). 度数(_副目標,_度数) :- findall(1,_副目標,L), length(L,_度数).