◆愛知県 Y.M.Ojisan さんからの解答
【問題１】
１４手
スタート(1,1)→ (6,6)→(6,2)→(1,2)→(6,7)→(2,7)→ (2,1)→(7,6)→(2,6)→(7,1)→(7,8)→ (1,8)→(1,1)→(8,1)→(8,8)【問題２】
１４手が最短
14888通りある。
∵ PC探索によった。
単純な探索では莫大な探索時間を要するので、残りの手数で取れる最大の石数以上が残存していないかチェックした。
また２次元なので、２手連続で石をとらない手順は最小ではなく、これもチェックした。
１３手が存在しないことは短時間で確認できたが、１４手の全てを探索するには10時間を要した。
全手順は添付ファイル参照。
ただし初手が（８，８）の方向(４０９０通り）と（８，１）の方向（５３９９通り）のみである。
（１，８）の方向は（８，１）の手順を転置すればよい。
◆東京都 明 さんからの解答
【問題１】
手数：14手 手順：(1,1)→ (1,8)→(8,8)→(8,1)→(2,1)→(2,7)→ (7,7)→(7,2)→(3,2)→(3,6)→(7,6)→ (4,3)→(4,6)→(7,3)→(5,3)→【問題２】
14手が最短手数であることを証明します。
碁石の数を一般的にN×Nとします。
(1)石を拾う方向の、縦のラインの数がNの場合
縦のラインをつなぐために、間に必ず横、または斜めのラインが必要です。
したがって、手数は最低でも2N-1となります。
(2)石を拾う方向の、縦のラインの数がN-1の場合
縦のラインで拾えない石が縦にN個残ります。
横のライン、もしくは斜めのラインで残った石を拾うには、1つのラインでは1個の石しか拾えないことから、N本のラインが必要になります。
したがって、手数は最低でも2N-1となってしまいます。
(3)石を拾う方向を横にして議論しても(1)、(2)と同じになります。
したがって、拾う手数を2N-1より少なくするためには、
石を拾う縦、および横のラインをN-2以下とする必要があります。
(4)石を拾う縦のラインをN-v、横のラインをN-hとします。
（ただしv、hは2以上）
このラインで拾えない石がv×h個残りますが、これを斜めのラインで取り切る必要があります。
v×h個の最外周の石に着目します。
最外周の石の数は2v+2h-4個です。
斜めのラインは最外周の石を、最大でも2個しか取れません。
したがって、必要な斜めのラインは最小でもv+h-2本となります。
したがって、このとき最小手数は2N-2となります。
以上からN×Nの石を取り切るための最小手数は2N-2となります。
14手での取り方は、以下のように結構バリエーションがありそうです。
総当りプログラムではチェック数がかなりの数になりそうなので、解の数を求めるのは諦めてしまいました。
(1,8)→(8,8)→(8,1)→(2,1)→(2,7)→ (7,7)→(7,2)→(1,2)→(6,7)→(6,2)→ (2,6)→(5,6)→(5,3)→(2,3)→ (1,8)→(8,8)→(8,1)→(2,1)→(8,7)→ (2,7)→(2,2)→(7,2)→(7,6)→(2,6)→ (6,2)→(6,5)→(3,5)→(3,3)→ (8,8)→(8,1)→(1,8)→(1,1)→(7,1)→ (7,8)→(2,8)→(2,3)→(8,3)→(3,8)→ (3,2)→(8,2)→(3,7)→(6,7)→ (1,7)→(8,7)→(8,1)→(1,8)→(8,8)→ (1,1)→(7,1)→(2,6)→(6,6)→(6,1)→ (2,5)→(2,2)→(7,2)→(7,6)→ (1,8)→(7,2)→(7,8)→(2,8)→(2,1)→ (8,1)→(8,8)→(2,2)→(8,2)→(3,7)→ (3,3)→(8,3)→(4,7)→(6,7)→ (1,6)→(6,1)→(6,8)→(1,8)→(8,1)→ (8,8)→(1,1)→(7,1)→(7,8)→(1,2)→ (6,2)→(1,7)→(5,7)→(2,4)→
◆静岡県 ｍｅｄａｋａ さんからの解答
【問題１】
(1) hand solutionによる解
スタート(1,1)→ (1,8)→(8,8)→(8,1)→(2,1)→(8,7)→ (1,7)→(7,1)→(7,6)→(2,6)→(2,2)→ (6,2)→(6,5)→(3,5)→(3,2)→(2) ＰＣによる探索結果(少し珍しい形？)
スタート(1,1)→ (1,6)→(6,1)→(6,6)→(2,6)→(2,2)→ (6,2)→(1,7)→(8,7)→(8,1)→(1,1)→ (7,7)→(7,2)→(1,8)→(8,8)→ スタート(1,1)→ (6,6)→(3,6)→(8,1)→(1,1)→(1,8)→ (7,8)→(7,1)→(1,7)→(6,7)→(6,1)→ (2,5)→(2,2)→(8,2)→(8,8)→【問題２】
(答え)
最短手数は、１４手。
解の数は、７４４４通り。
（ただし、反転対称解は除外した)
(解法)
反復深化探索法のアルゴリズムで探索プログラムを作成しましたが、下限値評価関数にちょっと苦労しました。
詳細は添付のソース(ZIP圧縮)を見てください。
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる