ナイトツアーをPythonで解いてみる

はじめに

• 深さ優先探索がずっと苦手だったので，使って実装してみようと思いました

ナイトとは

• チェスの駒の一種

• ナイトの動き

  
  
  

• ナイトは以下のicooonサイトより引用

  • https://icooon-mono.com/12796-%e9%a6%ac%e3%81%ae%e3%83%95%e3%83%aa%e3%83%bc%e3%82%a2%e3%82%a4%e3%82%b3%e3%83%b3/

ナイトツアーとは

• n×nの盤面が与えられた際に，右下隅から開始してナイトの動きですべてのマスを一回ずつ通る経路を考えるパズル

深さ優先探索

• 解の探索アルゴリズムの一種
• 進めるところまでできる限り深く探索
  • 解が見つかれば終了
  • 解が見つからずこれ以上進めなくなれば一つ浅い部分に戻って探索を再開

ナイトツアーと深さ優先探索

• ナイトの8通りの動きのうち1つを選択して動かす
  • 上記を動けなくなるまで繰り返す
• 動けなくなるかつ盤面をすべて訪問済みの場合
  -> 探索終了
• 動けなくなるかつ盤面に未訪問のマスがある場合
  -> 動かす前に戻ってほかの動かし方を探索

作成したプログラム

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()

実行結果

• 実際は数字に色がついています
• size=7が現実的な実行時間で最大の盤面でした

initial chessboard
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|  -1|
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|  -1|
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|  -1|
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|  -1|
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|  -1|
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|  -1|
+----+----+----+----+----+----+----+
|  -1|  -1|  -1|  -1|  -1|  -1|   1|
+----+----+----+----+----+----+----+

answer
visit count: 593790
+----+----+----+----+----+----+----+
|  11|   8|  19|   4|  29|  46|  49|
+----+----+----+----+----+----+----+
|  18|   5|  10|  47|  20|  31|  28|
+----+----+----+----+----+----+----+
|   9|  12|   7|  30|   3|  48|  45|
+----+----+----+----+----+----+----+
|   6|  17|  14|  21|  44|  27|  32|
+----+----+----+----+----+----+----+
|  13|  22|  39|  16|  35|   2|  43|
+----+----+----+----+----+----+----+
|  40|  15|  24|  37|  42|  33|  26|
+----+----+----+----+----+----+----+
|  23|  38|  41|  34|  25|  36|   1|
+----+----+----+----+----+----+----+

7×7よりも広い盤面でも解ける方法ないか考えてみます