Pygame Knight’s Tour

Python Pygame application showing Knight’s Tour iterative algorithm.

# © 2019 TheFlyingKeyboard and released under MIT License
# theflyingkeyboard.net

import pygame
import sys
from random import randint


def draw_background():
    screen.fill(blackTileColor)

    for y in range(n):
        for x in range(n):
            if (x + y) % 2 == 0:
                pygame.draw.rect(screen, whiteTileColor, (tileSize * x, tileSize * y, tileSize, tileSize), 0)


def draw_tiles():
    for y in range(n):
        for x in range(n):
            if board[y][x] == visitedTile:
                pygame.draw.circle(screen, visitedTileColor,
                                   (tileSize * x + tileSize // 2, tileSize * y + tileSize // 2), tileSize // 4,  0)
            if board[y][x] == knightTile:
                pygame.draw.circle(screen, knightTileColor,
                                   (tileSize * x + tileSize // 2, tileSize * y + tileSize // 2), tileSize // 4, 0)


def can_move(next_knight_x_pos, next_knight_y_pos, move_num):
    x_move = next_knight_x_pos + knightMoves[move_num][0]
    y_move = next_knight_y_pos + knightMoves[move_num][1]

    if not ((0 <= x_move < len(board)) and (0 <= y_move < len(board))):
        return False

    return board[y_move][x_move] == emptyTile


def count_possible_moves(next_knight_x_pos, next_knight_y_pos):
    moves = 0

    for i in range(len(knightMoves)):
        if can_move(next_knight_x_pos, next_knight_y_pos, i):
            moves += 1

    return moves


def move():
    global knightXPos
    global knightYPos

    moves = []

    for i in range(len(knightMoves)):
        x_move = knightXPos + knightMoves[i][0]
        y_move = knightYPos + knightMoves[i][1]

        if can_move(knightXPos, knightYPos, i):
            moves.append(count_possible_moves(x_move, y_move))
        else:
            moves.append(-1)

    smallest_number = 8
    smallest_number_index = 0

    for i in range(len(knightMoves)):
        if moves[i] < smallest_number and moves[i] >= 0:
            smallest_number = moves[i]
            smallest_number_index = i

    board[knightYPos][knightXPos] = visitedTile
    pygame.draw.circle(screen, visitedTileColor,
                       (tileSize * knightXPos + tileSize // 2, tileSize * knightYPos + tileSize // 2), tileSize // 4, 0)

    knightXPos += knightMoves[smallest_number_index][0]
    knightYPos += knightMoves[smallest_number_index][1]

    board[knightYPos][knightXPos] = knightTile
    pygame.draw.circle(screen, knightTileColor,
                       (tileSize * knightXPos + tileSize // 2, tileSize * knightYPos + tileSize // 2), tileSize // 4, 0)


n = 8

screenSize = 1200
tileSize = screenSize // n

pygame.init()
screen = pygame.display.set_mode((screenSize, screenSize))

clock = pygame.time.Clock()

fps = 1

emptyTile = '.'
visitedTile = 'X'
knightTile = 'K'

whiteTileColor = (254, 205, 157)
blackTileColor = (208, 138, 70)
visitedTileColor = (255, 255, 255)
knightTileColor = (120, 120, 120)

knightMoves = [[2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1]]
board = [[emptyTile for _ in range(n)] for _ in range(n)]

knightXPos = randint(0, n - 1)
knightYPos = randint(0, n - 1)

board[knightYPos][knightXPos] = knightTile

moveNum = 0

draw_background()
draw_tiles()

skip = True

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_q:
                fps += 1
            if event.key == pygame.K_a:
                fps -= 1
                if fps == 0:
                    fps = 1
            if event.key == pygame.K_r:
                board = [[emptyTile for _ in range(n)] for _ in range(n)]

                knightXPos = randint(0, n - 1)
                knightYPos = randint(0, n - 1)

                board[knightYPos][knightXPos] = knightTile

                draw_background()
                draw_tiles()

                moveNum = 0
                skip = True

    if moveNum != n * n - 1 and not skip:
        move()
        moveNum += 1

    pygame.display.set_caption("Knight\'s Tour " + str(fps) + "fps")

    pygame.display.update()

    msElapsed = clock.tick(fps)

    skip = False