Aristotle Number Puzzle 설명

Question

P : S : this 메타 스레드에서 코드 설명에 스택 오버플로를 요청할 수도 있음을 알게되었습니다.

this 사이트의 Aristotle Number 퍼즐에 대한 해결 방법을 이해하려고합니다. 나는 우리가 가우스 소거법을 사용 감소를 행 않을 때까지 점을 이해하고 다음 발견

이

a = 76 - j - k - n - 2o - p - r - s 
b = j + n + o 
c = -38 + k + o + p + r + s 
d = j + k + o 
e = -38 + k + n + o + p + r 
f = 38 - j - k - n - o - p 
g = 38 - k - o - r 
h = -38 + n + o + p + r + s 
i = 38 - j - k - n - o - r 
l = 38 - p - s 
m = 38 - n - o - p 
q = 38 - r - s 

코드의 저자는 다음 계속 :

을 이제 {에서 1 크기 (7)의 각 순열을을 , 2, ..., 19}, 독립 변수에 할당하고, 종속 변수를 생성하고 솔루션을 찾을 때까지 제약 조건을 테스트합니다.

정말이 개념을 이해하지 못합니다. 특히 this C 파일에, 나는 다음과 같은 두 가지 기능을 이해하고 있지 않다 : 누군가가이 해석을 이해 나를 도울 수 있다면

bool next_permutation(void) 
{ 
    for (int x = 6; x >= 0; x--) { 
     indices[x]++; 

     if (indices[x] == 19) { 
      if (!x) { 
       return false; 
      } 
      moveback(x, 18); 
      indices[x] = x; 
      continue; 
     } 

     swap(x, indices[x]); 
     break; 
    } 

    j = elem[0]; 
    k = elem[1]; 
    n = elem[2]; 
    o = elem[3]; 
    p = elem[4]; 
    r = elem[5]; 
    s = elem[6]; 

    return true; 
} 



// adds values to set 
// returns true if value successfully added; false otherwise 
bool add(int value) 
{ 
    if (value > 19 || value < 1) { 
     return false; 
    } 

    int bit = 1 << value; 
    if (set & bit) { 
     return false; 
    } 

    set |= bit; 
    return true; 
} 

나는 감사 높은 것이다. 저자는 행 축소를 위해 python 스크립트를 사용했습니다.

Answer 1

나는 Gaussian elimination이 하나의 방정식을 다른 방정식으로 대체하여 불필요한 변수를 제거함으로써 방정식 집합을 줄이는 방법 일 뿐이라고 생각합니다. 예를 들어, 당신은 19 개 방정식의 첫 번째 걸릴 수와 대한 방정식으로 변환합니다 :

a = 38 - b - c 

그리고 다른 18로 이것은을 제거하는 것이고, 그 때까지 반복 (18)에 식을 줄 것으로 대체 더 이상 제거 할 수 없습니다.

좋은 문제이며 SymPy 패키지를 사용해 볼 수있는 변명 거리가되었습니다.

다음은 SymPy에 방정식을 만든 다음 SymPy의 solve 함수를 사용하여 방정식을 줄이는 코드입니다.

from sympy import symbols, solve 
from sympy.parsing.sympy_parser import parse_expr 

# Number of unknowns 
n = 19 

variable_names = [chr(c + 97) for c in range(19)] 

# Create SymPy variables 
variables = symbols(variable_names) 

print("\n{} unknowns:".format(len(variables))) 
print(variables) 

# These strings define the equations to be solved 
hexagon_rows = [ 
    'abc', 
    'defg', 
    'hijkl', 
    'mnop', 
    'qrs', 
    'cgl', 
    'bfkp', 
    'aejos', 
    'dinr', 
    'hmq', 
    'lps', 
    'gkor', 
    'cfjnq', 
    'beim', 
    'adh' 
] 

def make_expression(chars, rhs=0): 
    return parse_expr('+'.join(list(chars)) + '-' + str(rhs)) 

expressions = [] 
for chars in hexagon_rows: 
    expressions.append(make_expression(chars, 38)) 

print("\n{} equations to solve:".format(len(expressions))) 

for expr in expressions: 
    print("{} = 0".format(expr)) 

# Try to solve the equations 
# (They can't be solved but SymPy reduces them down) 
reduced_expressions = solve(expressions) 

print("\nReduced to {} equations:".format(len(reduced_expressions))) 
for var, expr in reduced_expressions.items(): 
    print("{} = {}".format(var, expr)) 

출력 : 도움이

19 unknowns: 
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s] 

15 equations to solve: 
a + b + c - 38 = 0 
d + e + f + g - 38 = 0 
h + i + j + k + l - 38 = 0 
m + n + o + p - 38 = 0 
q + r + s - 38 = 0 
c + g + l - 38 = 0 
b + f + k + p - 38 = 0 
a + e + j + o + s - 38 = 0 
d + i + n + r - 38 = 0 
h + m + q - 38 = 0 
l + p + s - 38 = 0 
g + k + o + r - 38 = 0 
c + f + j + n + q - 38 = 0 
b + e + i + m - 38 = 0 
a + d + h - 38 = 0 

Reduced to 12 equations: 
j = b - n - o 
k = e - n - o - p - r + 38 
l = -p - s + 38 
i = -b - e + n + o + p 
c = e - n + s 
f = -b - e + n + o + r 
g = -e + n + p 
q = -r - s + 38 
m = -n - o - p + 38 
h = n + o + p + r + s - 38 
d = b + e - 2*n - o - p - r + 38 
a = -b - e + n - s + 38 

희망. 첫 번째 부분은 적어도!