knights.py

import sys
from copy import copy

n = 5
moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

def intersect(p1, p2, p3, p4):
    # Going back on self
    if p1 == p4 and p2 == p3:
        return True
    
    # From one point to another (not backwards)
    if p2 == p3:
        return False

    if p2 == p4:
        return True

    def ccw(a, b, c):
        return (c[1]-a[1]) * (b[0]-a[0]) > (b[1]-a[1]) * (c[0]-a[0])
    
    test = ccw(p1,p3,p4) != ccw(p2,p3,p4) and ccw(p1,p2,p3) != ccw(p1,p2,p4)
    
    return test

def valid_position(p):
    return p[0] >= 0 and p[0] < n and p[1] >= 0 and p[1] < n

def crosses(path, knight, move):
    cross = False
    for i in range(len(path)-1):
        if intersect(path[i], path[i+1], knight, add_point(knight, move)):
            cross = True
    return cross

def add_point(p1, p2):
    return (p1[0]+p2[0], p1[1]+p2[1])

def solve(path, knight, move):
    next_knight = add_point(knight, move)
    next_path = copy(path)
    
    if valid_position(next_knight) and not crosses(path, knight, move):
        next_path.append(next_knight)
        return next_path, next_knight    
    else:
        return None

def make_move(path, knight, moves=moves):
    solves = []
    for m in moves:
        s = solve(path, knight, m)
        if s is not None:
            solves.append(s)
    return solves

def next_moves(last_move=[]):
    if last_move == []:
        return make_move([(0, 0)], (0, 0))
    else:
        solves = []
        for (path, knight) in last_move:
            solves.extend(make_move(path, knight))
        return solves

for line in sys.stdin:
    n = int(line.strip())
    moves, count = next_moves(), 1
    while len(moves):
        # print("{} -> ".format(len(moves)), end='')
        sys.stdout.flush()
        moves = next_moves(moves)
        count += 1
    print(count-1)