# knight.py

Created by schraf

Created on September 23, 2023

2.3 KB

```import random
from kandinsky import fill_rect
from time import sleep
from turtle import *

class Cell:
def __init__(self, x, y):
self.x = x
self.y = y

N = 8
BL, NR, RO = (255,)*3, (0,)*3, (255,0,0)
cx = [1, 1, 2, 2, -1, -1, -2, -2]
cy = [2, -2, 1, -1, 2, -2, 1, -1]

def board():
fill_rect(0,0,320,222,BL)
for i in range(9):
fill_rect(60 + 25 * i, 10, 1, 200, NR)
fill_rect(60, 10 + 25 * i, 200, 1, NR)

def ajout(a,c):
fill_rect(68+25*c.x, 18+25*c.y, 10, 10, RO)
sleep(.01)

def suppr(x,y):
fill_rect(68+25*x, 18+25*y, 10, 10, BL)

def limits(x, y):
return ((x >= 0 and y >= 0) and (x < N and y < N))

def isempty(a, x, y):
return (limits(x, y)) and (a[y * N + x] < 0)

def getDegree(a, x, y):
count = 0
for i in range(N):
if isempty(a, (x + cx[i]), (y + cy[i])):
count += 1
return count

def nextMove(a, cell):
ajout(a, cell)
min_deg_idx = -1
c = 0
min_deg = (N + 1)
nx = 0
ny = 0
start = random.randint(0, 1000) % N
for count in range(0, N):
i = (start + count) % N
nx = cell.x + cx[i]
ny = cell.y + cy[i]
c = getDegree(a, nx, ny)
if ((isempty(a, nx, ny)) and c < min_deg):
min_deg_idx = i
min_deg = c
if (min_deg_idx == -1):
return None
nx = cell.x + cx[min_deg_idx]
ny = cell.y + cy[min_deg_idx]
a[ny * N + nx] = a[(cell.y) * N + (cell.x)] + 1
cell.x = nx
cell.y = ny
return cell

def sol(a):
penup()
speed(3)
for n in range(N*N):
r = a.index(1+n)
x, y = -87.5 + 25 * (r // N), -87.5 + 25 * (r % N)
goto(x,y)
pensize(4)
goto(x,y)
pensize(1)
pendown()

def neighbour(x, y, xx, yy):
for i in range(N):
if ((x + cx[i]) == xx) and ((y + cy[i]) == yy):
return True
return False

def findClosedTour():
board()
a = [-1] * N * N
sx = 3
sy = 2
cell = Cell(sx, sy)
a[cell.y * N + cell.x] = 1
ret = None
for i in range(N * N - 1):
ret = nextMove(a, cell)
if ret == None:
suppr(cell.x, cell.y)
return False
if not neighbour(ret.x, ret.y, sx, sy):
return False
board()
sol(a)
return True

while not findClosedTour():pass```