Reverse boggle.py

from difflib import SequenceMatcher
from itertools import combinations
from math import sqrt, ceil
from random import choice

inp = """MID
RANA
GRANT
BOCCA
CILIA
WAIVE
OSSAL
SALMO
FICE"""
max_N = ceil(sqrt(len(inp.replace('\n', ''))))


class Cell:
    def __init__(self, x, y, board):
        self.x = x
        self.y = y
        self.nbs = {(x - nx, y - ny) for nx in range(-1, 2) for ny in range(-1, 2) if
                    board.N > x - nx >= 0 and board.N > y - ny >= 0 and not nx == ny == 0}
        self.letter = '-'

    def __str__(self):
        return self.letter


class Board:
    def __init__(self, n):
        self.N = n
        self.cells = [['-'] * n for _ in range(n)]
        self.available = []
        for y in range(n):
            for x in range(n):
                self.cells[x][y] = Cell(x, y, self)
                self.available.append(self.cells[x][y])

    def get(self, x, y):
        return self.cells[x][y]

    def place(self, w, c=None, path=None):
        if path is None:
            path = []

        if c is None:
            c = self.available[0]

        self.available.remove(c)
        c.letter = w[0]
        path.append(c)
        if len(w) > 1:
            return self.place(w[1:], self.get(*choice([x for x in c.nbs if self.get(*x) in self.available])), path)
        else:
            return path

    def place_in(self, w, a, b, size, path):
        cur = path[a]
        for i in range(b - 1, -1, -1):
            cur = self.get(*choice([x for x in cur.nbs if self.get(*x) in self.available]))
            self.available.remove(cur)
            cur.letter = w[i]

        cur = path[a + size - 1]
        for i in range(b + size, len(w)):
            cur = self.get(*choice([x for x in cur.nbs if self.get(*x) in self.available]))
            self.available.remove(cur)
            cur.letter = w[i]

    def fill_empty(self):
        for cell in self.available:
            cell.letter = choice('ABCDEFGHIJKLMNOPQRSTUVWXYZ')

    def __str__(self):
        return '\n'.join([''.join(map(str, row)) for row in self.cells])


mchrs = []
for c in combinations(inp.splitlines(), 2):
    mchrs.append(SequenceMatcher(None, *c))

ms = []
for m in sorted(mchrs, key=lambda mr: mr.ratio(), reverse=True):
    ms.append((m.a, m.b, m.find_longest_match(0, len(m.a), 0, len(m.b))))


while True:
    try:
        b = Board(max_N)
        done = set()

        for m in ms:
            if m[0] not in done:
                p = b.place(m[0])
                done.add(m[0])
                if m[1] not in done:
                    b.place_in(m[1], m[2][0], m[2][1], m[2][2], p)
                    done.add(m[1])
            elif m[1] not in done:
                b.place(m[1])
    except:
        pass
    else:
        b.fill_empty()
        print(b)
        break