Очередная задачка для разминки мозгов ;)

← →
MBo © (2002-11-29 10:14) [0]

Квадраты в квадрате.
Целые числа от 1 до 9 разместить в клетках квадрат 3x3 так, чтобы в нем
можно было найти максимальное количество чисел, являющихся квадратами.
Где запись квадрата может идти слева направо, справа налево,
сверху вниз и снизу вверх.
То есть если есть квадрат 169, то есть и квадраты 1,9,16 и 961.

Например:

1 2 3
4 5 6
7 8 9

здесь 5 квадратов: 1,4,9,25 и 36

из fido.golovolomka

← →
MBo © (2002-11-29 10:19) [1]

P.S. у меня получилось макс. 10 квадратов

← →
Igorek © (2002-11-29 10:37) [2]

Максимум только полный перебор однозначно определит. А вручную неинтересно. Надо программу писать. Правда вариантов куча, так что без оптимизации перебора - никак.

← →
Виктор Щербаков © (2002-11-29 10:39) [3]

MBo ©
Как бы сделать, чтобы все варианты не перебирать?
Тут ведь симметрия сплошная!

← →
Opuhshii © (2002-11-29 14:05) [4]

10 квадратов получилось, но имхо можно больше,..

← →
MBo © (2002-11-29 15:03) [5]

>Виктор Щербаков
Не знаю, как не перебирать. Я вручную прикинул - вроде больше 10 не получилось. Сделал переборную программу, не оптимизировал, даже зеркальные и повернутые не отсеивал, т.е. 9! матриц пробежал. Около 10-15 сек. считает на П600.

← →
Виктор Щербаков © (2002-11-29 16:00) [6]

Надо найти способ упорядочить множество квадратов.
Первое, что в голову приходит: располагать наименьшую из угловых цифр в строго определенном месте, например, в левом верхнем углу.
Затем, можно отражать (или не отражать) по диагонали, таким образом, чтобы в правом верхнем углу располагалась наименьшая из возможных цифр.

← →
MBo © (2002-11-29 16:24) [7]

>упорядочить множество квадратов
А принципе, эта задачу можно свести к такой:
1)
нумеруем клетки в таком порядке
а1 а2 а3
а8 а9 а4
а7 а6 а5
2)
теперь составляем такие последовательности из 8 из 9 чисел, чтобы среди них не было обратных друг к другу и закольцованных (т.е. сдвиг с переносом): если у нас есть 12345678, то 23456781,56781234 и т.п., и 87654321, 32187654 и т.п. отбрасываем.
3)
После этого расставляем полученные последовательности, начиная с a1 и с a2 по кругу, не занимая клетку a9, в которую ставим остающееся число. Таким образом получаем все несимметричные решения.
Здесь главное - пункт 2 мудро реализовать

← →
Igorek © (2002-11-29 16:28) [8]

Можно с другой стороны подойти. Сначала вычислить все квадраты вплоть до 999. Потом заполнять квадрат этими последовательностями. Похоже на составление кросворда (я когда то такую программу написал). Правда алгоритм перебора нетривиальный.

по пункту 2 (MBo 16:24) придумал пока такой метод -
чтобы не сравнивать, есть ли уже циклически сдвинутая последовательность (что нетрудно сделать с помощью логических операций сдвига и or c приведением 8-байтового массива, скажем, к Int64, но требует хранения уже полученных последовательностей), можно сделать так:
исключаем, скажем, наименьшее из 8 чисел, для остальных получаем все перестановки, после чего в начало или конец добавляем исключенное число. Таким образом получим 9*7! последовательностей. Остающаяся избыточность - обращенные последовательности.

> Виктор Щербаков © (29.11.02 16:30)
> Igorek © (29.11.02 16:28)
> ИМХО, ты всё усложнил :)))

Ваш алгоритм хорош еще для матрицы 3х3. А как для 4х4 и больше?

Прошу прощения, в программе допустил ошибку, максимальное число квадратов после ее исправления выросло ;) до 11 штук

9 4 3
2 5 6
7 8 1

1,4,9,16,25,36,49,81,256,361,729

Очередная задачка для разминки мозгов ;) Найти похожие ветки