spaghetti

from math import sqrt
from itertools import count, islice

def is_prime(n):
    return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n)-1)))

N = 100

adj = [[] for _ in range(N)]

for i in range(1, N):
    for j in range(1, i):
        if is_prime(i + j):
            adj[i].append(j)


grid = [[-1] * N for _ in range(N)]

def prettyprint():
    cp = [i[:] for i in grid]
    for i in range(len(cp)):
        for j in range(len(cp)):
            if cp[i][j] == -1:
                cp[i][j] = ''
            else:
                cp[i][j] = str(cp[i][j])
            cp[i][j] = cp[i][j].rjust(3)
    strings = [''.join(i) for i in cp]
    minleading = min(len(a) - len(a.lstrip()) for a in strings)
    maxending = min(len(a) - len(a.rstrip()) for a in strings)
    print('\n'.join(i[minleading:][:-maxending] for i in strings if not len(set(i)) == 1))


def nei(x, y):
    for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
        if 0 <= nx < N and 0 <= ny < N:
            yield nx, ny

best = [0]

def dfs(current, x, y):
    if current > best[0]:

        best[0] = max(best[0], current)
        print('-' * 100)
        prettyprint()

    for nx, ny in nei(x, y):
        if grid[nx][ny] == -1:
            for x1, y1 in nei(nx, ny):
                if grid[x1][y1] in adj[current + 1]:
                    break
            else:
                continue
            grid[nx][ny] = current + 1
            dfs(current + 1, nx, ny)
            grid[nx][ny] = -1

grid[N//2][N//2] = 1
dfs(1, N//2, N//2)
print(best)