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

今回は Python の Tkinter を利用して「ナイト巡回問題」を解く様子の可視化を行なってみたいと思います。

「ナイト巡回問題」がどのような問題であるかは下のページで解説していますので、こちらを参照していただければと思います(紹介しているプログラムはC言語になりますが、ナイト巡回問題がどのようなものであるかはプログラミング言語関係なく読んでみていただけると思います)。

ナイト巡回問題解説ページのアイキャッチ【C言語】ナイト巡回問題(ナイトツアー)のバックラック法での解き方

簡単に説明すると下記のようなゲームです。

  • チェスのナイトを利用したパズルゲーム
  • ゲームの目的は、チェス盤上の全マスを重複なくナイトに巡回させること
  • バックトラック法により、その巡回ルートを導出することが可能
    • バックトラック法とは「手を進めるだけで進め、途中で解になり得ないと分かったら一手戻して別の手を試す」手法

今回作成する Python スクリプトではこのバックトラック法でナイト巡回を解く際に、どのように「手を進める・一手戻す」が試行されていっているかを Tkinter で GUI 上に表示することで可視化を行います。

スクリプトを実行すると下のアニメーションのようにどんどんナイトの巡回ルートの描画・削除が行われていく様子が確認できます。

作成アプリのイメージ

これによりナイト巡回問題が解かれるときの様子やバックトラック法がどのような手法であるかを更に実感することができます。

ナイト巡回問題を解く様子を可視化するスクリプト

ナイト巡回問題を解く様子を可視化するスクリプトは下記のようになります。

ナイト巡回の可視化スクリプト
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

		# ナイトを8箇所全てに対して巡回させる
		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()

スクリプトの実行

スクリプトを実行すると下のような画面が表示されます。

起動画面

画面の下側にある「開始」ボタンをクリックすれば、キャンバス上にチェス盤が表示され、さらにチェス盤上にどんどん線が描画されていきます。

ナイトの巡回ルートを表示する様子

この線がナイトが巡回してきたルートを示すものになります。

この線が描画された時には「ナイトの巡回が1手進んだ」ことを表し、線が消えた時には「ナイトの巡回が1手戻った」ことを表すことになります。

どんどん線が描画されたり消えたりすることが確認でき、これによりナイト巡回がどのように解かれていっているかを実感することができます。

開始ボタンの上にはラベルを設置しており、このラベルには、現在までに幾つのパターンのナイト巡回問題の解を導き出したかを表示するようにしています。

解の数の表示

スクリプトの先頭ではチェス盤のサイズやナイトの初期位置等を設定できるようにしています。

スクリプトの設定
# チェス盤のサイズ
CHESS_WIDTH = 10
CHESS_HEIGHT = 3

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

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

またスクリプトでは線の描画時と削除時にスリープ処理を入れています。

これは、スリープを入れることで「ゆっくり・じっくり」ナイトの巡回する様子を確認できるようにするためです。

同様にスクリプトの先頭付近にこのスリープする時間を設定することが出来るようにしています。

スリープ時間の設定
# 描画時のウェイト(s)
WAIT = 0.1

0 に設定すればナイトが巡回するスピードが上がりますが、それでも描画にオーバーヘッドがかかるので解を求めるのにかなりの時間がかかります…。

スポンサーリンク

スクリプトの解説

最後に簡単にスクリプトの解説をしておきます。

スクリプトは3つのクラスから構成しています。

Controller クラス

Controller はユーザーからのイベント(アクション)を受け付けるクラスです。

といっても今回のスクリプトでは受け付けるイベントは「開始ボタンのクリック」のみです。

開始ボタンがクリックされた際には、後述する View クラスと Knight クラスのオブジェクトに処理開始を依頼(start メソッドを実行)します。

View クラス

View は主にアプリの画面の描画を行うクラスです。インスタンス生成時にアプリの画面(キャンバス・ボタン・ラベル)を作成します。

さらに View クラスは下記のメソッドを提供します。

start(処理の開始)

start メソッドはチェス盤の縦横サイズを引数として受け取り、キャンバス上にそのサイズ分の正方形を描画します。この縦横に並んだ正方形がチェス盤(を表したもの)となります。

この正方形の描画は tkinter Canvas クラスの create_rectangle メソッドにより実行しています。

チェス盤の描画
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"
)

第1引数から第4引数は描画する正方形の始点と終点であり、これらはマスのサイズ等から計算しています。

