2018将棋パズルとは数年前にTwitterで女流棋士の中倉彰子さんの呟きを見てその存在を知りました、最近書籍を出されたようです。子供の頃4×4の16マスのケースに1〜15までの数字が書かれたバラバラのピースを数字の順に並べ直すというパズルをやったことがありますが、それの将棋版と思えばいいと思います。盤面は3×3で先手番の駒だけを自由に配置し、スタートの局面から将棋の駒を動かしてゴールの局面に変化させるというもので、まず将棋の駒の動きを覚えないと出来ません。パズルの存在を知った時は解答を得るためのプログラムを作ろうなんて思いませんでしたが、3三将棋アプリを作った直後なので、プログラムに必要な部品が全て揃っているので作ってみました。駒の動きを定義したPieceクラス(作成済み)駒の制御を行うBoardクラス(作成済み)盤面を多分木データとして格納するNodeクラス(今回作成)BFS(幅優先探索)で存在し得る全ての盤面を生成してNodeオブジェクトに追加15ピースパズルや迷路を解く時なんかは1、2は不要なので簡単ですが、将棋パズル解答プログラムを一から作るとなると結構大変です。今回は前回の記事で使用したソースを若干修正してそのまま利用出来ます。#{elapsed}ミリ秒"重複局面を除くことで答えの局面を探し出す際に最短手順であることが保証されます。223ミリ秒ゴールの局面からスタートの局面まで遡って表示されます。以前の記事にも書きましたが、BFS(幅優先探索)では局面を辿る順番が、一手目で現れ得る局面を全て辿った後に二手目の局面、二手目で現れ得る全ての局面を辿った後に三手目の局面と進んでいきますので、たとえ答えの局面に辿り着く経路が複数あったとしても答えに辿り着いた手順が最短経路であることが保証されます。答えに辿り着く手順が10手で完成する手順と15手で完成する手順があったとしても、BFSを使っている限り最短手数のものから見つかるからです。答えが見つかった時点で探索をやめればわざわざ多分木データを生成しなくてもいいのですが、せっかく全局面を探索してくれるので、このプログラムでは一旦全局面を保存してます。今回のNodeオブジェクトのような二つのメンバー変数を持つオブジェクトに全データを格納しておけば、いろいろな条件に当てはまる局面を探し出すのに便利で、最長手数を求めたりその手数で実現出来る局面を全てリストアップしたり出来ますので問題を作る時も便利です。問題を作る例えば以下のようなメソッドを追加してnode.recurCount(0)と呼び出せば、スタート局面から最短手順を選択した上で手数が最も長くなるのは何手かを求めることが出来ます。_counter先の例題のスタート局面から最も長い手数が必要となる局面は以下の局面で、必要な手数は9手です。最短手数=9手スタート局面から無駄に手数を伸ばすことなく最も手数がかかる局面をゴール局面とすれば難問が完成します。難問を作れるかTwitterでゴール局面まで60手掛かるという難問を見かけたので、問題を作る側の立場で考えてみました。全ての駒を適当に配置した問題を作って調べてみました。下の3パターンが上図をスタート局面とした場合の最長手数となる解答です。手順は省略しますが上の局面から下の3つの局面に駒を移動させるには最短手数でも25手必要で、上のスタート局面から出現し得る全ての局面のうち25手かかるのは下の局面3つだけのようです。手数を伸ばして実現することは可能ですが、最短手順を選んでも25手かかってしまうというところがミソです。ちなみにスタート画面の「歩」を「と金」に変えると最長手順は31手に伸びるようですが、長手順の難問を作るには適当に駒を配置するだけではダメなのかも知れません。3三将棋アプリを作った時に感じたのですが、「3三将棋(=9マス将棋)」だと適当に駒を配置するだけだと一目で正解が分かるような簡単な配置になってしまうことも多くて、熱戦が期待出来るような初期配置パターンを探すのに苦労しました。「将棋パズル」の場合も正解手順を見つけることより、長手順になる問題を見つける方が、問題を解くより難しいのかもしれません。用途」とかの検索ワードで来訪される人が偶にいるのですが、対戦ゲームに使用するとすればBFS(幅優先探索)の使い途は定跡データや学習データの格納・検索、DFS(深さ優先探索)の使い途は局面の先読み(MIN-MAX法を使った有利不利判定)ってことになるんじゃないでしょうか。進化する三目並べでも学習データの保存・検索にBFSを使用しています。3三将棋アプリでは簡単な初期配置は除いて、面白い対局になる初期配置を厳選しているつもりです。