2012年 秋期 応用情報技術者試験 問2

Nクイーン問題に関するプログラミング

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の大きさはともにアである。

[図3-5の図が示されている：列方向の配列、斜め上方向の配列、斜め下方向の配列を示す図]

例えば，図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となる。

[図6のクイーンの配置と利き筋の例（8×8マスの場合）が示されている]

[Nクイーン問題の解法のプログラム]

i行目以降についてクイーンの配置の仕方を探索する再帰関数searchのプログラムを図7に，メインプログラムを図8に示す。

関数searchはi行目以降のクイーンの配置の仕方が見つかった場合にSUCCESSを，見つからなかった場合にFAILUREを戻す。

配列posは，行番号を添字とし，その行に配置したクイーンの位置（列番号）を値とする。配置されていない場合の値は0である。

function search(i)
  for ( ウ を エ から オ まで1ずつ増やす )
    if ( col[k]とupwd[i+k-1]とdownwd[イ]が全てFREEと等しい ) then
      // クイーンを配置する
      カ
      col[k] ← NOT_FREE
      upwd[i+k-1] ← NOT_FREE
      downwd[イ] ← NOT_FREE
      if ( iとNが等しい ) then
        return SUCCESS
      else
        if ( search( キ ) とSUCCESSが等しい ) then
          return SUCCESS
        else
          // クイーンを取り除く
          pos[i] ← 0
          col[k] ← FREE
          upwd[i+k-1] ← FREE
          downwd[イ] ← FREE
        endif
      endif
    endif
  endfor
  // クイーンが配置できる列が見つからなかった
  return FAILURE
endfunction

// メインプログラム
配列posを初期化する
配列col，upwd及びdownwdを初期化する
if ( search( ク ) とSUCCESSが等しい ) then
  解となるクイーンの配置を印字する
else
  "解が見つからなかった"と印字する
endif