図2: 
将棋の駒を使ったパズルに「歩と銀を逆にするゲーム」というものがあります。次の動画で紹介されています: https://www.youtube.com/watch?v=vUoOiphQhR8
図2: 簡単に言うと、図1のように3x3のマスに歩、銀、金からなる8枚の駒を置いて始め、この限られた9マス内で将棋のルールに従った駒の動きで図2のような配置に持っていく、というゲームです。
例えば、34手での解答は次のようになります: 図3
このゲームの解で最小手数はいくつになるでしょうか。プログラムで初期状態から可能な状態遷移を網羅したゲーム木を生成すると、図4(svg/png)が得られます。
図4における矢印は、1つ駒を動かして得られる状態遷移を表します。ただし、グレーで白抜きの△からなる矢印による遷移は、最短でない経路であることを示します。ブルーで◇からなる矢印による遷移は(これも最短でない経路を表しますが)、駒を動かすと同時に盤面を左右反転させると(鏡像として)得られることを示します。
図4によって、このゲームの解としては32手が最短手数であることが分かります。また以下のようなことも分かります:
