Решение простых уравнений

Question

Представьте себе систему уравнений, подобную следующей:

a* = b + f + g
b* = a + c + f + g + h
c* = b + d + g + h + i
d* = c + e + h + i + j
e* = d + i + j   
f* = a + b + g + k + l
g* = a + b + c + f + h + k + l + m
h* = b + c + d + g + i + l + m + n
...  

a, b, c, ... element of { 0, 1 }
a*, b*, c*, ... element of { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
+ ... a normal integer addition

Даны некоторые переменные a, b, c ... a *, b *, c * .... Я хочу вычислить столько других переменных (a, b, c ... но не a *, b *, c * ...), сколько возможно логически.

Пример:

given: a = 0; b = 0; c = 0; 
given: a* = 1; b* = 2; c* = 1; 

a* = b + f + g          ==> 1 = 0 + f + g         ==> 1 = f + g
b* = a + c + f + g + h  ==> 2 = 0 + 0 + f + g + h ==> 2 = f + g + h
c* = b + d + g + h + i  ==> 1 = 0 + d + g + h + i ==> 1 = d + g + h + i

1 = f + g
2 = f + g + h     ==> 2 = 1 + h         ==> h = 1
1 = d + g + h + i ==> 1 = d + g + 1 + i ==> d = 0; g = 0; i = 0;

1 = f + g ==> 1 = f + 0 ==> f = 1

other variables calculated: d = 0; f = 1; g = 0; h = 1; i = 0;

Кто-нибудь может придумать, как выполнить эти операции автоматически?
Грубая сила может быть возможна в этом примере, но позже есть около 400 переменных a, b, c ... и 400 переменных a *, b *, c * ....

Answer 1

Это немного похоже на ограничение распространения .Вы можете найти " Решение каждой головоломки Судоку ", чтобы получить общее представление.

Answer 2

Проблема является NP-полной.Посмотрите на систему уравнений:

2 = a + c + d1
2 = b + c + d2
2 = a + b + c + d3

Предположим, что d1, d2, d3 являются фиктивными переменными, которые используются только один раз, и, следовательно, не добавляют никаких других ограничений, которые di = 0 или di = 1.Следовательно, из первого уравнения следует c = 1, если a = 0.Из второго уравнения следует c = 1, если b = 0, а из третьего мы получаем c = 0, если a = 1 и b = 1, и, следовательно, получаем соотношение

 c = a NAND b.

. Таким образом, мы можем выразить любоебулева схема с использованием такой системы уравнений и, следовательно, проблема булевой выполнимости может быть сведена к решению такой системы уравнений.