昔、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