Ｎクイーン問題（４４）第七章　対象解除法 Python編

  TOTAL=UNIQUE=COUNT2=COUNT4=COUNT8=0

mask=(1<<size)-1
    +-+-+-+-+-+  
    |M|M|M|M|M|  mask=(1<<size)-1
    +-+-+-+-+-+  $(( (1<<5)-1 )):31
    | | | | | |  $(( 2#11111 )) 
    +-+-+-+-+-+  $ 31
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

$ echo $(( 2#11111 ))
$ 31

  TOPBIT=1<<(size-1)
    +-+-+-+-+-+  
    |T| | | | |  TOPBIT=1<<(size-1)
    +-+-+-+-+-+  $(( (1<<(5-1) )):16 
    | | | | | |  $(( 2#10000 )) 
    +-+-+-+-+-+  $ 16 
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

ENDBIT=LASTMASK=SIDEMASK=0

  ENDBIT=LASTMASK=SIDEMASK=0
    ０は何も置かない（なにもはじまってない）
    +-+-+-+-+-+  
    |T|E| | | |  0#01000
    +-+-+-+-+-+  
    | | | | | | 
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

  BOUND1=2
  BOUND2=0

  board[0]=1       # Qを右上角に配置

      bit=1<<BOUND1

       Ｎ５の場合、BOUND1は２と３になる
        1<<BOUND1  ２行目は真ん中に置く
        +-+-+-+-+-+  
        | | | | |Q|  1#00001
        +-+-+-+-+-+  
        | | |B| | |  BOUND1=2 4#00100
        +-+-+-+-+-+  $(( 1<<2 ))
        | | | | | |  $ 4
        +-+-+-+-+-+  1->2->4               
        | | | | | | 
        +-+-+-+-+-+ 
        | | | | | |      
        +-+-+-+-+-+  

        1<<BOUND1    ２行目は真ん中の次に置く
        +-+-+-+-+-+  
        | | | | |Q|  1#00001
        +-+-+-+-+-+  
        | |B| | | |  BOUND1=3 8#01000
        +-+-+-+-+-+  $(( 1<<3 ))
        | | | | | |  $ 8
        +-+-+-+-+-+  1->2->4->8             
        | | | | | | 
        +-+-+-+-+-+ 
        | | | | | |      
        +-+-+-+-+-+  

  TOPBIT=1<<(size-1)
    +-+-+-+-+-+  
    |T| | | | | TOPBIT=1<<(size-1)
    +-+-+-+-+-+ $(( 2#10000 )) 
    | | | | | | $ 16 
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

  ENDBIT=TOPBIT>>1
    +-+-+-+-+-+  
    |T|E| | | | ENDBIT=TOPBIT>>1
    +-+-+-+-+-+ $(( 2#01000 )) 
    | | | | | | $ 8
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

  SIDEMASK=TOPBIT|1
    +-+-+-+-+-+  
    |S| | | |S| SIDEMASK=TOPBIT|1
    +-+-+-+-+-+ $(( 2#10001 )) 
    | | | | | | $ 17
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

  LASTMASK=TOPBIT|1
    +-+-+-+-+-+  
    |L| | | |L| LASTMASK=TOPBIT|1
    +-+-+-+-+-+ $(( 2#10001 )) 
    | | | | | | $ 17
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

  LASTMASK=$(( TOPBIT|1 )); 
    +-+-+-+-+-+  
    | | | | | | LASTMASK=$(( TOPBIT|1 ))
    +-+-+-+-+-+ $(( 2#10001 )) 
    | | | | | | $ 17
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    |L| | | |L|      
    +-+-+-+-+-+  

    ENDBIT=ENDBIT>>1
      +-+-+-+-+-+  
      |T|E| | | | ENDBIT=TOPBIT>>1
      +-+-+-+-+-+ $(( 2#01000 )) 
      | | | | | | $ 8
      +-+-+-+-+-+  
      | | | | | |       
      +-+-+-+-+-+             
      | | | | | | 
      +-+-+-+-+-+ 
      | | | | | |      
      +-+-+-+-+-+  
           ↓
      +-+-+-+-+-+  
      |T| |E| | | ENDBIT=ENDBIT>>1
      +-+-+-+-+-+ $(( 2#00100 )) 
      | | | | | | $ 4
      +-+-+-+-+-+  
      | | | | | |       
      +-+-+-+-+-+             
      | | | | | | 
      +-+-+-+-+-+ 
      | | | | | |      
      +-+-+-+-+-+  

    +-+-+-+-+-+  
    |L|L| |L|L| LASTMASK=LASTMASK<<1 | LASTMASK | LASTMASK>>1
    +-+-+-+-+-+ $(( 2#11011 )) 
    | | | | | | $ 27
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    | | | | | |      
    +-+-+-+-+-+  

    +-+-+-+-+-+  
    | | | | | | LASTMASK=LASTMASK<<1 | LASTMASK | LASTMASK>>1
    +-+-+-+-+-+ $(( 2#11011 )) 
    | | | | | | $ 27
    +-+-+-+-+-+  
    | | | | | |       
    +-+-+-+-+-+             
    | | | | | | 
    +-+-+-+-+-+ 
    |L|L| |L|L|      
    +-+-+-+-+-+  

  """
  １．クイーンが右上角にある場合、ユニーク解が属する
  グループの要素数は必ず８個(＝２×４)
  """
  if row==(size-1):
    if bitmap :
      board[row]=bitmap
      if DISPLAY :
        printRecord_bitmap(size,1)
      COUNT8+=1

  else:
    if row<BOUND1:    # 枝刈り
      bitmap=bitmap|2
      bitmap=bitmap^2
    while bitmap:
    """
    上から２行目のクイーンの位置が左から何番目にあるかと、
    右から２列目のクイーンの位置が上から何番目にあるかを、
    比較するだけで判定します。
    具体的には、２行目と２列目の位置を数値とみなし、
    ２行目＜２列目という条件を課せばよい
    結論： 以下の図では、１，２，４を枝刈りを入れる
      
      +-+-+-+-+-+  
      | | | |X|Q| 
      +-+-+-+-+-+  
      | |Q| |X| |  8（左から数えて１，２，４，８）
      +-+-+-+-+-+  
      | | | |X| |       
      +-+-+-+-+-+             
      | | | |Q| |  8（上から数えて１，２，４，８） 
      +-+-+-+-+-+ 
      | | | | | |      
      +-+-+-+-+-+  
    """

      bitmap=bitmap|2
      bitmap=bitmap^2

    else                            # Qが角にない
      : '
      オリジナルがユニーク解であるためには先ず、
      前提：symmetryOpsは回転・鏡像変換により得られる状態の
      ユニーク値を比較し最小のものだけがユニーク解となるようにしている。
      Qができるだけ右に置かれている方がユニーク値は小さい。
      例えば1行目の2列目にQが置かれている方が3列目に置かれているより
      ユニーク値は小さくユニーク解に近い。
      1行目のクイーンの位置が同じなら2行目のクイーンの位置がより右の
      列におかれているものがユニーク値は小さくユニーク解に近い。

      下図の X への配置は禁止されます。
      Qの位置より右位置の８対象位置（X）にクイーンを置くことはできない。
      置いた場合回転・鏡像変換したユニーク値が最小にならなくなり、symmetryOps
      で負けるので枝刈りをする


      1行目のクイーンが3列目に置かれている場合
      +-+-+-+-+-+-+-+-+  
      |X|X| | | |Q|X|X| 
      +-+-+-+-+-+-+-+-+  
      |X| | | | | | |X| 
      +-+-+-+-+-+-+-+-+  
      | | | | | | | | |       
      +-+-+-+-+-+-+-+-+             
      | | | | | | | | | 
      +-+-+-+-+-+-+-+-+ 
      | | | | | | | | |      
      +-+-+-+-+-+-+-+-+  
      | | | | | | | | |
      +-+-+-+-+-+-+-+-+
      |X| | | | | | |X|
      +-+-+-+-+-+-+-+-+
      |X|X| | | | |X|X|
      +-+-+-+-+-+-+-+-+

      1行目のクイーンが4列目に置かれている場合
      +-+-+-+-+-+-+-+-+  
      |X|X|X| |Q|X|X|X| 
      +-+-+-+-+-+-+-+-+  
      |X| | | | | | |X| 
      +-+-+-+-+-+-+-+-+  
      |X| | | | | | |X|       
      +-+-+-+-+-+-+-+-+             
      | | | | | | | | | 
      +-+-+-+-+-+-+-+-+ 
      | | | | | | | | |      
      +-+-+-+-+-+-+-+-+  
      |X| | | | | | |X|
      +-+-+-+-+-+-+-+-+
      |X| | | | | | |X|
      +-+-+-+-+-+-+-+-+
      |X|X|X| | |X|X|X|
      +-+-+-+-+-+-+-+-+

      プログラムではこの枝刈を上部サイド枝刈り、下部サイド枝刈り、最下段枝刈り
      の3か所で行っている
      それぞれ、1,2,3の数字で表すと以下の通り

      1行目のクイーンが3列目に置かれている場合
      +-+-+-+-+-+-+-+-+  
      |X|X| | | |Q|X|X| 
      +-+-+-+-+-+-+-+-+  
      |1| | | | | | |1| 
      +-+-+-+-+-+-+-+-+  
      | | | | | | | | |       
      +-+-+-+-+-+-+-+-+             
      | | | | | | | | | 
      +-+-+-+-+-+-+-+-+ 
      | | | | | | | | |      
      +-+-+-+-+-+-+-+-+  
      | | | | | | | | |
      +-+-+-+-+-+-+-+-+
      |2| | | | | | |2|
      +-+-+-+-+-+-+-+-+
      |2|3| | | | |3|2|
      +-+-+-+-+-+-+-+-+
      1行目にXが残っているが当然Qの効き筋なので枝刈する必要はない
      ';
    if row<BOUND1:          # 上部サイド枝刈り
      bitmap=bitmap|SIDEMASK
      bitmap=bitmap^SIDEMASK
    else:
      if row==BOUND2:       # 下部サイド枝刈り
        if not down&SIDEMASK:
          return
        if down&SIDEMASK!=SIDEMASK:
          bitmap=bitmap&SIDEMASK

#!/usr/bin/env python3

# -*- coding: utf-8 -*-

"""
対象解除版 Ｎクイーン

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

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

# 実行 
$ python <filename.py>

# 実行結果
1
 0 2 4 1 3
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+

2
 0 3 1 4 2
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+

3
 1 3 0 2 4
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+

4
 1 4 2 0 3
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
|O| | | | |
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+

5
 2 4 3 1 4
+-+-+-+-+-+
| | |O| | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+
| | | |O| |
+-+-+-+-+-+
| |O| | | |
+-+-+-+-+-+
| | | | |O|
+-+-+-+-+-+

size: 5 TOTAL: 10 COUNT2: 5

"""

#
# グローバル変数
MAX=21                          # ボードサイズ最大値
TOTAL=0                         # 解
UNIQUE=0
COUNT2=0                        # ミラー
COUNT4=0
COUNT8=0
BOUND1=0
BOUND2=0
TOPBIT=0
ENDBIT=0
LASTMASK=0
SIDEMASK=0
board=[0 for i in range(MAX)]   # ボード配列格納用
down=[0 for i in range(MAX)]    # 効き筋チェック
left=[0 for i in range(MAX)]    # 効き筋チェック
right=[0 for i in range(MAX)]   # 効き筋チェック
#
# ビットマップ版ボードレイアウト出力
def printRecord_bitmap(size,flag):
  global TOTAL
  global board
  print(TOTAL)
  sEcho=""
  """
  ビットマップ版
     ビットマップ版からは、左から数えます
     上下反転左右対称なので、これまでの上から数える手法と
     rowを下にたどって左から数える方法と解の数に変わりはありません。
     0 2 4 1 3 
    +-+-+-+-+-+
    |O| | | | | 0
    +-+-+-+-+-+
    | | |O| | | 2
    +-+-+-+-+-+
    | | | | |O| 4
    +-+-+-+-+-+
    | |O| | | | 1
    +-+-+-+-+-+
    | | | |O| | 3
    +-+-+-+-+-+
  """
  if flag:
    for i in range(size):
      for j in range(size):
        if board[i]&1<<j:
          sEcho+=" " + str(j)
  else:
    """
    ビットマップ版以外
    (ブルートフォース、バックトラック、配置フラグ)
    上から数えます
       0 2 4 1 3 
      +-+-+-+-+-+
      |O| | | | |
      +-+-+-+-+-+
      | | | |O| |
      +-+-+-+-+-+
      | |O| | | |
      +-+-+-+-+-+
      | | | | |O|
      +-+-+-+-+-+
      | | |O| | |
      +-+-+-+-+-+
    """
    for i in range(size):
      sEcho+=" " + str(board[i])
  print(sEcho)

  print ("+",end="")
  for i in range(size):
    print("-",end="")
    if i<(size-1):
      print("+",end="")
  print("+")
  for i in range(size):
    print("|",end="")
    for j in range(size):
      if flag:
        if board[i]&1<<j:
          print("O",end="")
        else:
          print(" ",end="")
      else:
        if i==board[j]:
          print("O",end="")
        else:
          print(" ",end="")
      if j<(size-1):
        print("|",end="")
    print("|")
    if i in range(size-1):
      print("+",end="")
      for j in range(size):
        print("-",end="")
        if j<(size-1):
          print("+",end="")
      print("+")
  print("+",end="")
  for i in range(size):
    print("-",end="")
    if i<(size-1):
      print("+",end="")
  print("+")
  print("")
# 
# ボードレイアウト出力
def printRecord(size):
  global TOTAL
  global board
  print(TOTAL)
  sEcho=""
  for i in range(size):
    sEcho+=" " + str(board[i])
  print(sEcho)
  print ("+",end="")
  for i in range(size):
    print("-",end="")
    if i<(size-1):
      print("+",end="")
  print("+")
  for i in range(size):
    print("|",end="")
    for j in range(size):
      if i==board[j]:
        print("O",end="")
      else:
        print(" ",end="")
      if j<(size-1):
        print("|",end="")
    print("|")
    if i in range(size-1):
      print("+",end="")
      for j in range(size):
        print("-",end="")
        if j<(size-1):
          print("+",end="")
      print("+")
  print("+",end="")
  for i in range(size):
    print("-",end="")
    if i<(size-1):
      print("+",end="")
  print("+")
  print("")
#
# 対象解除法　対象解除ロジック
def symmetryOps(size):
  global BOUND1,BOUND2
  global TOPBIT,ENDBIT
  global COUNT2,COUNT4,COUNT8
  """
  ２．クイーンが右上角以外にある場合、
  (1) 90度回転させてオリジナルと同型になる場合、さらに90度回転(オリジナルか
  ら180度回転)させても、さらに90度回転(オリジナルから270度回転)させてもオリ
  ジナルと同型になる。
  こちらに該当するユニーク解が属するグループの要素数は、左右反転させたパター
  ンを加えて２個しかありません。
  """
  if board[BOUND2]==1:
    ptn=2
    own=1
    while own<size:
      bit=1
      you=size-1
      while (board[you]!=ptn) and (board[own]>=bit):
        bit<<=1
        you-=1
      if board[own]>bit :
        return 
      if board[own]<bit :
        break
      own+=1
      ptn<<=1 
    #90度回転して同型なら180度回転も270度回転も同型である
    if own>size-1:
      COUNT2+=1
      if DISPLAY==1:
        printRecord_bitmap(size,1)
      return 
  """
  ２．クイーンが右上角以外にある場合、
    (2) 90度回転させてオリジナルと異なる場合は、270度回転させても必ずオリジナル
    とは異なる。ただし、180度回転させた場合はオリジナルと同型になることも有り得
    る。こちらに該当するユニーク解が属するグループの要素数は、180度回転させて同
    型になる場合は４個(左右反転×縦横回転)
  """
  # 180度回転
  if board[size-1]==ENDBIT:
    you=size-1-1
    own=1
    while own<size:
      bit=1
      ptn=TOPBIT
      while (ptn!=board[you]) and (board[own]>=bit):
        bit<<=1
        ptn>>=1
      if board[own]>bit:
        return 
      if board[own]<bit:
        break
      own+=1
      you-=1
    #90度回転が同型でなくても180度回転が同型であることもある
    if own>size-1:
      COUNT4+=1
      if DISPLAY==1:
        printRecord_bitmap(size,1)
      return
  """
  ２．クイーンが右上角以外にある場合、
    (3)180度回転させてもオリジナルと異なる場合は、８個(左右反転×縦横回転×上下反転)
  """
  # 270度回転
  if board[BOUND1]==TOPBIT:
    ptn=TOPBIT>>1
    own=1
    while own<=size-1:
      bit=1
      you=0
      while (board[you]!=ptn) and (board[own]>=bit):
        bit<<=1
        you+=1
      if board[own]>bit:
        return 
      if board[own]<bit:
        break
      own+=1
      ptn>>=1
    COUNT8+=1
    if DISPLAY==1:
      printRecord_bitmap(size,1)
#
# 対象解除法　角にQがないときのバックトラック
def symmetry_backTrack(size,row,left,down,right):
  mask=(1<<size)-1
  bitmap=mask&~(left|down|right)
  if row==(size-1):
    if bitmap:
      if not  bitmap&LASTMASK:
        board[row]=bitmap   # Qを配置
        symmetryOps(size)   # 対象解除
  else:
    if row<BOUND1:          # 上部サイド枝刈り
      bitmap=bitmap|SIDEMASK
      bitmap=bitmap^SIDEMASK
    else:
      if row==BOUND2:       # 下部サイド枝刈り
        if not down&SIDEMASK:
          return
        if down&SIDEMASK!=SIDEMASK:
          bitmap=bitmap&SIDEMASK
    while bitmap:
      bit=-bitmap&bitmap
      bitmap=bitmap^bit
      board[row]=bit        # Qを配置
      symmetry_backTrack(size,row+1,(left|bit)<<1,down|bit,(right|bit)>>1)
#
# 対象解除法　角にQがあるときのバックトラック
def symmetry_backTrack_corner(size,row,left,down,right):
  global BOUND1
  global COUNT8
  mask=(1<<size)-1
  bitmap=mask&~(left|down|right)
  if row==(size-1):
    """
    １．クイーンが右上角にある場合、ユニーク解が属する
    グループの要素数は必ず８個(＝２×４)
    """
    if bitmap :
      board[row]=bitmap
      if DISPLAY :
        printRecord_bitmap(size,1)
      COUNT8+=1
  else:
    if row<BOUND1:    # 枝刈り
      bitmap=bitmap|2
      bitmap=bitmap^2
    while bitmap:
      bit=-bitmap&bitmap
      bitmap=bitmap^bit
      board[row]=bit
      symmetry_backTrack_corner(size,row+1,(left|bit)<<1,down|bit,(right|bit)>>1)
#
# 対象解除法
def symmetry(size):
  global TOTAL,UNIQUE,COUNT2,COUNT4,COUNT8
  global BOUND1,BOUND2
  global TOPBIT,ENDBIT,LASTMASK,SIDEMASK
  TOTAL=UNIQUE=COUNT2=COUNT4=COUNT8=0
  mask=(1<<size)-1
  TOPBIT=1<<(size-1)
  ENDBIT=LASTMASK=SIDEMASK=0
  BOUND1=2
  BOUND2=0
  board[0]=1
  while BOUND1>1 and BOUND1<size-1 :
    if BOUND1<size-1:
      bit=1<<BOUND1
      board[1]=bit    # ２行目にQを配置
      # 角にQがあるときのバックトラック
      symmetry_backTrack_corner(size,2,(2|bit)<<1,1|bit,(2|bit)>>1)
    BOUND1+=1
  TOPBIT=1<<(size-1)
  ENDBIT=TOPBIT>>1
  SIDEMASK=TOPBIT|1
  LASTMASK=TOPBIT|1
  BOUND1=1
  BOUND2=size-2
  while BOUND1>0 and BOUND2<size-1 and BOUND1<BOUND2:
    if BOUND1<BOUND2:
      bit=1<<BOUND1
      board[0]=bit    # Qを配置
      # 角にQがないときのバックトラック
      symmetry_backTrack(size,1,bit<<1,bit,bit>>1)
    BOUND1+=1
    BOUND2-=1
    ENDBIT=ENDBIT>>1
    LASTMASK=LASTMASK<<1|LASTMASK|LASTMASK>>1
  UNIQUE=COUNT8+COUNT4+COUNT2
  TOTAL=COUNT8*8 + COUNT4*4 + COUNT2*2
  print("TOTAL:" + str(TOTAL) + " COUNT2:"+str(COUNT2)+ " COUNT4:"+str(COUNT4)+" COUNT8:"+str(COUNT8))
#
# ミラーソルバー
def mirror_solver(size,row,left,down,right):
  global COUNT2
  global TOTAL
  mask=(1<<size)-1
  bit=0
  bitmap=0
  if row==size:
    COUNT2+=1
    TOTAL=TOTAL+1 # ボードレイアウト出力用
    printRecord_bitmap(size,1)
  else:
    # Ｑが配置可能な位置を表す
    bitmap=mask&~(left|down|right)
    while bitmap:
      bit=-bitmap&bitmap  # 一番右のビットを取り出す
      bitmap=bitmap^bit   # 配置可能なパターンが一つずつ取り出される
      board[row]=bit      # Ｑを配置
      mirror_solver(size,row+1,(left|bit)<<1,down|bit,(right|bit)>>1)
#
# ミラー
def Mirror(size):
  global COUNT2
  mask=(1<<size)-1
  bit=0
  """
  if size%2 :
    limit=size//2-1
  else:
    limit=size//2
  """
  limit=size%2 if size/2-1 else size/2
  # pythonでは割り算の切り捨ては`//`です
  for i in range(size//2):  # 奇数でも偶数でも通過
    bit=1<<i
    board[0]=bit            # １行目にＱを配置
    mirror_solver(size,1,bit<<1,bit,bit>>1)
  if size%2:                # 奇数で通過
    # Pythonでの割り算の切り捨ては`//`です
    bit=1<<(size-1)//2
    board[0]=1<<(size-1)//2 # １行目の中央にＱを配置
    left=bit<<1
    down=bit
    right=bit>>1
    for i in range(limit):
      bit=1<<i
      mirror_solver(size,2,(left|bit)<<1,down|bit,(right|bit)>>1)
  TOTAL=COUNT2<<1          # 倍にする
  print("size:",size,"TOTAL:",TOTAL,"COUNT2:",COUNT2)
#
# ビットマップ
def Bitmap(size,row,left,down,right):
  global TOTAL
  bitmap=0
  bit=0
  col=0
  mask=(1<<size)-1
  if row==size:
    TOTAL=TOTAL+1
    printRecord_bitmap(size,1) # 1:bitmap版 0: それ以外
  else:
    bitmap=mask&~(left|down|right)
    while bitmap:
      bit=-bitmap&bitmap
      bitmap=bitmap&~bit
      board[row]=bit
      Bitmap(size,row+1,(left|bit)<<1, (down|bit),(right|bit)>>1)
#
# ポストフラグ
def postFlag(row,size):
  global TOTAL
  col=0
  if row==size:
    TOTAL=TOTAL+1
    printRecord(size)
  else:
    for col in range(size):
      board[row]=col
      if(down[col]==0 and 
          right[row-col+size-1]==0 and
          left[row+col]==0):
        down[col]=1
        right[row-col+(size-1)]=1
        left[row+col]=1
        postFlag(row+1,size)
        down[col]=0
        right[row-col+(size-1)]=0
        left[row+col]=0;
#
# バックトラック版効き筋をチェック
def check_backTracking(row):
  global board
  for i in range(row):
    if board[i]>=board[row]:
      val=board[i]-board[row]
    else:
      val=board[row]-board[i]
    if board[i]==board[row] or val==(row-i):
      return 0
  return 1
#
# バックトラック
def backTracking(row,size):
  global TOTAL
  col=0
  if row==size:
    TOTAL=TOTAL+1
    printRecord(size)
  else:
    for col in range(size):
      board[row]=col
      if check_backTracking(row)==1:
        backTracking(row+1,size)
#
# ブルートフォース版効き筋チェック
def check_bluteForce(size):
  global board
  for r in range(1,size,1):
    for i in range(r):
      if board[i]>=board[r]:
        val=board[i]-board[r]
      else:
        val=board[r]-board[i]
      if board[i]==board[r] or val==(r-i):
        return 0
  return 1
#
# ブルートフォース
def bluteForce(row,size):
  col=0
  global TOTAL
  global board
  if row==size:
    if check_bluteForce(size)==1:
      TOTAL=TOTAL+1
      printRecord(size)
  else:
    for col in range(size):
      board[row]=col
      bluteForce(row+1,size)
#
# 実行
# bluteForce(0,5)   # １．ブルートフォース
# backTracking(0,5) # ２．バックトラッキング
# postFlag(0,5)     # ３．ポストフラグ
# Bitmap(5,0,0,0,0) # ４．ビットマップ
# Mirror(5)         # ５．ミラー
DISPLAY=1;          # 表示 1:出力する 0: 出力しない
symmetry(5)         # ６．対象解除法
#