Nクイーン問題(48)第七章 シングルスレッド Python編


【参考リンク】Nクイーン問題 過去記事一覧はこちらから

エイト・クイーンのソース置き場 BashもJavaもPythonも!

シングルスレッド

マルチスレッドを作成する前にシングルスレッドを作ってみます。
「今までのも考えようによってはシングルスレッドだ」
というばかちんがいそうですが、全然違います。
シングルスレッドの構造になって初めてマルチスレッドに展開できるわけで、通常の処理とシングルスレッドは異なります。

シングルスレッドの実装

前回やっておけばよかったのですが、pres_apres_bを母体クラスのグローバルへ移行します。
というのも、チェーンを初期化してビルドするまでしか使わないので、いつまでもBoardクラスにあっても意味ないですから。

シングルスレッド移行への段取り

1.ソース冒頭に以下を追加しておきます。

import logging
import threading
from threading import Thread

2.nQueensクラスの引数にThreadを追加
これでnQueensクラスはThreadクラスを「継承した」ということになります。

#
# nQueens メインスレッドクラス
class nQueens(Thread): # pylint:disable=RO902
  #

3.Threadクラスを継承したnQueensクラスに run()を追加
Threadにはもともとrun()があります。
nQueensクラスにrun()を追加するというのは、元々あるrun()をオーバーライド(上書き)するという意味です。
JavaやPythonでは「Threadクラスのrun()メソッドをオーバーライドする」と言います。

  #
  # シングルスレッド
  def run(self):
    if self.child is None:
      self.buildChain()  # チェーンのビルド
  #

4.main()にスレッドを作成
Threadを継承したnQueensクラスをnqでインスタンスします。
その後、nq.carryChain()で処理を開始し、nq.start()run()の処理を開始します。
run()は一度しか実行されません。ぐるぐる回転するわけではありません。
最後に、それぞれの処理がすべて終わるまで待機してくれるnq.join()を実行します。

メインクラスにて親スレッドを作成して実行
    start_time = datetime.now()
    nq=nQueens(size)
    nq.carryChain()
    nq.start()
    nq.join()
    time_elapsed = datetime.now() - start_time

ソースコード

#!/usr/bin/env python3

# -*- coding: utf-8 -*-
import numpy as np
import copy
from datetime import datetime
import logging
import threading
from threading import Thread

"""
シングルスレッド対応版 Nクイーン

pres_a/pres_b/BはnQueensクラスのグローバルへ移行
nQueensクラスの引数にThread
nQueensクラスに`run()`を追加してスレッド時の関数を準備
メインクラスにて親スレッドを作成して実行
    start_time = datetime.now()
    nq=nQueens(size)
    nq.carryChain()
    nq.start()
    nq.join()
    time_elapsed = datetime.now() - start_time


詳細はこちら。
【参考リンク】Nクイーン問題 過去記事一覧はこちらから
https://suzukiiichiro.github.io/search/?keyword=Nクイーン問題

エイト・クイーンのプログラムアーカイブ
Bash、Lua、C、Java、Python、CUDAまで!
https://github.com/suzukiiichiro/N-Queens

# 実行 
$ python <filename.py>

# 実行結果
キャリーチェーン シングルスレッド
 N:        Total       Unique        hh:mm:ss.ms
 5:           10            2         0:00:00.002
 6:            4            1         0:00:00.010
 7:           40            6         0:00:00.044
 8:           92           12         0:00:00.204
 9:          352           46         0:00:00.885
10:          724           92         0:00:03.527
11:         2680          341         0:00:12.188
12:        14200         1788         0:00:37.435
"""
#
# Board ボードクラス
class Board:
  def __init__(self,size):
    self.size=size
    self.row=0
    self.left=0
    self.down=0
    self.right=0
    self.X=[-1 for i in range(size)]
