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

← →
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. Потом заполнять квадрат этими последовательностями. Похоже на составление кросворда (я когда то такую программу написал). Правда алгоритм перебора нетривиальный.

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

← →
MBo (2002-11-29 17:35) [10]

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

← →
Igorek (2002-11-29 19:54) [11]

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

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

← →
MBo (2002-12-02 18:35) [12]

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

9 4 3
2 5 6
7 8 1

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

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