Python エイト・クイーン問題



何かの雑誌でエイト・クイーン問題が取り上げられていました。

「総当りした場合と、適切に枝刈りした場合では実装速度に
大きな差が出る。アルゴリズムは適切に選択しましょう。」
という内容だったかと思います。

どの程度差がでるのか試してみたときのメモです。


#総当りロジック
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import time, copy

#縦・横・斜で重複が存在しないかチェックする
def check8q(q):
  ans = copy.copy(q)
  
  while(True):
    target = q[0]
    del(q[0])
    
    #横方向に重複があるか確認
    if target in q:
      return
    
    #斜めに重複があるか確認
    for i, t in enumerate(q):
      if target + (i + 1) == t or target - (i + 1) == t:
        return
    
    #キューがなくなるまで確認できれば正当
    if len(q) == 0:
      #結果を出力
      print ans
      break

if __name__ == '__main__':

  #総当り
  t1 = time.time()

  #8重ループ
  for i1 in range(8):
    for i2 in range(8):
      for i3 in range(8):
        for i4 in range(8):
          for i5 in range(8):
            for i6 in range(8):
              for i7 in range(8):
                for i8 in range(8):
                  check8q([i1,i2,i3,i4,i5,i6,i7,i8])

  t2 = time.time()
  print t2 - t1,'sec'


#枝刈りロジック
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import time

def check8q(q):
  
  #配置する要素が存在するか
  if -1 in q:
    #配置する要素のインデックスを取得
    index = q.index(-1)
    
    for i in range(8):
      #配置しようとする要素がリストに存在する場合は、
      #処理スキップ
      if i in q:
        continue
      
      #斜めに重複が存在する場合は処理スキップ
      isbreak = False
      for j in range(index):
        if i - (index - j) == q[j] or i + (index - j) == q[j]:
          isbreak = True
          break
      
      if isbreak:
        continue
      
      #インデックスに検証を通過した要素を追加し再帰
      q[index] = i
      check8q(q)
      #print 'cas', q
      
    q[index] = -1
  
  #追加できる要素なし
  else:
    #妥当な配置である
    print q

if __name__ == '__main__':

  #枝刈り
  t1 = time.time()
  
  check8q([-1] * 8)
  
  t2 = time.time()
  print t2 - t1,'sec'



実行速度は
総当り:80.379999876 sec
枝刈り:0.0940001010895 sec


80秒の処理が0.09秒に短縮です。


アルゴリズムの選定って重要ですね・・・


もどる