Last active
August 4, 2020 01:24
-
-
Save Carleslc/4da84bd8700b393abfea0f15face6c04 to your computer and use it in GitHub Desktop.
Solve Knight's Tour problem graphically step by step using Warndsdorff's rule on a classic chess board
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python3 | |
# -*- coding: utf-8 -*- | |
# KNIGHT'S TOUR PROBLEM | |
# https://en.wikipedia.org/wiki/Knight%27s_tour | |
# This program solves the problem using Warndsdorff's rule for a 8x8 board | |
# Further investigation: https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true | |
import argparse | |
import chess # python-chess (https://python-chess.readthedocs.io/en/latest/) | |
import chess.svg | |
from PyQt5.QtWidgets import QApplication, QWidget, QPushButton | |
from PyQt5.QtSvg import QSvgWidget | |
class Window(QWidget): | |
def __init__(self, left = 100, top = 100, width = 500, height = 500): | |
super().__init__() | |
self.left = max(0, left) | |
self.top = max(0, top) | |
self.width = max(20, width) | |
self.height = max(20, height) | |
self.update_geometry() | |
self.widgetSvg = QSvgWidget(parent=self) | |
self.widgetSvg.setGeometry(10, 10, self.width - 20, self.height - 20) | |
def update_geometry(self): | |
self.setGeometry(self.left, self.top, self.width, self.height) | |
def display_svg(self, svg): | |
self.widgetSvg.load(svg) | |
self.repaint() | |
def add_button(self, text, on_click): | |
btn = QPushButton(text, self) | |
self.height = self.height + 60 | |
self.update_geometry() | |
btn.move(int(self.width / 2) - 50, self.height - 50) | |
btn.clicked.connect(on_click) | |
class App(): | |
def __init__(self): | |
self.app = QApplication([]) | |
self.window = Window() | |
def exec(self): | |
self.window.show() | |
self.app.exec() | |
def set_args(): | |
global args | |
parser = argparse.ArgumentParser() | |
parser.add_argument("--start", help="start position (default = a8)", default="a8") | |
parser.add_argument("--reverse", action='store_true', help="reverse move ordering for another solution") | |
parser.add_argument("--verbose", action='store_true', help="log moves") | |
args = parser.parse_args() | |
def initial_board(): | |
global board, move_board, position, move_index | |
board = chess.Board.empty() | |
start = chess.__dict__.get(args.start.upper()) | |
position = start | |
board.set_piece_at(start, chess.Piece(chess.KNIGHT, chess.WHITE)) | |
move_board = [None] * 64 # each square position is the n-th knight's move | |
move_index = 0 | |
move(board, move_board, chess.Move(start, position)) # first move (start) | |
return board | |
def print_board(): | |
for i in range(8): | |
for j in range(8): | |
print(move_board[(8 - i - 1) * 8 + j], end=' ') | |
print() | |
def move(board, move_board, move): | |
global move_index | |
board.push(move) | |
board.turn = chess.WHITE | |
move_index += 1 | |
move_board[move.to_square] = move_index | |
def available_moves(move_board, moves): | |
return list(filter(lambda position: move_board[position] is None, moves)) | |
def warndsdorff_move(board, move_board, from_position): | |
moves = available_moves(move_board, board.attacks(from_position)) | |
if len(moves) == 0: | |
return None | |
if args.reverse: | |
moves.reverse() | |
next_available_moves_count = [] | |
for to_position in moves: | |
board.push(chess.Move(from_position, to_position)) | |
next_available_moves_count.append(len(available_moves(move_board, board.attacks(to_position)))) | |
board.pop() | |
next_position = moves[next_available_moves_count.index(min(next_available_moves_count))] | |
next_move = chess.Move(from_position, next_position) | |
return next_move | |
def board_svg(board, squares = [], lastmove = None): | |
return chess.svg.board( | |
board=board, | |
squares=chess.SquareSet(squares), | |
lastmove=lastmove, | |
coordinates=args.verbose).encode("UTF-8") | |
def next_board(board, move_board, position): | |
next_move = warndsdorff_move(board, move_board, position) | |
if next_move is None: | |
if args.verbose: | |
if len(list(filter(lambda check: check is None, move_board))) > 0: | |
print("No moves available") | |
print_board() | |
return None, None | |
move(board, move_board, next_move) | |
if args.verbose: | |
print(next_move) | |
return next_move, board_svg( | |
board=board, | |
squares=[check[0] for check in enumerate(move_board) if check[1] is not None and check[0] != next_move.to_square], | |
lastmove=next_move) | |
def display(svg): | |
if svg is None: | |
exit() | |
app.window.display_svg(svg) | |
def display_next_board(): | |
global position | |
next_move, svg = next_board(board, move_board, position) | |
display(svg) | |
position = next_move.to_square | |
if __name__ == "__main__": | |
global app, board, move_board, position | |
set_args() | |
app = App() | |
board = initial_board() | |
display(board_svg(board)) | |
app.window.add_button("Next move", display_next_board) | |
app.exec() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Usage
Example
python3 knight-tour-8.py --verbose