【Python】ナイト巡回問題を解く様子を Tkinter で可視化

import tkinter
import time

# チェス盤のサイズ
CHESS_WIDTH = 10
CHESS_HEIGHT = 3

# ナイトを最初に置く位置
START_X = 0
START_Y = 0

# マスのサイズ
SQUARE_WIDTH = 80
SQUARE_HEIGHT = 80

# 描画時のウェイト（s）
WAIT = 0.1


class Knight():

	def __init__(self, view):
		'ナイト巡回問題を解くオブジェクト生成'

		self.view = view

	def start(self, w, h, x, y):
		'初期位置(x,y)時のナイト巡回問題の開始'

		# チェス盤の全てを未巡回(0)に設定
		self.board = [[0] * w for _ in range(h)]

		# チェス盤のサイズを設定
		self.chess_width = w
		self.chess_height = h

		# 巡回済みマス数を0に設定
		self.num_knight = 0

		# 巡回必要なマス数を設定
		self.num_square = w * h

		# ナイト巡回問題の解の数を初期化
		self.resolve = 0

		start = time.time()

		# 初期位置を(x, y)としてナイト巡回問題を解く
		self.tour(x, y)

		end = time.time()

		print("time:" + str(end - start) + "[sec]")

	def tour(self, x, y):
		"(x,y)マスにナイトを巡回させる"

		# チェス盤の外に出る場合は巡回させない
		if x < 0 or x >= self.chess_width:
			return

		if y < 0 or y >= self.chess_height:
			return

		# 既にナイトが巡回済みの場合は巡回させない
		if self.board[y][x] != 0:
			return

		# ナイトを(x,y)マスに移動させる
		self.move(x, y)

		# 全マスを巡回し終わったかどうかを判断
		if self.num_square == self.num_knight:

			# 全マス巡回し終わっていたら解の数を+1
			self.resolve += 1

			self.view.update_message("見つかった解：" + str(self.resolve))

			# ナイト巡回を一手戻す
			self.reverse(x, y)

			return

		# ナイトを８箇所全てに対して巡回させる
		self.tour(x - 2, y - 1)
		self.tour(x - 2, y + 1)
		self.tour(x + 2, y - 1)
		self.tour(x + 2, y + 1)
		self.tour(x - 1, y - 2)
		self.tour(x - 1, y + 2)
		self.tour(x + 1, y - 2)
		self.tour(x + 1, y + 2)

		# ナイト巡回を戻して別の手を試す
		self.reverse(x, y)

	def move(self, x, y):
		'ナイトを(x,y)に移動させる'

		# ナイトが何手目に巡回したかを記録
		self.board[y][x] = self.num_knight + 1

		# ナイトの巡回回数をインクリメント
		self.num_knight += 1

		# 巡回先に丸を描画
		self.view.draw_oval(x, y)

		if self.num_knight == 1:
			return

		# 一手前にナイトが巡回した位置を取得
		for y1 in range(self.chess_height):
			for x1 in range(self.chess_width):
				if self.board[y1][x1] == self.num_knight - 1:
					break
			else:
				continue
			break

		# ナイトの巡回経路を遷都して描画
		tag = "line_" + str(self.num_knight)
		self.view.draw_line(x1, y1, x, y, tag)

	def reverse(self, x, y):
		'ナイト巡回を一手戻す'

		# 一手前にナイトが巡回した位置を取得
		for y1 in range(self.chess_height):
			for x1 in range(self.chess_width):
				if self.board[y1][x1] == self.num_knight - 1:
					break
			else:
				continue
			break

		# 一手戻したナイトの位置に丸を描画
		self.view.draw_oval(x1, y1)

		# ナイトの巡回経路を一手分削除
		tag = "line_" + str(self.num_knight)
		self.view.delete_line(tag)

		# ナイト巡回を一手戻す
		self.board[y][x] = 0
		self.num_knight -= 1


