ナイトツアーにwarnsdorff's ruleを適用する

はじめに

• 以前以下の記事でナイトツアーを深さ優先探索で解いた
  • ナイトツアーをPythonで解いてみる
  
  
• ヒューリスティックな手法warnsdorff's ruleを適用してより高速に解いてみる

深さ優先探索によるナイトツアー

KnightTour.py

from functools import partial
import sys

def my_colorize(text: str, color: int):
  return f"\x1b[{color}m{text}\x1b[0m"

colorize_green = partial(my_colorize, color=32)
colorize_red = partial(my_colorize, color = 31)

class Chessboard:
  def __init__(self, size):
    self.size = size
    self.board = [[-1 for i in range(self.size)] for j in range(self.size)]
    self.track = 1
    self.p = [self.size-1, self.size-1]
    self.move_list = [[-2,-1],[-1,-2],[1,-2],[2,-1],[-2,1],[-1,2],[1,2],[2,1]]
    self.count = 0
    self.visit(self.p)

  def show_board(self):
    for v in range(2*self.size+1):
      if v % 2 == 0:
        print("+",end = '')
        for h in range(self.size):
          print("----",end='+')
        print()
      else:
        for h in range(self.size):
          if self.board[v //2][h] < 0:
            print('|'+colorize_red('{:>4}').format(self.board[v // 2][h]),end = '')
          else:
            print('|'+colorize_green('{:>4}').format(self.board[v // 2][h]),end = '')
        print('|')

  def visit(self, next): # next:次に訪れる座標のリスト
    self.count += 1
    if next[0] > self.size-1 or next[0] < 0 or next[1] > self.size-1 or next[1] < 0:
      return False
    if self.board[next[0]][next[1]] == -1:
      self.board[next[0]][next[1]] = self.track
      self.track += 1
      self.p = next
      return True
    else:
      return False

  def backtrack(self):
    self.track -= 1
    self.board[self.p[0]][self.p[1]] = -1
    for i in range(self.size):
      for j in range(self.size):
        if self.board[i][j] == self.track-1:
          self.p[0] = i
          self.p[1] = j

  def search(self):
    for move in self.move_list:
      if self.visit([self.p[i]+move[i] for i in range(len(move))]):
        self.search()
      else:
        continue
    if any(-1 in row for row in self.board): # これ以上探すところがなく，-1が残っているとき
      self.backtrack()
      return
    else:
      print("\nanswer")
      print("visit count:",self.count)
      self.show_board()
      sys.exit()

  def knight_tour(self):
    return

size = 7
chess = Chessboard(size)
print("\ninitial chessboard")
chess.show_board()
chess.search()

深さ優先探索の流れ

• 移動可能なマスに移動し続ける
• 移動可能なマスがなくなったとき，1つ前の状態に戻る

計算量削減に有効なマスの選択方法をしていない

warnsdorff's ruleとは

• 計算量を減らすためのヒューリスティックな手法
• 移動先の少ないマスを探索の序盤で調べる
  • のちに移動不可能となる可能性を減らす

warnsdorff's ruleの手順

• ナイトの動きで移動可能なマスについて以下を実行
  • それぞれのマスからナイトの動きで移動可能なマスの数を数える
• 上で調べた中から最も移動可能数の小さいマスへ移動
• 最小の移動可能数が同じ場合ランダム

warnsdorff's ruleの具体例

• 初期盤面での次の一手の決め方

  
  
  

• 移動可能な2マスについて，移動後の移動可能マスを数える

  1. 5マス

     
     
     

  2. 5マス

     
     
     

• 移動可能なマスの数は同じ

  • どちらに移動するかランダムで決定

• 次の盤面での次の一手の決め方

  
  
  

• 移動可能な5マスについて，移動後の移動可能なマス数を数える

  1. 1マス

     
     
     

  2. 3マス

     
     
     

  3. 3マス

     
     
     

  4. 3マス

     
     
     

  5. 3マス

     
     
     

• 最も移動可能なマスが少ないのは1.の1マスのとき

  • そのマスへ進む

warnsdorff's ruleの適用

• 以下のコードをKnightTour.pyに追加

def warnsdorff(self):
    option_list = []
    move_list = []
    for move in self.move_list:
      next = [self.p[i]+move[i] for i in range(len(move))]
      if not self.visitable(next):
        continue
      move_list.append(move)
      option = 0
      for nextmove in self.move_list:
        nextnext = [next[i] + nextmove[i] for i in range(len(nextmove))]
        if self.visitable(nextnext):
          option += 1
      option_list.append(option)
    if len(option_list) == 0 :
      return []
    option_min = min(option_list)
    output = []
    for i in range(len(option_list)):
      if option_list[i] == option_min:
        output.append(move_list[i])
    random.shuffle(output)
    return output

• KnightTourのsearch関数を以下のように変更

def search(self):
    move_list = self.warnsdorff() # warnsdorff's rule を用いた実装
    for move in move_list:
      if self.visitable([self.p[i]+move[i] for i in range(len(move))]):
        self.visit([self.p[i]+move[i] for i in range(len(move))])
        self.search()
      else:
        continue
    if any(-1 in row for row in self.board): # これ以上探すところがなく，-1が残っているとき
      self.backtrack()
      return
    else:
      print("\nanswer")
      print("backtrack count:",self.count)
      self.show_board()
      sys.exit()

深さ優先探索で探索するマスの候補をwarnsdorff's ruleによって絞る

実行結果

5×5の盤面でwarnsdorff's rule有り無しで比較

• warnsdorff's rule無し

  answer
  backtrack count: 51303
  +----+----+----+----+----+
  |  23|  12|   3|  18|  25|
  +----+----+----+----+----+
  |   4|  17|  24|  13|   8|
  +----+----+----+----+----+
  |  11|  22|   7|   2|  19|
  +----+----+----+----+----+
  |  16|   5|  20|   9|  14|
  +----+----+----+----+----+
  |  21|  10|  15|   6|   1|
  +----+----+----+----+----+
  

  
  

• warnsdorff's ruleを適用

  answer
  backtrack count: 0
  +----+----+----+----+----+
  |   5|  16|  21|  10|   3|
  +----+----+----+----+----+
  |  22|  11|   4|  15|  20|
  +----+----+----+----+----+
  |  17|   6|  25|   2|   9|
  +----+----+----+----+----+
  |  12|  23|   8|  19|  14|
  +----+----+----+----+----+
  |   7|  18|  13|  24|   1|
  +----+----+----+----+----+
  

  
  

• warnsdorff's ruleの適用によって深さ優先のバックトラック回数が 51303 → 0 に削減

warnsdorff's rule適用後では，ナイトはど真ん中（移動可能マスが最大のマス）を最後に訪問

盤面サイズの限界

• 今回実装したwarnsdorff's rule適用後のアルゴリズムでは48×48の盤面まで探索可能