Simple equations solving

Think of a equations system like the following:

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

Some of the variables a, b, c... a*, b*, c*... are given. I want to calculate as much other variables (a, b, c... but not a*, b*, c*...) as logically possible.

Example:

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;

Can anybody think of a way to perform this operations automatically?

Brute force may be possible in this example, but later there are about 400 a, b, c... variables and 400 a*, b*, c*... variables.

---

This sounds a little like constraint propogation. You might find "Solving every Sudoku Puzzle" a good read to get the general idea.

---

The problem is NP-complete. Look at the system of equations:

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

Assume that d1,d2,d3 are dummy variables that are only used once and hence add no other constraints that di=0 or di=1. Hence from the first equation follows c=1 if a=0. From the second equation follows c=1 if b=0 and from the third one we get c=0 if a=1 and b=1 and hence we get the relation

 c = a NAND b.

Thus we can express any boolean circuit using such a system of equations and therefore the boolean satisfyability problem can be reduced to solving such a system of equations.