class View():

	def __init__(self, master):
		'UI関連のオブジェクト生成'

		# キャンバスのサイズをチェス盤のマス数から決定
		self.canvas_width = CHESS_WIDTH * SQUARE_WIDTH
		self.canvas_height = CHESS_HEIGHT * SQUARE_HEIGHT

		# キャンバスの生成と配置
		self.canvas = tkinter.Canvas(
			master,
			width=self.canvas_width,
			height=self.canvas_height,
		)
		self.canvas.pack()

		# ラベルの生成と配置
		self.text = tkinter.StringVar()
		self.text.set("開始ボタンを押してね")

		self.label = tkinter.Label(
			master,
			textvariable=self.text,
		)
		self.label.pack()

		# 開始ボタンの生成と配置
		self.button = tkinter.Button(
			master,
			text="開始",
		)
		self.button.pack()

	def start(self, w, h):
		'ナイト巡回経路描画用の背景を描画'

		# チェス盤のマス数を設定
		self.chess_width = w
		self.chess_height = h

		# チェス盤の位置調整用（中央寄せ）
		self.offset_x = (self.canvas.winfo_width() - SQUARE_WIDTH * w) // 2
		self.offset_y = (self.canvas.winfo_height() - SQUARE_HEIGHT * h) // 2

		# マス（チェス盤）を描画
		for y in range(h):
			for x in range(w):
				self.canvas.create_rectangle(
					self.offset_x + x * SQUARE_WIDTH,
					self.offset_y + y * SQUARE_HEIGHT,
					self.offset_x + (x + 1) * SQUARE_WIDTH,
					self.offset_y + (y + 1) * SQUARE_HEIGHT,
					width=3,
					fill="#EEEEFF",
					outline="#AAAAFF"
				)

		# 即座に描画を反映
		self.canvas.update()

	def draw_oval(self, x1, y1):
		'ナイトの現在位置を示す丸を描画'

		# マスの位置からキャンバス上のピクセルに変換
		coord = self.get_pixel((x1, y1))

		# 一旦丸を削除
		self.canvas.delete("oval")

		# 丸を描画（半径1px）
		self.canvas.create_oval(
			coord[0] - 10, coord[1] - 10,
			coord[0] + 10, coord[1] + 10,
			tag="oval",
			fill="#FFA588",
			outline="#DD8588"
		)

		# 描画を即座に反映
		self.canvas.update()

	def draw_line(self, x1, y1, x2, y2, tag):
		'ナイトの巡回経路を線として描画する'

		# 線の始点マスをキャンバス上にピクセルに変換
		coord1 = self.get_pixel((x1, y1))

		# 線の終点マスをキャンバス上にピクセルに変換
		coord2 = self.get_pixel((x2, y2))

		# 線を描画
		self.canvas.create_line(
			coord1[0], coord1[1],
			coord2[0], coord2[1],
			tag=tag,
			width=5,
			fill="#FFA588"

		)

		# 描画を即座に反映
		self.canvas.update()

		time.sleep(WAIT)

	def delete_line(self, tag):
		'描画済みの線を削除'

		# 指定されたタグの線を削除
		self.canvas.delete(tag)

		# 描画を即座に反映
		self.canvas.update()

		time.sleep(WAIT)

	def get_pixel(self, coord):
		'チェス盤上のマスをキャンバス上のピクセルに変換'

		# キャンバス上のピクセルに変換（マスの中央になるように変換）
		x = self.offset_x + SQUARE_WIDTH * coord[0] + SQUARE_WIDTH // 2
		y = self.offset_y + SQUARE_HEIGHT * coord[1] + SQUARE_HEIGHT // 2

		return (x, y)

	def update_message(self, text):
		'メッセージを更新してラベルに表示'

		# ラベルに描画する文字列をセット
		self.text.set(text)

		# 描画を即座に反映
		self.label.update()


class Controller():
	def __init__(self, view, knight):
		'KnightとViewを制御するオブジェクトを生成'

		# 制御するViewとKnightのオブジェクト設定
		self.view = view
		self.knight = knight

		# ボタンクリック時のイベントを受け付け
		self.view.button["command"] = self.button_click

	def button_click(self):
		'ボタンクリック時の処理'

		# Viewにナイト巡回問題開始（チェス盤のサイズ）を通知
		self.view.start(CHESS_WIDTH, CHESS_HEIGHT)

		# メッセージ更新
		self.view.update_message("解を探しています")

		# Knightにナイト巡回問題開始（チェス盤のサイズとナイトの初期位置も）を通知
		self.knight.start(CHESS_WIDTH, CHESS_HEIGHT, START_X, START_Y)


# アプリ生成
app = tkinter.Tk()
app.title("ナイト巡回問題")

# Viewオブジェクト生成
view = View(app)

# Knightオブジェクト生成
knight = Knight(view)

# Controllerオブジェクト生成
controller = Controller(view, knight)

# mainloopでイベント受付を待機
app.mainloop()

# チェス盤のサイズ
CHESS_WIDTH = 10
CHESS_HEIGHT = 3

# ナイトを最初に置く位置
START_X = 0
START_Y = 0

# マスのサイズ
SQUARE_WIDTH = 80
SQUARE_HEIGHT = 80

# 描画時のウェイト（s）
WAIT = 0.1

self.canvas.create_rectangle(
	self.offset_x + x * SQUARE_WIDTH,
	self.offset_y + y * SQUARE_HEIGHT,
	self.offset_x + (x + 1) * SQUARE_WIDTH,
	self.offset_y + (y + 1) * SQUARE_HEIGHT,
	width=3,
	fill="#EEEEFF",
	outline="#AAAAFF"
)

self.canvas.create_oval(
	coord[0] - 10, coord[1] - 10,
	coord[0] + 10, coord[1] + 10,
	tag="oval",
	fill="#FFA588",
	outline="#DD8588"
)

self.canvas.delete("oval")