Knights Tour Example

knights_tour.py

#!/usr/bin/env python3

"""
A puzzle game based on the Knight's Tour problem.

Requires Python 3.6+ and PyGame ($ pip3 install pygame)

Instructions:
* Left-click to move a knight's move away from the starting cell (highlighted blue)
* Right-click anywhere to undo
* Visit each of the gray cells the number of times the cell has in the center. (empty cells are visited once)
* When you solve it, close the window and restart it to generate a new puzzle.
* Change the random seed and grid size parameters after the import statements (line 28).
"""

from collections import defaultdict
from random import randint, shuffle, seed
from typing import DefaultDict, List, Tuple


try:
    import pygame as pg
except ImportError:
    print("Must have pygame installed")
    exit()


# ========== PARAMETERS ============
GRID_COUNT = (4, 4)  # (ncols, nrows)
seed(6)


all_moves: List[Tuple[int, int]] = [
    (-1, -2),
    (1, -2),
    (2, -1),
    (2, 1),
    (1, 2),
    (-1, 2),
    (-2, 1),
    (-2, -1),
]


def attempt_move(x: int, y: int, dx: int, dy: int, width: int, height: int):
    x += dx
    y += dy
    if 0 <= x < width and 0 <= y < height:
        return x, y, True
    return x - dx, y - dy, False


def gen_puzzle(width: int, height: int):
    """
    Generate a knight puzzle where you have to fill in the grid using only knights moves
    """
    grid = [[0] * width for _ in range(height)]
    x, y = startx, starty = randint(0, width - 1), randint(0, height - 1)
    grid[y][x] = 1
    ms = all_moves[:]

    max_steps = int(1.05 * width * height)
    steps = 0
    moves = [(0, 0)]
    while steps < max_steps:
        shuffle(ms)
        for move in ms:
            if move[0] == -moves[-1][0] and move[1] == -moves[-1][1]:
                continue

            x, y, valid = attempt_move(x, y, *move, width, height)

            if not valid:
                continue

            if grid[y][x] == -1:
                x -= move[0]
                y -= move[1]
                continue

            if grid[y][x] >= 0:
                grid[y][x] += 1
                steps += 1
                moves.append(move)
                break

        else:
            # Start backtracking (ran into a corner)
            if grid[y][x] == 1:
                grid[y][x] = -1
            else:
                grid[y][x] -= 1

            move = moves.pop()
            x -= move[0]
            y -= move[1]

    return (startx, starty), grid


def cell_rect(x, y):
    return pg.Rect(
        OFFSET[0] + x * CELL_SIZE + 2,
        OFFSET[1] + y * CELL_SIZE + 2,
        CELL_SIZE - 3,
        CELL_SIZE - 3,
    )


def coords2grid(x: int, y: int):
    return (
        (x - OFFSET[0]) // CELL_SIZE,
        (y - OFFSET[1]) // CELL_SIZE,
    )


def tiny_font(surface: pg.Surface, x: int, y: int, text: str, color=pg.Color("black")):
    text_render = _tiny_font.render(text, True, color)
    rect = cell_rect(x, y)
    surface.blit(
        text_render,
        (
            rect.centerx - text_render.get_width() // 2,
            rect.centery - text_render.get_height() // 2,
        ),
    )


OverlayGroup = pg.sprite.Group()


class TransCell(pg.sprite.Sprite):
    def __init__(self, x, y, color, a=128):
        pg.sprite.Sprite.__init__(self, OverlayGroup)
        self.rect = cell_rect(x, y)

        self.image = pg.Surface(self.rect.size)
        self.image.set_alpha(a)
        self.image.fill(color)


pos, puzzle = gen_puzzle(*GRID_COUNT)
goal = -1 + sum(sum(row) for row in puzzle)

pg.init()
pg.display.init()

