algorithm - 简单方程求解

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

这听起来有点像 constraint propogation .您可能会发现“Solving every Sudoku Puzzle”是了解总体思路的好书。