在3×3的釘板上，把一枚紅圖釘插在其中一個(gè)角落上，然后在除了對(duì)角之外的其余洞中，插上藍(lán)圖釘，如圖所示。圖釘可以向上、向下或橫向移動(dòng)到相鄰的空位，但不能沿對(duì)角線方向移動(dòng)，也不能跳過別的圖釘。
請(qǐng)以最少的移動(dòng)次數(shù)，使紅圖釘?shù)竭_(dá)對(duì)角的位置。
當(dāng)你認(rèn)為已找到3×3釘板的最好解答后，請(qǐng)?jiān)囍?×4的釘板上，然后在5×5的釘板上解同樣的問題。
這時(shí)你應(yīng)該已考慮出一套基本策略，可以將紅圖釘移動(dòng)到板上的任何位置。因此，可以試著用公式說明在n×n的釘板上，移動(dòng)紅圖釘?shù)綄?duì)角所需最少次數(shù)N，以及n與N的關(guān)系。
解答與分析
在3×3的釘板上需走13步。
在4×4的釘板上需走21步。
在5×5的釘板上需走29步。
N=8n-11
這些數(shù)字和公式也許經(jīng)多次的嘗試后就可以得到，不過還是應(yīng)作更深入的探討。
先把3×3釘板上的各個(gè)位置從1到9編號(hào)，如圖1。在紅圖釘移動(dòng)之前，旁邊必須要有空位。最簡單的做法，就是移動(dòng)最靠邊的3枚圖釘，使空位按照1→2→3→4的次序移動(dòng)，這樣位于9的紅圖釘就可以在第四次移動(dòng)時(shí)到達(dá)4�，F(xiàn)在紅圖釘可以用一種有系統(tǒng)的方式，按部就班地以向右、向上、再向右的路線移動(dòng)，最后抵達(dá)對(duì)角；每一步都可以用3枚圖釘?shù)囊苿?dòng)說明(圖2)。
圖3分別表示在3×3、4×4、5×5的釘板上，紅圖釘?shù)囊苿?dòng)路線，以及每一步所需要的移動(dòng)次數(shù)。
因此在n×n的釘板上，總共所需的移動(dòng)次數(shù)為：
N＝(2n-2)＋(2n-3)×3＝8n-11
嘗試在長方形的釘板上探討類似問題。
