Задача на магический квадрат
Моё решение не проходит по времени задачу "Магический квадрат".
ссылка на задачу https://informatics.msk.ru/mod/statements/view.php?chapterid=2776#1
Магический квадрат
Магическим квадратом будем называть квадрат с одинаковой суммой чисел по всем вертикалям и горизонталям; никаких требований на суммы по диагоналям накладывать не будем. Составьте такой квадрат из заданного набора чисел.
Входные данные Во входном файле записаны 16 различных целых чисел в интервале от 0 до 32768
Выходные данные В выходной файл необходимо вывести искомое расположение чисел, составляющее магический квадрат 4*4 (каждое число должно встречаться ровно один раз), в четырех строках по четыре числа, или строку NO SOLUTION, если квадрат составить нельзя.
Примеры входные данные
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
выходные данные
1 6 13 14
2 11 12 9
15 7 4 8
16 10 5 3
Я пытался решать рекурсивным перебором. Кидать код не обязательно. Мне нужны идеи для оптимизации перебора или эффективный алгоритм решения
#include<iostream>
using namespace std;
int a[4][4];
int b[4][4];
bool cmt[32769]; //т.к. все числа различные я решил создать массив, в котором буду проверять наличие числа
bool ok=true;
int f(int n,int m){
int tmp = b[0][0]+b[0][1]+b[0][2]+b[0][3];// сумма чисел первой горизонтали
if(n > 0 && m>0){ // проверяю, чтобы сумма чисел вертикалей не была больше первой горизонтали
int t=0;
for(int i = 0;i <= n;i++){
t+= b[i][m-1];
if(t > tmp)return 0;
}
}
if(m==3 && n > 0){ // если не первая горизонталь почти собрана и не хватает одного числа, то я
// просто сразу нахожу какое число мне нужно
int t=b[n][0]+b[n][1]+b[n][2];
if(t > tmp)return 0;
else if(cmt[tmp - t]){
cmt[tmp-t]=false;
b[n][m]=tmp-t;
f(n+1,0);
b[n][m]=0;
cmt[tmp-t]=true;
return 0;
}
else return 0;
}
if(m==4)n++,m=0;
if(n==3){ // если 3 горизонтали собраны, то я могу найти числа, которые мне нужны для
// магического квадрата
int tmp = b[0][0]+b[0][1]+b[0][2]+b[0][3];
for(int i = 0;i < 4;i++){
int t = b[0][i]+b[1][i]+b[2][i];
if(t > tmp){
for(int j = 0;j<i;j++){
int t = b[0][j]+b[1][j]+b[2][j];
cmt[tmp-t]=true;
}
return 0;
}
if(cmt[tmp-t]){
cmt[tmp-t]=false;
b[3][i]=tmp-t;
}
else {
for(int j = 0;j<i;j++){
int t = b[0][j]+b[1][j]+b[2][j];
cmt[tmp-t]=true;
}
return 0;
}
}
ok = false;
for(int i = 0;i < 4;i++){
for(int j = 0;j < 4;j++){
cout<<b[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
if(n > 0){ // проверяю, чтобы сумма чисел горизонталей не была больше первой горизонтали
int t=0;
for(int i = 0;i <m;i++){
t+=b[n][i];
if(tmp < t)return 0;
}
}
for(int i = 0;i < 4 && ok;i++){
for(int j = 0;j < 4 && ok;j++){
if(cmt[a[i][j]]){
cmt[a[i][j]]=false;
b[n][m]=a[i][j];
f(n,m+1);
b[n][m]=0;
cmt[a[i][j]]=true;
}
}
}
return 0;
}
int main(){
for(int i = 0;i < 32769;i++)cmt[i]=false;
for(int i = 0;i < 4;i++){
for(int j = 0;j < 4;j++){
cin>>a[i][j];b[i][j]=0;
cmt[a[i][j]]=true;
}
}
f(0,0);
if(ok)cout<<"NO SOLUTION";
return 0;
}
Ответы (2 шт):
известная задача. Когда то ей я вывел из работы целую команду, они все мучались.
В целом. Самое первое, что Вы должны сделать, это рассчитать сумму по строке-столбце. Можно просто просуммировать все числа и поделить на 4. Если нацело не делится, то все, приплыли.
Теперь посмотрим на саму схему
1 2 3 *
5 6 7 *
9 10 11 *
* * * *
числа, отмеченные звездочками, можно очень легко посчитать. Поэтому, на самом деле нужно делать перебор для 9 чисел, а остальные 7 просто будут легко посчитаны. Но даже тут перебор можно сократить - после перебора первых трех чисел, можно почитать 4 (сумма то нам известна!) и проверить, подходит ли оно нам (оно явно не должно быть отрицательным). Этот прием очень сильно сокращает перебор. Но все равно, это много перебора.
Но если есть навыки математика, то можно понять, что такой магический квадрат это просто 16 неизвестных и 10 уравнений (4 строки, 4 столбца и 2 диагонали). А значит, у нас есть 6 свободных переменных, которые нужно перебирать. И всего вариантов на перебор - 11*12 .. *16 = 5765760 - а это уже легко поддается перебору. Но вот только уравнения нужно будет решить.
Думаю, вот такая схема будет оптимальна.
1 2 3 *
* 6 7 *
* * 11 *
* * * *
вначале можно найти числа на местах 4,15 и 16. Потом перебором подобрать числа на позиции 5, 8 и 12. А потом рекурсивно на каждый вариант проверять остаток. Я так пробовал, работает хорошо. за несколько секунд можно уложиться в поиск всех вариантов.
Второй вариант более сложен. Вначале генерируются все возможные четверки (без учета порядка. Потом перебираются четверки по три штуки и на базе этого ищется оставшаяся четверка. Потом эти четверки "перетасовываются" и подбирается такой вариант, что бы столбцы и диагонали работали. Но этот способ достаточно сложен в реализации.
Также стоит помнить, что для чисел от 1 до 16 есть 7040 вариантов вообще.
А также почитайте, как это делают на gpu https://habr.com/ru/post/424845/
P.S.
Если просто перебирать первую строку, то это 13*14*15*16 = 43680, если перебирать только 3 числа, а 4 вычислять, то это уже 3360. Если делать отсечку дубликатов, то есть всего то 1992 вариантов первой строки. Круто же.
Оценим число комбинаций чисел, которые перебирает ваша программа. Я добавил в вашу программу счётчик вызовов функции f, подал на вход комбинацию чисел для которой квадрата нет и через полминуты получил такую таблицу:
i j # вызовов комментарий
----------------------------------------------------
0 0 1
0 1 16 перебираем все 16 вариантов
0 2 240 и ещё 15 оставшихся
0 3 3360 и ещё 14
1 0 43680 и ещё 13
1 1 524160 и ещё 12
1 2 5411736 ! первый раз множитель меньше максимального (11) 10.3246
1 3 48912000 множитель 9.0381 < 10
2 0 10000440 ! первая существенная оптимизация
2 1 80003520
2 2 430306744
2 3 1927687584
3 0 192920976
3 1 0
3 2 0
3 3 0
Перебор слишком свободный, а потому медленный. Нужно сузить его как можно сильнее.
Пусть мы построили квадрат у которого самый маленький элемент не в левом верхнем углу. Тогда переставляя столбцы и строки его можно туда переместить сохраняя "магичность" (напомню что на диагонали условий нет).
Если верхняя строка не упорядочена по возрастанию, переставим столбцы чтобы числа росли. Тоже сделаем с первым столбцом.
Квадрат останется квадратом если его транспонировать. Из двух вариантов выберем тот где a[1][0] > a[0][1] (нотация будет a[0 <= row <= 3][0 <= col <= 3]).
Порядок перебора полей так же влияет на количество вариантов. Я буду перебирать поля так:
1 2 3 4 # правила: 1: a[0][0] = min(values)
* * * * # 3: a[0][2] > a[0][1]
* * * * # 4: a[0][0] + a[0][1] + a[0][2] + a[0][3] = sum(values) / 4
* * * * # 4: a[0][3] > a[0][2]
Первый элемент - фиксированный минимальный. Элементы в строке растут. Сумма строки равна четверти суммы всех значений. Это самое важное правило - отсекаем варианты как только построили строку.
Далее первый столбец:
1 2 3 4 # правила: 5: a[1][0] > a[0][1]
5 * * * # 6: a[2][0] > a[1][0]
6 * * * # 7: a[0][0] + a[1][0] + a[2][0] + a[3][0] = sum(values) / 4
7 * * * # 7: a[3][0] > a[2][0]
Элементы в столбце растут. Сумма столбца сами знаете какая. Правило для пятого элемента запрещает транспонировать квадрат.
Вторая строка:
1 2 3 4 # правило: 10: a[1][0] + a[1][1] + a[1][2] + a[1][3] = sum(values) / 4
5 8 9 10 #
6 * * * #
7 * * * #
Удаётся проверить только один элемент - десятый. На другие условий нет.
Второй столбец:
1 2 3 4 # правило: 12: a[0][1] + a[1][1] + a[2][1] + a[3][1] = sum(values) / 4
5 8 9 10 #
6 11 * * #
7 12 * * #
Снова только одна проверка.
Оставшиеся ячейки:
1 2 3 4 # правила: 14: a[2][0] + a[2][1] + a[2][2] + a[2][3] = sum(values) / 4
5 8 9 10 # 15: a[0][2] + a[1][2] + a[2][2] + a[3][2] = sum(values) / 4
6 11 13 14 #
7 12 15 16 #
Проверяем сумму в третьих строке и столбце. Суммы для четвёртых строки и столбца я не проверяю. Они верны автоматом. Нам известно что первые три строки имеют правильные суммы. Тогда сумма четвертой вычисляется из полной суммы.
Новый порядок перебора и более строгие правила приводят к такой таблице вызовов:
i j # вызовов комментарий
----------------------------------------------------
0 0 1
0 1 1 в углу фиксированное число
0 2 15 перебираем все 15 вариантов
0 3 105 вариантов 14 но порядок в строке оставляет 7
1 0 9 ! экономия из-за проверки суммы первой строки
2 0 69
3 0 293
1 1 19 проверка суммы первого столбца
1 2 171
1 3 1368
2 1 438 проверка суммы второй строки
3 1 2628
2 2 352 проверка суммы второго столбца
2 3 1408
3 2 280 проверка суммы третьей строки
3 3 0 проверка суммы третьго столбца
Видно как ранние проверки сумм уменьшают количество вызовов. Упорядочение значений первых строки и столбца также играет свою роль.
Конечно числа в таблицах могут меняться в зависимости от значений в квадрате. Эти таблицы ничего не доказывают, только иллюстрируют.
Программа на Python.
def search(values):
s = sum(values)
if s % 4 != 0:
return
target = s // 4
a = [[None] * 4 for _ in range(4)]
def a00():
yield min(values)
def a01():
yield from tuple(values)
def a02():
for v in tuple(values):
if v > a[0][1]:
yield v
def a03():
v = target - sum(a[0][i] for i in range(3))
if v > a[0][2] and v in values:
yield v
def a10():
for v in tuple(values):
if v > a[0][1]:
yield v
def a20():
for v in tuple(values):
if v > a[1][0]:
yield v
def a30():
v = target - sum(a[i][0] for i in range(3))
if v > a[2][0] and v in values:
yield v
def a11():
yield from tuple(values)
def a12():
yield from tuple(values)
def a13():
v = target - sum(a[1][i] for i in range(3))
if v in values:
yield v
def a21():
yield from tuple(values)
def a31():
v = target - sum(a[i][1] for i in range(3))
if v in values:
yield v
def a22():
yield from tuple(values)
def a23():
v = target - sum(a[2][i] for i in range(3))
if v in values:
yield v
def a32():
v = target - sum(a[i][2] for i in range(3))
if v in values:
yield v
def a33():
yield from values
route = (
(0, 0, a00), (0, 1, a01), (0, 2, a02), (0, 3, a03),
(1, 0, a10), (2, 0, a20), (3, 0, a30),
(1, 1, a11), (1, 2, a12), (1, 3, a13),
(2, 1, a21), (3, 1, a31),
(2, 2, a22), (2, 3, a23), (3, 2, a32),
(3, 3, a33)
)
def search(k):
if k == len(route):
yield a
return
i, j, f = route[k]
for v in f():
values.remove(v)
a[i][j] = v
yield from search(k + 1)
a[i][j] = None
values.add(v)
yield from search(0)
values = set(map(int, (w for _ in range(4) for w in input().split())))
for row in next(iter(search(values)), [['NO SOLUTION']]):
print(*row)
$ cat input-1-16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 $ time python make-magic-square.py < input-1-16 1 2 15 16 6 11 10 7 13 9 4 8 14 12 5 3 real 0m0.026s user 0m0.016s sys 0m0.012s $ cat input-1-28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 28 $ time python make-magic-square.py < input-1-28 NO SOLUTION real 0m0.035s user 0m0.032s sys 0m0.004s