Solve Knight's Tour problem graphically step by step using Warndsdorff's rule on a classic chess board

knight-tour-8.py

#!/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()

pip install python-chess

Usage

usage: knight-tour-8.py [-h] [--start START] [--reverse] [--verbose]

optional arguments:
  -h, --help     show this help message and exit
  --start START  start position (default = a8)
  --reverse      reverse move ordering for another solution
  --verbose      log moves

Example

python3 knight-tour-8.py --verbose

a8b6
b6a4
a4b2
b2d1
d1f2
f2h1
h1g3
g3f1
f1h2
h2g4
g4h6
h6g8
g8e7
e7c8
c8a7
a7b5
b5a3
a3b1
b1d2
d2c4
c4a5
a5b7
b7d8
d8c6
c6b8
b8a6
a6c7
c7e8
e8d6
d6f7
f7h8
h8g6
g6h4
h4g2
g2e1
e1c2
c2a1
a1b3
b3c1
c1a2
a2b4
b4d3
d3e5
e5f3
f3g1
g1h3
h3g5
g5h7
h7f8
f8d7
d7c5
c5e4
e4c3
c3e2
e2d4
d4f5
f5e3
e3d5
d5f6
f6h5
h5f4
f4e6
e6g7
1 26 15 24 29 50 13 32 
16 23 28 51 14 31 64 49 
27 2 25 30 63 60 33 12 
22 17 52 59 44 57 48 61 
3 42 21 56 53 62 11 34 
18 39 54 43 58 45 8 47 
41 4 37 20 55 6 35 10 
38 19 40 5 36 9 46 7