Решатель нонограмм - поиск всех возможных комбинаций строк в соответствии с его ограничениями на Python с использованием отслеживания с возвратом - PullRequest
Новая
       21

Решатель нонограмм - поиск всех возможных комбинаций строк в соответствии с его ограничениями на Python с использованием отслеживания с возвратом

1 голос
/ 26 мая 2020

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

Итак, мне нужна функция foo, которая получает строка и ограничения foo(row, const), и возвращает комбинации в соответствии с порядком в списке ограничений.

Строка содержит элементы: 1, 0 или «?».

1 - уже окрашены

0 - неокрашенный

"?" - нейтральный (может быть как цветным, так и неокрашенным)

Несколько примеров желаемого результата: 

foo([1, 1, "?", 0], [3]) ---> [[1, 1, 1, 0]]

foo(["?", 0, 1, 0, "?", 0], [1,1]) ---> [[0, 0, 1, 0, 1, 0], [1, 0, 1, 0, 0, 0]]

foo([0, 0, "?", 1, 0] , [3]) ---> []

Вот моя неудачная попытка: 

def foo(row, const, options_lst=[]):

if len([const[j] for i in range(len(row)) if row[i:i + const[0]]
       == const[0]*[1] for j in range(len(const))]) >= 1:
    if row not in options_lst:
        for i in range(len(row)):
            if row[i] == "?":
                row[i] = 0
        options_lst.append(row)
    print(options_lst)
    return

for i in range(len(row)):
    if row[i] == "?":
        row[i] = 1
        foo(row, const)
...