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

Проблема

Предположим, я даю вам треугольный набор лампочек с длиной стороны $n$ :

     o
    o o
   o o o
  o o o o
 o o o o o
o o o o o o
1 2  ...  n

Я собираюсь включить три лампочки, которые образуют «вертикальный» равносторонний треугольник, как в следующем примере:

     o
    o x
   o o o
  o o o o
 o x o o x
o o o o o o

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

Например, если вы удалили следующие лампочки (помеченные .), вы увидите только два следующих индикатора (помеченных x), что достаточно однозначно вывести третью (неосвещенную) позицию:

     .              .
    . o            . x
   . . o          . . o
  o o o .   =>   o o o .
 o o o o .      o x o o . <- the third unlit position
o . . . o o    o . . . o o

Позвольте a(n)быть максимальное количество лампочек, которые могут быть удалены без внесения каких-либо неясностей.

пример

С наивным алгоритмом я проверил значения до треугольника с длиной стороны 7, как показано ниже:

                                                                      .
                                                      .              . o
                                        .            . o            o . o
                           .           . .          . . o          . o o .
              .           . .         . o o        o o o .        o o . o .
 .           . .         . o o       o o . o      o o o o .      o . o . o o
. .         . o o       . o o o     o . . o o    o . . . o o    o . o . o o o

a(2) = 3    a(3) = 4    a(4) = 5    a(5) = 7     a(6) = 9       a(7) = 11

счет

Представление, которое вычисляет последовательность [a(2), a(3), ..., a(n)]для самых больших n побед. Если два представления имеют идентичные последовательности, выигрывает тот, который был опубликован ранее.

Хотя это и не обязательно для представления, для меня было бы поучительно, если вы опубликуете конструкцию получающихся триангулярных массивов, как в примере выше.

Python 3 ,n=8

import itertools
from ortools.sat.python import cp_model


def solve(n):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()
    cells = {
        (y, x): model.NewBoolVar(str((y, x)))
        for y in range(n) for x in range(y + 1)}
    triangles = [
            {cells[v] for v in ((y1, x1), (y2, x1), (y2, x1 + y2 - y1))}
            for (y1, x1) in cells.keys() for y2 in range(y1 + 1, n)]
    for t1, t2 in itertools.combinations(triangles, 2):
        model.AddBoolOr(t1.symmetric_difference(t2))
    model.Minimize(sum(cells.values()))
    solver.Solve(model)
    return len(cells) - round(solver.ObjectiveValue())


for n in itertools.count(2):
    print('a(%d) = %d' % (n, solve(n)))

Использует решатель CP-SAT Google OR-Tools .

После работы в течение ~ 30 секунд, он выводит следующее:

a(2) = 3
a(3) = 4
a(4) = 5
a(5) = 7
a(6) = 9
a(7) = 11
a(8) = 13

n=9$n^6$a(9)=15n=8

Как это устроено

$T_1$$T_2$$T_1$$T_2$

Таким образом, вопрос можно перефразировать как проблему SAT, с одним ограничением для каждой пары треугольников.

PS: Я бы очень хотел привести пример для n=8, но у меня проблемы с решателем SAT, который, очевидно, хочет оставить решения для себя.

Получение решений из программы @ Delfad0r

Я расширил программу @ Delfad0r для вывода решений. Это также дает промежуточные результаты, так что вы получите такой результат:

Solving n = 8:
a(8) >= 9
a(8) >= 10
a(8) >= 11
a(8) >= 12
a(8) >= 13
       o
      . o
     . o o
    . o o .
   o o . o o
  o o o o . .
 o . . o o o .
o . . o . o o o
a(8) = 13

Solving n = 9:
a(9) >= 10
a(9) >= 13
a(9) >= 14
a(9) >= 15
        o
       o o
      o . .
     o . o o
    . o . o o
   . o o o o o
  o o o . o . .
 o o o . . . o o
. o o o o o o . .
a(9) = 15

Это вычисление заняло несколько часов.

Если вы испытываете нетерпение и нажимаете Ctrl-Cпосле того, как какое-то неоптимальное решение было найдено, программа покажет это решение. Так что это не займет много времени, чтобы получить это:

                   .
                  o o
                 . o o
                . o o o
               o o . o o
              o . o o o .
             o . o . o o o
            . o o o o o . o
           o . . o o o o o o
          o o o o o o o o o .
         o o . o o o o . o o o
        o o o o o o . o . o o o
       o . o o . o o o o o o o o
      o o o . o o o o o . o o o o
     o o o . o o o o o o o o . . o
    o o o o o o o o o o o . o . . o
   o o o o . o o o o . o o o o o . o
  o o o o o o o o . o o . . o o o o .
 o o o o . o o . o . o o o o o o . o o