WIDTH = 1500
HEIGHT = 900
CELL_SIZE = 60
GRID_SIZE = (GRID_COUNT[0] * CELL_SIZE, GRID_COUNT[1] * CELL_SIZE)
OFFSET = ((WIDTH - GRID_SIZE[0]) // 2, (HEIGHT - GRID_SIZE[1]) // 2)

screen = pg.display.set_mode((WIDTH, HEIGHT))
background = pg.Surface((WIDTH, HEIGHT))
# Used in tiny_font()
_tiny_font = pg.font.Font(None, 24)

# Draw background and grid
pg.draw.rect(background, pg.Color("white"), pg.Rect(0, 0, WIDTH, HEIGHT))
pg.draw.rect(background, pg.Color("gray"), pg.Rect(OFFSET, GRID_SIZE))
for x in range(GRID_COUNT[0] + 1):
    x = OFFSET[0] + x * CELL_SIZE
    pg.draw.line(
        background, pg.Color("black"), (x, OFFSET[1]), (x, OFFSET[1] + GRID_SIZE[1]), 3
    )
for y in range(GRID_COUNT[1] + 1):
    y = OFFSET[1] + y * CELL_SIZE
    pg.draw.line(
        background, pg.Color("black"), (OFFSET[0], y), (OFFSET[0] + GRID_SIZE[0], y), 3
    )

# Fill in unused squares
for y, row in enumerate(puzzle):
    for x, val in enumerate(row):
        if val in (-1, 0):
            pg.draw.rect(background, pg.Color(30, 30, 30), cell_rect(x, y))
        elif val > 1:
            tiny_font(background, x, y, str(val))

jumps: DefaultDict[Tuple[int, int], int] = defaultdict(int)
jumps[pos] = 1
current = TransCell(*pos, color=pg.Color(0, 0, 255))

overlay: DefaultDict[Tuple[int, int], List[TransCell]] = defaultdict(list)
positions = [cell_rect(*pos)]

killed = False
while not killed and goal > 0:
    for event in pg.event.get():
        if event.type == pg.QUIT:
            killed = True
            break

        elif event.type == pg.MOUSEBUTTONDOWN and event.button == 1:
            new_pos: Tuple[int, int] = coords2grid(*event.pos)

            if 0 <= new_pos[0] < GRID_COUNT[0] and 0 <= new_pos[1] < GRID_COUNT[1]:
                dx, dy = new_pos[0] - pos[0], new_pos[1] - pos[1]
                if sorted([abs(dx), abs(dy)]) != [1, 2]:
                    continue

                x, y = new_pos
                if (
                    puzzle[y][x] != -1
                    and jumps[new_pos] < puzzle[y][x]
                    and (
                        len(positions) < 2
                        or new_pos != coords2grid(*positions[-2].center)
                    )
                ):
                    overlay[pos].append(TransCell(*pos, pg.Color("black")))
                    pos = new_pos
                    jumps[pos] += 1
                    current.rect = cell_rect(*pos)
                    positions.append(current.rect)
                    goal -= 1

        elif (
            event.type == pg.MOUSEBUTTONDOWN
            and event.button == 3
            and len(positions) > 1
        ):
            current.rect = positions[-2]
            del positions[-1]
            jumps[pos] -= 1
            pos = coords2grid(*current.rect.center)
            overlay[pos].pop().kill()
            goal += 1

    screen.blit(background, (0, 0))
    OverlayGroup.draw(screen)
    if len(positions) > 1:
        pg.draw.lines(
            screen, pg.Color("black"), False, [rect.center for rect in positions], 2
        )

    pg.display.flip()


if goal > 0:
    quit()


large_font = pg.font.Font(None, 200)
win_message = large_font.render("You won!", True, pg.Color("green"))
screen.blit(
    win_message,
    ((WIDTH - win_message.get_width()) // 2, (HEIGHT - win_message.get_height()) // 2),
)
pg.display.flip()

pg.event.set_allowed(pg.QUIT)
pg.event.clear()
while True:
    for event in pg.event.get():
        if event.type == pg.QUIT:
            quit()