Разделочная доска algo

Это заняло у меня время, чтобы придумать, и не очень эффективно, но для маленьких головоломок это должно быть хорошо.

class Piece:
    def __init__(self, data, w, h):
        self.data = data
        self.w = w
        self.h = h

    def cut_vertically(self, x):
        a = Piece([v for i, v in enumerate(self.data) if i % self.w <= x], x + 1, self.h)
        b = Piece([v for i, v in enumerate(self.data) if i % self.w > x], self.w - x - 1, self.h)
        s = sum(self.data)
        return a, b, s

    def cut_horizontally(self, y):
        a = Piece([v for i, v in enumerate(self.data) if i < self.w * (y + 1)], self.w, y + 1)
        b = Piece([v for i, v in enumerate(self.data) if i >= self.w * (y + 1)], self.w, self.h - y - 1)
        s = sum(self.data)
        return a, b, s

    def generate_cuts(self):
        for x in range(self.w - 1):
            yield self.cut_vertically(x)
        for y in range(self.h - 1):
            yield self.cut_horizontally(y)

def scores(p):
    if p.w == 1 and p.h == 1:
        yield 0

    for a, b, s in p.generate_cuts():
        for s1 in scores(a):
            for s2 in scores(b):
                yield s + s1 + s2

p = Piece([2, 7, 5, 1, 9, 5], 3, 2)

min_score = None
for score in scores(p):
    if not min_score or score < min_score:
        min_score = score

print(score)

У него нет проверки на наличие ошибок, поэтому вы должны убедиться, что ваш Piece настроен правильно, но я надеюсь, что этого достаточно для ваших нужд.