Magic Square Solver Использование Constraint-Programming

Question

Я пытаюсь создать собственный волшебный квадратный решатель с использованием программирования ограничений в Python. Для этого я использую ограничение python (http://labix.org/python-constraint).

Для этой задачи определение магического квадрата будет следующим: «Магический квадрат - это расположение целых чисел (положительных или отрицательных) в матрице nxn и такое, что сумма записей любой строки, любого столбца, или любая основная диагональ одинакова ».

У меня есть предварительно заполненные магический квадрат, как это:

+----+----+----+----+ 
| 7 | | | 4 | 
+----+----+----+----+ 
| | | | | 
+----+----+----+----+ 
| 0 | -3 | -2 | 3 | 
+----+----+----+----+ 
| -5 | 6 | | | 
+----+----+----+----+ 

Вот код, я использую:

from constraint import * 

problem = Problem() 
problem.addVariables(range(0, 16), range(-20, 20)) 

problem.addConstraint(lambda a: a==7, [0]) 
problem.addConstraint(lambda a: a==4, [3]) 
problem.addConstraint(lambda a: a==0, [8]) 
problem.addConstraint(lambda a: a==-3, [9]) 
problem.addConstraint(lambda a: a==-2, [10]) 
problem.addConstraint(lambda a: a==3, [11]) 
problem.addConstraint(lambda a: a==-5, [12]) 
problem.addConstraint(lambda a: a==6, [13]) 

problem.addConstraint(ExactSumConstraint(-2), [0,5,10,15]) 
problem.addConstraint(ExactSumConstraint(-2), [3,6,9,12]) 
for row in range(4): 
    problem.addConstraint(ExactSumConstraint(-2), 
          [row*4+i for i in range(4)]) 
for col in range(4): 
    problem.addConstraint(ExactSumConstraint(-2), 
          [col+4*i for i in range(4)]) 
solutions = problem.getSolution() 
print solutions 

Я не могу найти какие-либо решения, в то время как я думаю, что мои ограничения исправляет. Сумма каждой строки и каждого столбца и обеих диагоналей должна быть равна -2 (в зависимости от строки, которую мы имеем на магическом квадрате).

Есть ли у вас идеи? Благодарю.

Answer 1

Хорошо, давайте сделаем математику (и питон), чтобы решить вашу тайну.

Ограничение строки в первой строке сообщает вам, что значение в pos. 4 - -4. Ограничение для диагонали off указывает, что значение в pos. 6 равно 2.

Следовательно, мы уже использовали значения [-5, -4, -3, -2, 0, 2, 3, 4, 6, 7]. Сумма этих значений равна 8.

Для этого мы должны выбрать шесть значений вне диапазона (-20, 20) без уже выбранных значений.

В магическом квадрате с 4 раза 4 записей строки/столбец/диагональная сумма должна быть

1/4 * суммой (all_entries)

При том, что мы можем подготовить грубое силовое решение.

from itertools import combinations 
choosen = [-5, -4, -3, -2, 0, 2, 3, 4, 6, 7] # len(choosen) == 10 
s_choosen = sum(choosen) 
free_values = [x for x in range(-20, 20) if x not in choosen] 
to_test = [] 
# we have to choose 6 values out of free_values 
for comb in combinations(free_values, 6): 
    if (1/4. * (sum(comb) + s_choosen)) == -2: # could form correct row/col/diag sum 
    to_test.append(comb) 

Этот код дает нам 7254 возможных 6-ти кортежей, чтобы заполнить свободные места на площади. И ни один из них не дает волшебный квадрат.

Если вы явно не хотите применять AllDifferentConstraint(), вам необходимо выполнить следующее, чтобы проверить решение python-constraint с помощью принудительного выполнения.

Вы по-прежнему должны выбрать 6 значений; но на этот раз из всего диапазона (-20, 20) с заменой.

from itertools import combinations_with_replacement 
to_test2 = [] 
for comb in combinations_with_replacement(range(-20, 20), 6): 
    if (1/4. * (sum(comb) + s_choosen)) == -2: # could form correct row/col/diag sum 
      to_test2.append(comb) 
len (to_test2) 


97063 

Функция combinations_with_replacements возвращает только отсортированные комбинации. Теперь мы должны добавить все перестановки, которые удовлетворяют ограничению для сумм строк.

Уже установленные значения (7 и 4) имеют сумму 11. Поэтому первые две записи в 6-кортежах должны иметь сумму == -13. Для второй строки вычисленные записи (-4 и 2) имеют сумму -2. Таким образом, остальная запись для этой строки должна содержать до 0. В последней строке сумма уже заданных записей равна 1.Следовательно, сумма последних двух записей должна быть равна -3:

from itertools import permutations 
sum_rows = [] 
for comb in to_test2: 
    for entry in permutations(comb): 
     if entry[0] + entry[1] == -13 and entry[2] + entry[3] == 0 and entry[4] + entry[5] == -3: 
      sum_rows.append(entry) 
len(sum_rows) 




56672 

Теперь мы должны проверить суммы столбцов. Вторая колонка имеет (-3 и 6) сумму 3. Таким образом, сумма записей 0 и 2 должна быть равна -5. Третья колонка имеет (2 и -2) сумму 0. Поэтому сумма входов 1 и 4 должна быть равна -2. Четвертая колонка имеет (4 и 3) сумму 7. Следовательно, сумма записей 3 и 5 должна быть -9.

col_sums = [] 
for entry in sum_rows: 
    if entry[0] + entry[2] == -5 and entry[1] + entry[4] == -2 and entry[3] + entry[5] == -9: 
     col_sums.append(entry) 
len(col_sums) 




32 

Наконец, мы должны проверить сумму диагонали. Сумма диагонали (7 и -2) равна 5. Поэтому сумма входов 2 и 5 должна быть равна -7.

diag_sums = [] 
for entry in col_sums: 
    if entry[2]+ entry[5] == -7: 
     diag_sums.append(entry) 
len(diag_sums) 




1 




print diag_sums 

[(-6, -7, 1, -1, 5, -8)]