#
# nQueens メインスレッドクラス
class nQueens(Thread): # pylint:disable=RO902
  #
  # 初期化
  def __init__(self,size): # pylint:disable=R0913
    super(nQueens,self).__init__()
    self.size=size
    self.COUNTER=[0]*3
    self.pres_a=[0]*930
    self.pres_b=[0]*930
    self.B=Board(size)
    self.child=None
  #
  # ユニーク数の集計
  def getUnique(self):
    return self.COUNTER[0]+self.COUNTER[1]+self.COUNTER[2]
  #
  # 合計解の集計
  def getTotal(self):
    return self.COUNTER[0]*2+self.COUNTER[1]*4+self.COUNTER[2]*8
  #
  # カウンター セッター
  def setCount(self,sym,count):
    self.COUNTER[sym]+=count
  #
  # ボード外側2列を除く内側のクイーン配置処理
  def solve(self,row,left,down,right):
    total=0
    if not down+1:
      return 1
    while row&1:
      row>>=1
      left<<=1
      right>>=1
    row>>=1           # 1行下に移動する
    bitmap=~(left|down|right)
    while bitmap!=0:
      bit=-bitmap&bitmap
      total+=self.solve(row,(left|bit)<<1,down|bit,(right|bit)>>1)
      bitmap^=bit
    return total
  #
  # キャリーチェーン solve()を呼び出して再起を開始する
  def process(self,sym):
    self.setCount(sym,self.solve(self.B.row>>2,self.B.left>>4,((((self.B.down>>2)|(~0<<(self.size-4)))+1)<<(self.size-5))-1,(self.B.right>>4)<<(self.size-5)))
  #
  # キャリーチェーン 対象解除
  def carryChainSymmetry(self,n,w,s,e):
    # n,e,s=(N-2)*(N-1)-1-w の場合は最小値を確認する。
    ww=(self.size-2)*(self.size-1)-1-w
    w2=(self.size-2)*(self.size-1)-1
    # 対角線上の反転が小さいかどうか確認する
    if s==ww and n<(w2-e): return 
    # 垂直方向の中心に対する反転が小さいかを確認
    if e==ww and n>(w2-n): return
    # 斜め下方向への反転が小さいかをチェックする
    if n==ww and e>(w2-s): return
    # 【枝刈り】1行目が角の場合
    # 1.回転対称チェックせずにCOUNT8にする
    if not self.B.X[0]:
      self.process(2) # COUNT8
      return
    # n,e,s==w の場合は最小値を確認する。
    # : '右回転で同じ場合は、
    # w=n=e=sでなければ値が小さいのでskip
    # w=n=e=sであれば90度回転で同じ可能性 ';
    if s==w:
      if n!=w or e!=w: return
      self.process(0) # COUNT2
      return
    # : 'e==wは180度回転して同じ
    # 180度回転して同じ時n>=sの時はsmaller?  ';
    if e==w and n>=s:
      if n>s: return
      self.process(1) # COUNT4
      return
    self.process(2)   # COUNT8
    return
  #
  # キャリーチェーン 効きのチェック dimxは行 dimyは列
  def placement(self,dimx,dimy):
    if self.B.X[dimx]==dimy:
      return 1
    if self.B.X[0]:
      if self.B.X[0]!=-1:
        if((dimx<self.B.X[0] or dimx>=self.size-self.B.X[0]) and 
          (dimy==0 or dimy==self.size-1)): return 0
        if((dimx==self.size-1) and 
          (dimy<=self.B.X[0] or dimy>=self.size-self.B.X[0])):return 0
    else:
      if self.B.X[1]!=-1:
        if self.B.X[1]>=dimx and dimy==1: return 0
    if( (self.B.row & 1<<dimx) or 
        (self.B.left & 1<<(self.size-1-dimx+dimy)) or
        (self.B.down & 1<<dimy) or
        (self.B.right & 1<<(dimx+dimy))): return 0
    self.B.row|=1<<dimx
    self.B.left|=1<<(self.size-1-dimx+dimy)
    self.B.down|=1<<dimy
    self.B.right|=1<<(dimx+dimy)
    self.B.X[dimx]=dimy
    return 1
  #
  # チェーンのビルド
  def buildChain(self):
    wB=copy.deepcopy(self.B)
    for w in range( (self.size//2)*(self.size-3) +1):
      self.B=copy.deepcopy(wB)
      # 1.0行目と1行目にクイーンを配置
      if self.placement(0,self.pres_a[w])==0:
        continue
      if self.placement(1,self.pres_b[w])==0:
        continue
      # 2.90度回転
      nB=copy.deepcopy(self.B)
      mirror=(self.size-2)*(self.size-1)-w
      for n in range(w,mirror,1):
        self.B=copy.deepcopy(nB)
        if self.placement(self.pres_a[n],self.size-1)==0:
          continue
        if self.placement(self.pres_b[n],self.size-2)==0:
          continue
        # 3.90度回転
        eB=copy.deepcopy(self.B)
        for e in range(w,mirror,1):
          self.B=copy.deepcopy(eB)
          if self.placement(self.size-1,self.size-1-self.pres_a[e])==0:
            continue
          if self.placement(self.size-2,self.size-1-self.pres_b[e])==0:
            continue
          # 4.90度回転
          sB=copy.deepcopy(self.B)
          for s in range(w,mirror,1):
            self.B=copy.deepcopy(sB)
            if self.placement(self.size-1-self.pres_a[s],0)==0:
              continue
            if self.placement(self.size-1-self.pres_b[s],1)==0:
              continue
            # 対象解除法
            self.carryChainSymmetry(n,w,s,e)
  #
  # チェーンの初期化
  def initChain(self):
    idx=0
    for a in range(self.size):
      for b in range(self.size):
        if (a>=b and (a-b)<=1) or (b>a and (b-a<=1)):
          continue
        self.pres_a[idx]=a
        self.pres_b[idx]=b
        idx+=1
  #
  # シングルスレッド
  def run(self):
    if self.child is None:
      self.buildChain()  # チェーンのビルド
  #
  # キャリーチェーン
  def carryChain(self):
    self.initChain()     # チェーンの初期化
#
# メイン
def main():
  nmin = 5
  nmax = 21
  print("キャリーチェーン シングルスレッド")
  print(" N:        Total       Unique        hh:mm:ss.ms")
  for size in range(nmin, nmax,1):
    start_time = datetime.now()
    nq=nQueens(size)
    nq.carryChain()
    nq.start()
    nq.join()
    time_elapsed = datetime.now() - start_time
    _text = '{}'.format(time_elapsed)
    text = _text[:-3]
    print("%2d:%13d%13d%20s" % (size, nq.getTotal(),nq.getUnique(),text))  # 出力
#
main()
#

実行結果

キャリーチェーン シングルスレッド
 N:        Total       Unique        hh:mm:ss.ms
 5:           10            2         0:00:00.002
 6:            4            1         0:00:00.010
 7:           40            6         0:00:00.044
 8:           92           12         0:00:00.204
 9:          352           46         0:00:00.885
10:          724           92         0:00:03.527
11:         2680          341         0:00:12.188
12:        14200         1788         0:00:37.435

参考リンク

以下の詳細説明を参考にしてください。
【参考リンク】Nクイーン問題 過去記事一覧
【Github】エイト・クイーンのソース置き場 BashもJavaもPythonも!

Nクイーン問題(50)第七章 マルチプロセス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-04-n-queens-suzuki/
Nクイーン問題(49)第七章 マルチスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-03-n-queens-suzuki/
Nクイーン問題(48)第七章 シングルスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-02-n-queens-suzuki/
Nクイーン問題(47)第七章 クラス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-01-n-queens-suzuki/
Nクイーン問題(46)第七章 ステップNの実装 Python編
https://suzukiiichiro.github.io/posts/2023-06-16-02-n-queens-suzuki/
Nクイーン問題(45)第七章 キャリーチェーン Python編
https://suzukiiichiro.github.io/posts/2023-06-16-01-n-queens-suzuki/
Nクイーン問題(44)第七章 対象解除法 Python編
https://suzukiiichiro.github.io/posts/2023-06-14-02-n-queens-suzuki/
Nクイーン問題(43)第七章 ミラー Python編
https://suzukiiichiro.github.io/posts/2023-06-14-01-n-queens-suzuki/
Nクイーン問題(42)第七章 ビットマップ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-05-n-queens-suzuki/
Nクイーン問題(41)第七章 配置フラグ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-04-n-queens-suzuki/
Nクイーン問題(40)第七章 バックトラック Python編
https://suzukiiichiro.github.io/posts/2023-06-13-03-n-queens-suzuki/
Nクイーン問題(39)第七章 バックトラック準備編 Python編
https://suzukiiichiro.github.io/posts/2023-06-13-02-n-queens-suzuki/
Nクイーン問題(38)第七章 ブルートフォース Python編
https://suzukiiichiro.github.io/posts/2023-06-13-01-n-queens-suzuki/
Nクイーン問題(37)第六章 C言語移植 その17 pthread並列処理完成
https://suzukiiichiro.github.io/posts/2023-05-30-17-n-queens-suzuki/
Nクイーン問題(36)第六章 C言語移植 その16 pthreadの実装
https://suzukiiichiro.github.io/posts/2023-05-30-16-n-queens-suzuki/
Nクイーン問題(35)第六章 C言語移植 その15 pthread実装直前版完成
https://suzukiiichiro.github.io/posts/2023-05-30-15-n-queens-suzuki/
Nクイーン問題(34)第六章 C言語移植 その14
https://suzukiiichiro.github.io/posts/2023-05-30-14-n-queens-suzuki/
Nクイーン問題(33)第六章 C言語移植 その13
https://suzukiiichiro.github.io/posts/2023-05-30-13-n-queens-suzuki/
Nクイーン問題(32)第六章 C言語移植 その12
https://suzukiiichiro.github.io/posts/2023-05-30-12-n-queens-suzuki/
Nクイーン問題(31)第六章 C言語移植 その11
https://suzukiiichiro.github.io/posts/2023-05-30-11-n-queens-suzuki/
Nクイーン問題(30)第六章 C言語移植 その10
https://suzukiiichiro.github.io/posts/2023-05-30-10-n-queens-suzuki/
Nクイーン問題(29)第六章 C言語移植 その9
https://suzukiiichiro.github.io/posts/2023-05-30-09-n-queens-suzuki/
Nクイーン問題(28)第六章 C言語移植 その8
https://suzukiiichiro.github.io/posts/2023-05-30-08-n-queens-suzuki/
Nクイーン問題(27)第六章 C言語移植 その7
https://suzukiiichiro.github.io/posts/2023-05-30-07-n-queens-suzuki/
Nクイーン問題(26)第六章 C言語移植 その6
https://suzukiiichiro.github.io/posts/2023-05-30-06-n-queens-suzuki/
Nクイーン問題(25)第六章 C言語移植 その5
https://suzukiiichiro.github.io/posts/2023-05-30-05-n-queens-suzuki/
Nクイーン問題(24)第六章 C言語移植 その4
https://suzukiiichiro.github.io/posts/2023-05-30-04-n-queens-suzuki/
Nクイーン問題(23)第六章 C言語移植 その3
https://suzukiiichiro.github.io/posts/2023-05-30-03-n-queens-suzuki/
Nクイーン問題(22)第六章 C言語移植 その2
https://suzukiiichiro.github.io/posts/2023-05-30-02-n-queens-suzuki/
Nクイーン問題(21)第六章 C言語移植 その1
N-Queens問://suzukiiichiro.github.io/posts/2023-05-30-01-n-queens-suzuki/
Nクイーン問題(20)第五章 並列処理
https://suzukiiichiro.github.io/posts/2023-05-23-02-n-queens-suzuki/
Nクイーン問題(19)第五章 キャリーチェーン
https://suzukiiichiro.github.io/posts/2023-05-23-01-n-queens-suzuki/
Nクイーン問題(18)第四章 エイト・クイーンノスタルジー
https://suzukiiichiro.github.io/posts/2023-04-25-01-n-queens-suzuki/
Nクイーン問題(17)第四章 偉人のソースを読む「N24を発見 Jeff Somers」
https://suzukiiichiro.github.io/posts/2023-04-21-01-n-queens-suzuki/
Nクイーン問題(16)第三章 対象解除法 ソース解説
https://suzukiiichiro.github.io/posts/2023-04-18-01-n-queens-suzuki/
Nクイーン問題(15)第三章 対象解除法 ロジック解説
https://suzukiiichiro.github.io/posts/2023-04-13-02-nqueens-suzuki/
Nクイーン問題(14)第三章 ミラー
https://suzukiiichiro.github.io/posts/2023-04-13-01-nqueens-suzuki/
Nクイーン問題(13)第三章 ビットマップ
https://suzukiiichiro.github.io/posts/2023-04-05-01-nqueens-suzuki/
Nクイーン問題(12)第二章 まとめ
https://suzukiiichiro.github.io/posts/2023-03-17-02-n-queens-suzuki/
Nクイーン問題(11)第二章 配置フラグの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-17-01-n-queens-suzuki/
Nクイーン問題(10)第二章 バックトラックの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-16-01-n-queens-suzuki/
Nクイーン問題(9)第二章 ブルートフォースの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-14-01-n-queens-suzuki/
Nクイーン問題(8)第一章 まとめ
https://suzukiiichiro.github.io/posts/2023-03-09-01-n-queens-suzuki/
Nクイーン問題(7)第一章 ブルートフォース再び
https://suzukiiichiro.github.io/posts/2023-03-08-01-n-queens-suzuki/
Nクイーン問題(6)第一章 配置フラグ
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
Nクイーン問題(5)第一章 進捗表示テーブルの作成
https://suzukiiichiro.github.io/posts/2023-03-06-01-n-queens-suzuki/
Nクイーン問題(4)第一章 バックトラック
https://suzukiiichiro.github.io/posts/2023-02-21-01-n-queens-suzuki/
Nクイーン問題(3)第一章 バックトラック準備編
https://suzukiiichiro.github.io/posts/2023-02-14-03-n-queens-suzuki/
Nクイーン問題(2)第一章 ブルートフォース
https://suzukiiichiro.github.io/posts/2023-02-14-02-n-queens-suzuki/
Nクイーン問題(1)第一章 エイトクイーンについて
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/

書籍の紹介

Nクイーン問題(49)第七章 マルチスレッド Python編

Nクイーン問題(49)第七章 マルチスレッド Python編

Nクイーン問題(47)第七章 クラス Python編

Nクイーン問題(47)第七章 クラス Python編