簡單的公式解決

想到一個方程組的類似如下：簡單的公式解決

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 * ...變量。

來源

2011-03-31 raisyn

無論有多少變數，蠻力都能正常工作;） – Rudu 2011-03-31 18:25:13

[sympy]（http://code.google.com/p/sympy/） – 2011-03-31 18:27:16

聽起來有點像constraint propogation。你可能會發現「Solving every Sudoku Puzzle」是一個很好的閱讀來獲得總體思路。

來源

2011-03-31 18:25:53

是的，這與數獨解法有許多共同之處。這是一種[約束滿足問題]（http://en.wikipedia.org/wiki/Constraint_satisfaction_problem），其中有一些求解算法。 – 2011-03-31 18:27:23

問題是NP-complete。看方程系統：

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

假設D1，D2，D3中包含僅使用一次，因此添加沒有其他約束二= 0或di = 1的虛擬變量。因此，如果a = 0，則從第一個方程出發，c = 1。從第二個方程如下：C = 1，如果B = 0，並且從所述第三個，我們得到C = 0若a = 1且b = 1，因此，我們得到的關係

c = a NAND b.

因此，我們可以表達任何布爾電路使用這樣的方程組並且因此布爾滿足性問題可以被減少以求解這樣的方程組。

來源

2011-05-06 20:37:51 Accipitridae

簡單的公式解決

回答

相關問題