draw_oval(円の描画

draw_oval メソッドではナイトの現在位置を表す円を描画します。

円の描画は tkinter Canvas クラスの create_oval メソッドにより実行しています。

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

重複して円を描画しないように、create_oval メソッド実行前に、Canvas クラスの delete メソッドにより、事前に円の削除を行っています。

円の削除
self.canvas.delete("oval")

引数を create_oval メソッドの引数 tag に指定したタグ名とすることで、前回描画した円を削除することができます。

draw_line(線の描画

draw_line メソッドではナイトが今まで巡回した経路を表す線を描画します。

引数としてチェス盤上の座標(現在のナイトの位置と一手前のナイトの位置)を受け取って、それを get_pixel でキャンバス上の座標に変換し、そのキャンバス上の座標に線を描画します。

線の描画は tkinter Canvas クラスの create_line メソッドにより実行しています。

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

また引数として tag を受け取り、それを create_line に指定することで、ナイトの巡回を一手戻す際に、その tag の線を削除することが出来るようにしています。

delete_line(線の削除

delete_line メソッドは指定した tag の線を削除するメソッドです。

削除は Canvas クラスの delete メソッドにより行います。

線の削除
self.canvas.delete(tag)

get_pixel(キャンバス上の座標に変換

get_pixel メソッドは、チェス盤上の座標を受け取り、キャンバス上の座標に変換して返却するメソッドです。

マスのサイズ等を考慮して計算しています。

update_message(メッセージの描画

ラベルに表示するメッセージの更新を行います。

Knight クラス

Knight クラスはナイト巡回問題を解くクラスです。具体的にはナイトの巡回の手を進める・一手戻すといった処理を行います。

Knight クラスには4つのメソッドがあります。

start(処理の開始)

start メソッドが行うのは、ナイトの巡回状況を管理する二次元リスト board の初期化および各種設定(チェス盤のサイズや巡回必要なマス数など)と tour メソッド実行によるナイト巡回の開始です。

tour(ナイト巡回)

tour メソッドは実際にナイト巡回問題を解くメソッドになります。

tour メソッド内で tour メソッドを再帰的に呼び出すことで、チェス盤のマス数分をナイトが巡回し終わるまでナイト巡回を続けます。

今回は特にナイトが巡回する様子を可視化することが目的ですので、ナイト巡回問題を解くためのアルゴリズムについては省略させていただきます。

必要に応じて下記のナイト巡回問題を解く方法の解説ページを参考していただければと思います。

ナイト巡回問題解説ページのアイキャッチ【C言語】ナイト巡回問題(ナイトツアー)のバックラック法での解き方

tour メソッドでは、ナイト巡回を一手進める際には move メソッドを、ナイト巡回を一手戻す際には reverse メソッドを実行します。

move(ナイト巡回を一手進める)

ナイト巡回を進める際には、まずナイトが何回目の巡回で現在のマス(x, y)に訪れたかの情報を二次元リスト board[y][x] に格納し、さらにナイトが巡回したマス数 num_knight+1 します。

また、ナイト巡回が一手進んだことを画面に表示するために、View クラスの draw_oval メソッドと draw_line メソッドを実行することで円(ナイトの現在位置)と線(ナイトがこれまでに巡回した経路)の描画を行います。

reverse(ナイト巡回を一手戻す)

ナイト巡回を一手戻す際には、一手戻ったこと(ナイトの位置が元に戻る・ナイトの巡回経路が1つ取消しになる)を画面に表示するために View クラスの draw_oval メソッドと delete_line メソッドを実行します。

現在のマス(x, y)への巡回が取り消されたことを管理するために二次元リスト board[x][y]0 を格納し、さらにナイトが巡回したマス数 num_knight-1 します。

tour メソッドでナイト巡回を一手進める(move メソッド) or 一手戻す(reverse メソッド)を行い、move メソッドと reverse メソッドの中で線や円の描画・削除を行うことで、ナイトがどのように巡回しているかを画面上で確認することができます。

まとめ

このページではナイト巡回問題を解く様子を可視化する方法について解説しました。

ナイト巡回が一手進む or 一手戻る度に線や円の描画・削除を行うことでナイト巡回が解かれる様子を可視化しています。

こんな感じで自分で作ったプログラムの動作を可視化することで、よりプログラミングが楽しくなりますし、これも一つのプログラムの醍醐味だと思います。

今回はナイト巡回問題の可視化を行いましたが、他のプログラムの動作の可視化に是非挑戦してみてください!

オススメ参考書

今回紹介したスクリプトのように、ボタンや図形の描画を行う GUI アプリを作成するには tkinter がオススメです。

この tkinter の使い方を習得するための参考書としてはPythonでつくる ゲーム開発 入門講座がオススメです。

この本では主に tkinter を使用したゲームの開発を学べる参考書です。当然 tkinter について学べますし、題材がゲームなので楽しく学ぶ事もできます

私も Python を始めた時はこの参考書で勉強しました!

ゲームだけでなく、いろんな GUI アプリを作成したい方にもオススメです!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です