読者です 読者をやめる 読者になる 読者になる

fortran66のブログ

fortran について書きます。

エイトクィーン問題ふたたび

エイトクィーンの解を配列の配列に保存するようにします。以前はI/Oで出力しておりました。
参照
2012-05-19 8クイーン http://d.hatena.ne.jp/fortran66/20120519
2012-12-19 配列の配列 http://d.hatena.ne.jp/fortran66/20121219

再帰を使うと簡潔に書けても実行時の負担が重くていまいちです。盤配置を返さず、可能な配置数だけを数えるようにした場合でも n=17 くらいで待ちきれない位の時間がかかります。

(参考:n=18 666090624 に数時間。寝る前に実行して明け方目を覚ましたら終わってた。)

実行結果

結果としては Deep Copy しているせいか時間がかかるようになった上に、n=13以上でトレースバックの出ない実行時エラーで死ぬようになりました。
配列の配列の初期化でサイズ0にするのに allocatable を使うしかないのが困りもの。

ソース・プログラム

module m_8
    implicit none 
    type :: t_list
      integer, allocatable :: i(:)
    end type t_list
  contains
    recursive subroutine eightq(list1, list2, lists)
      integer, intent(in) :: list1(:), list2(:)
      type(t_list), allocatable, intent(in out) :: lists(:)
      integer :: i
      type(t_list), allocatable :: tmp(:)
      if (size(list2) == 0) then
        tmp = [lists, t_list(list1)]   ! deep copy
        call move_alloc(tmp, lists)
      else
        do i = 1, size(list2)
          if ( notdiag(list1, list2(i)) ) call eightq( [list1, list2(i)], pack(list2, list2 /= list2(i)), lists )        
        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 EightQueen
    use m_8
    implicit none
    type(t_list), allocatable :: lists(:)
    integer :: i, n8
    do n8 = 1, 10
      allocate( lists(0) )
      call eightq([integer::], [1:n8], lists)
      print '(a, i3, a, i10)', 'board size =', n8, ' possible solutions =', size(lists)
      do i = 1, size(lists)
        print '(i5, a, 25i3)', i, ':', lists(i)%i
      end do
      deallocate(lists)
    end do
    stop
  end program EightQueen