Не магические квадраты

[vladb314]

Добрый день!

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

Разумеется, речь идёт только о квадратах чётного порядка.
Для шестого порядка существует всего 5 таких квадратов (с точностью до перестановок строк и столбцов):

$ \begin{array}{cccccc} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 \end{array} $

$ \begin{array}{cccccc} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \end{array} $

$ \begin{array}{cccccc} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \end{array} $

$ \begin{array}{cccccc} 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{array} $

$ \begin{array}{cccccc} 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 \end{array} $

Квадратов 8-го порядка было найдено 6:


$ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} $

$ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} $

$ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} $

$ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} $

$ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} $

$ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} $

Думаю, что существуют ещё.

Существует ли какой-нибудь метод построения таких квадратов?

Эта задача у меня возникла из глубин теории псевдобулевой оптимизации. Я пытаюсь построить такие квадраты, у которых порядок достаточно большой и является степенью двойки, например, 1024. Буду рад услышать любую информацию по этому вопросу.

[ИСН]

http://en.wikipedia.org/wiki/Walsh_matrix



Uploaded with **invalid link**

[Nataly-Mak]

vladb314
вы построили нужные вам квадраты?
У меня есть идейка, но требует проверки.

[vladb314]

Nataly-Mak в сообщении #361916 писал(а):

vladb314
вы построили нужные вам квадраты?
У меня есть идейка, но требует проверки.

Да. Я нашёл способ, как строить такие квадраты из матриц Уолша порядка $2^n$ при нечётном $n$.

[venco]

vladb314 в сообщении #359982 писал(а):

Для шестого порядка существует всего 5 таких квадратов (с точностью до перестановок строк и столбцов):

А Вы уверены, что это разные квадраты? По крайней мере 1-й и 2-й совпадают после перестановки строк и столбцов.

[Nataly-Mak]

vladb314
А для чётных $n$ вам не надо?

Пока у меня работала программа построения магического квадрата, я на листе бумаги составила квадрат порядка 36 (можно было и порядка 64 составить, но на листе бумаги это неудобно) методом составных квадратов. За основу взяла один из ваших квадратов порядка 6.

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0
0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1
1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0
1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1
0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0
0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0
0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1
1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0
1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1
0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1
0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1
0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0
1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0
1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1
1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0
1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1
1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1
1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0
0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1
0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0
1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0
1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 0
1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1
0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1
0 0 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0
0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1
1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1
1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1
1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0
0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1
0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0

Не хочется писать программу проверки строк (столбцов) на одинаковость и противоположность. У вас, наверное, есть такая программа.
Визуально посмотрела, вроде всё нормально. Но это не точно.

Мне самой просто очень интересно, сработал метод или нет.
Что вы скажете? Получился квадрат или нет?

[vladb314]

venco в сообщении #362041 писал(а):

А Вы уверены, что это разные квадраты?

Уверен на 98%.

venco в сообщении #362041 писал(а):

По крайней мере 1-й и 2-й совпадают после перестановки строк и столбцов.

Вы можете это доказать?

-- Сб окт 16, 2010 20:46:02 --

Nataly-Mak в сообщении #362498 писал(а):

vladb314
Что вы скажете? Получился квадрат или нет?

Да, квадрат получился!

[Nataly-Mak]

Спасибо
Значит, метод работает. Запросто можно составить квадрат порядка 64, затем порядка 512 и т. д.

[venco]

vladb314 в сообщении #362710 писал(а):

venco в сообщении #362041 писал(а):

По крайней мере 1-й и 2-й совпадают после перестановки строк и столбцов.

Вы можете это доказать?

Во втором квадрате переставьте столбцы 2 и 3, затем вставьте строку 6 на место 4, и получите первый квадрат.

[vladb314]

venco в сообщении #362716 писал(а):

Во втором квадрате переставьте столбцы 2 и 3, затем вставьте строку 6 на место 4, и получите первый квадрат.

Действительно. Извиняюсь. Была ошибка в программе. Сейчас пересчитаю.

-- Сб окт 16, 2010 21:39:24 --

Пересчитал. Оказывается все эти пять квадратов получаются друг из друга перестановкой строк! Для 6-го порядка, с точностью до перестановок строк и столбцов, возможен только один такой квадрат!
Спасибо venco.