応用情報技術者 試験情報＆徹底解説

Nクイーン問題に関する次の記述を読んで，設問1～3に答えよ。

　Nクイーン問題とは，N×Nマスの盤上で互いの利き筋に当たらないようなN個のクイーンの配置を見つける問題である。クイーンは，縦・横・斜めのいずれか一方向にどこまでも移動することができ，一度に移動できる範囲をクイーンの利き筋という。8×8マスの盤上の行5列6に配置したクイーンの利き筋を，図1に示す。また，8×8マスの場合のNクイーン問題の解の一つを図2に示す。
　なお，Nクイーン問題の解は存在しないこともあるし，複数存在することもある。　Nクイーン問題に対し，空の盤上にクイーンを配置し，その配置したクイーンの利き筋に当たらない位置を探索しながら，行順にクイーンを配置するという，次のような解法を考えた。

〔Nクイーン問題の解法〕

• 1行目において，1列目にクイーンを配置する。次にこの1行目のクイーンの利き筋に当たらない2行目の列を1列目から順に探索し，クイーンを配置する。同様に次の行以降も，既に配置したクイーンの利き筋に当たらない列を探索し，クイーンを配置する。
• N行目までクイーンが配置できた場合は，解の一つが見つかったとして終了する。
• ある行でクイーンが配置できる列が見つからなかった場合は，一つ前の行に戻り，その行のクイーンを取り除く。取り除いたクイーンの次の列以降で，クイーンが配置できる列を探索する。それでも列が見つからなかった場合は，更に前の行に戻り，同様に繰り返す。
• 1行目においてもクイーンが配置できる列がなくなった場合は，このNクイーン問題の解はないということで終了する。

〔利き筋の判定〕
　行 i 列 k のマスが既に配置したクイーンの利き筋に当たるか否かを容易に判別できるよう，盤面の利き筋の方向別に配列 col(列方向)，upwd(斜め上方向)及び downwd(斜め下方向)を用意した(図3～5)。解法では，一つの行には一つしかクイーンが配置されないので，行方向の判別は行う必要がない。
　各配列の要素の値は，その方向にまだクイーンが配置されていないとき FREE となり，既に配置されているとき NOT_FREE となる。各要素の初期値は FREE である。図3～5の矢印の先の番号は，各配列の添字に対応する。N×Nマスの場合，配列 col の大きさはNであり，upwd と downwd の大きさはともにアである。　例えば，図6のように8×8マスの盤上の行 1 列 1 と行 2 列 3 のマスにクイーンを配置した場合は，col[1]，col[3]，upwd[1]，upwd[4]，downwd[7] 及び downwd[8]の値がNOT_FREEとなる。一般にN×Nマスの盤上の行 i 列 k のマスにクイーンを配置した場合は，col[k]，upwd[i＋k－1] 及び downwd[イ]の 値がNOT_FREEとなる。〔Nクイーン問題の解法のプログラム〕
　i 行目以降についてクイーンの配置の仕方を探索する再帰関数 search のプログラムを図7に，メインプログラムを図8に示す。　関数 search は i 行目以降のクイーンの配置の仕方が見つかった場合に SUCCESS を，見つからなかった場合に FAILURE を戻す。
　配列 pos は，行番号を添字とし，その行に配置したクイーンの位置(列番号)を値とする。配置されていない場合の値は 0 である。

N×Nマスの場合，本文中のアに入れる適切な字句を答えよ。

N×Nマスの場合，本文及び図7中のイに入れる適切な字句を答えよ。

〔Nクイーン問題の解法のプログラム〕について，(1)～(3)に答えよ。

• 図7中のウ～キに入れる適切な字句を答えよ。
• 図8中のクに入れる適切な字句を答えよ。
• 4×4マスの場合，このプログラムによる解を図9に示す。この結果が得られるまでに，図7中の①の部分は何回実行されるか答えよ。