o o . o o . o o o o . o o o . o o o o o
a(20) >= 42

Вот расширенная программа:

import itertools
from ortools.sat.python import cp_model

class ReportPrinter(cp_model.CpSolverSolutionCallback):

    def __init__(self, n, total):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__n = n
        self.__total = total

    def on_solution_callback(self):
        print('a(%d) >= %d' %
              (self.__n, self.__total-self.ObjectiveValue()) )

def solve(n):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()
    cells = {
        (y, x): model.NewBoolVar(str((y, x)))
        for y in range(n) for x in range(y + 1)}
    triangles = [
            {cells[v] for v in ((y1, x1), (y2, x1), (y2, x1 + y2 - y1))}
            for (y1, x1) in cells.keys() for y2 in range(y1 + 1, n)]
    for t1, t2 in itertools.combinations(triangles, 2):
        model.AddBoolOr(t1.symmetric_difference(t2))
    model.Minimize(sum(cells.values()))
    print('Solving n = %d:' % n)
    status = solver.SolveWithSolutionCallback(model, ReportPrinter(n,len(cells)))
    if status == cp_model.OPTIMAL:
        rel = '='
    elif status == cp_model.FEASIBLE:
        rel = '>='
    else:
        print('No result for a(%d)\n' % n)
        return
    for y in range(n):
        print(' '*(n-y-1), end='')
        for x in range(y+1):
            print('.o'[solver.Value(cells[(y,x)])],end=' ')
        print()
    print('a(%d) %s %d' % (n, rel, len(cells) - solver.ObjectiveValue()))
    print()

for n in itertools.count(2):
    solve(n)

Python 3

Основываясь строго на ответе Делфадора , в основном следует той же логической последовательности, проверяя пары треугольников и проверяя конфигурацию, если она не содержит пар треугольников, которые не проходят эту проверку. Поскольку я не использовал никаких библиотек, кроме itertools и copy, у меня есть полный контроль над сохранением примеров, встречающихся в программе.

examples = dict() # stores examples by key pair of n to a tuple with the triangle and number of lights turned off

for n in range(3, 8):
    tri = [] # model of the triangle, to be filled with booleans representing lights
    tri_points = [] # list of tuples representing points of the triangle
    for i in range(n):
        tri.append([True]*(i + 1))
        for j in range(i+1):
            tri_points.append((i, j))

    t_set = [] # list of all possible triangles from tri, represented by lists of points
    for i in range(n):
        for j in range(len(tri[i])):
            for k in range(1, n - i):
                t_set.append([(i, j), (i + k, j), (i + k, j + k)])

    from itertools import combinations
    import copy

    # validates whether or not a triangle of n lights can have i lights turned off, and saves an example to examples if validated
    def tri_validate(x):
        candidate_list = list(combinations(tri_points, x))
        tri_pairs = list(combinations(t_set, 2))
        for candidate in candidate_list:
            temp_tri = copy.deepcopy(tri)
            valid = False
            for point in candidate:
                (row, col) = point
                temp_tri[row][col] = False
            for pair in tri_pairs:
                valid = False
                (tri1, tri2) = pair
                for point in tri1:
                    if not valid:
                        if point not in tri2:
                            (row, col) = point
                            if temp_tri[row][col]:
                                valid = True
                for point in tri2:
                    if not valid:
                        if point not in tri1:
                            (row, col) = point
                            if temp_tri[row][col]:
                                valid = True
                if not valid:
                    break
            if valid:
                examples[n] = (temp_tri, x)
                return True
        return False

    # iterates up to the point that validation fails, then moves on to the next n
    for i in range(len(tri_points)):
        if tri_validate(i + 1):
            continue
        break

Проблема в том, что это не очень эффективно. Он работает очень быстро до n=5, но начинает значительно замедляться после этой точки. На n=6это занимает около минуты, и гораздо медленнее n=7. Я предполагаю, что есть много исправлений эффективности, которые могут быть сделаны с этой программой, но это быстро сделанный предварительный набросок хорошего решения с намного большей гибкостью, чтобы проверить внутреннюю работу этого метода. Я буду постепенно работать над этим со временем.