fortran66のブログ

fortran について書きます。

eight queens

昔、PASCALの再帰を使った例題でよく出ていた eight queens 問題を解いてみます。

前回の整数並べ替えの列挙を変形して利用します。配列の i 番目の要素が i 列目での queen の存在する行を指していると解釈します。
すでに飛車道を消した形になっているので、角道を消すことを考えます。これは対角線方向に新しい駒を置かないようにすれば実現されます。

なお回転と鏡像も重複して数えることとします。

実行結果

n = 8 の場合。

個数を n = 15 まで計算してみました。

1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184

これはオンライン整数列辞典 http://oeis.org/A000170 の結果と一致しています。

ソース・プログラム

list1 はすでに確定した並び、list2 は list1 中の駒の飛車道を避けた、これから並べうる場所です。

module m_8
contains
  recursive subroutine eightq(list1, list2)
    integer, intent(in) :: list1(:), list2(:)
    integer :: i, ic = 0
    if (size(list2) == 0) then
      ic = ic + 1
      print '(i5, a, 25i3)', ic, ':', list1
    else
      do i = 1, size(list2)
        if ( notdiag(list1, list2(i)) ) call eightq( [list1, list2(i)], pack(list2, list2 /= list2(i)) )        
      end do
    end if
    return
  end subroutine eightq

  logical function notdiag(list, k)
    integer, intent(in) :: list(:), k
    if (size(list) == 0) then
      notdiag = .true.
    else
      notdiag = all( abs(list - k) /= [size(list):1:-1] ) !non-standard [(i, i = size(list), 1, -1)]
    end if
    return
  end function notdiag

end module m_8  

program $8queen
  use m_8
  call eightq([integer::], [1:8])
  stop
end program $8queen