Идея:
так как у нас есть некоторые подсказки значений в виде неполной таблицы истиности, и она маленькой размерности, то можно просто проверить все перестановки.
Мне показалось, что искать перестановки будет удобнее, если подбирать таблицу по столбцам, поэтому запишу условие задачи вот так (None, естественно, соответствует пустой клетке):
patterns = [
[None, None, 1 ],
[None, 1, None],
[None, None, None],
[1, 1, None],
]
results = [
0,
0,
0
]
Далее, генерируем уникальные перестановки (a, b, c, d) и используем некоторую функцию (название мне было придумывать лень, назвал её fs) для проверки подойдет ли данная комбинация паттерну из условия задачи (таких комбинаций может быть несколько у подобных задач, но конкретно для этой таблицы будет только одна подходящая комбинация)
def search(patterns, results):
for variant in permutations(('a', 'b', 'c', 'd'), 4):
correct_variant = fs(variant, patterns, results)
if correct_variant:
print(variant)
Ну и далее основа решения - функция fs.
Данная функция это классический поиск в дереве состояний (эх, Prolog, тут был бы однозначно кстати).
В ней мы построчно идем по таблице-паттерну, для пустых None значений мы рекурсивно проверяем оба возможных варианта 0 или 1, учитывая требования задачи к уникальности строк таблицы.
def fs(positions, patterns, results, position=(0, 0)):
count_results = len(results) # == len(patterns[i])
count_positions = len(positions)
i, j = position
while i < count_results:
current_is_none = patterns[j][i] is None
if current_is_none:
isOk = False
for value in (0, 1):
patterns[j][i] = value
isOk = isOk or fs(positions, patterns, results, position=(i, j))
patterns[j][i] = None
return isOk
j += 1
if j == count_positions:
# попали в неуникальную строку, нужно делать откат
if len(set('_'.join(str(column[k]) for column in patterns) for k in range(i+1))) != i+1:
return False
# проверяем совпадает ли результат выполнения функции F с тем который нам нужен по условию
if results[i] != F(**{
name: patterns[j2][i] for j2, name in enumerate(positions)
}):
return False
i += 1
j = 0
return True
Ну и код целиком:
from itertools import *
# kwargs = {
# 'a': a,
# 'b': b,
# 'c': c,
# 'd': d,
# },
def F(a, b, c, d):
return int(a and not(b) or (a or b) and c or d)
def search(patterns, results):
for variant in permutations(('a', 'b', 'c', 'd'), 4):
correct_variant = fs(variant, patterns, results)
if correct_variant:
print(variant)
def fs(positions, patterns, results, position=(0, 0)):
count_results = len(results) # == len(patterns[i])
count_positions = len(positions)
i, j = position
while i < count_results:
current_is_none = patterns[j][i] is None
if current_is_none:
isOk = False
for value in (0, 1):
patterns[j][i] = value
isOk = isOk or fs(positions, patterns, results, position=(i, j))
patterns[j][i] = None
return isOk
j += 1
if j == count_positions:
# попали в неуникальную строку, нужно делать откат
if len(set('_'.join(str(column[k]) for column in patterns) for k in range(i+1))) != i+1:
return False
if results[i] != F(**{
name: patterns[j2][i] for j2, name in enumerate(positions)
}):
return False
i += 1
j = 0
return True
if __name__ == '__main__':
patterns = [
[None, None, 1 ],
[None, 1, None],
[None, None, None],
[1, 1, None],
]
results = [
0,
0,
0
]
search(patterns, results)