Ферзи, не бьющие друг друга

omega · Сообщение **omega** » 15 июн 2011, 08:26

Да, посмотрела в той теме внимательнее, там действительно отмечено, что решение на доске 8х8 с пустым квадратом 4х4 в центре является симметричным, а не дважды симметричным.

Ещё интересная задача о количестве расстановок как функции порядка доски, обозначим эту функцию Q(n), n - порядок доски.

Как я поняла, формула для этой функции до сих пор не найдена. Можно ли такую формулу вообще получить?

Имеем: $$Q(4) = 1, Q(8) = 12$$

.

Кто может найти $$Q(16)$$

?

У меня есть гипотеза, что $$Q(16) = 40$$

.
Конечно, имеются в виду только разные решения, не получающиеся друг из друга поворотами и отражениями.
Гипотеза фонарная
Есть у кого обоснованные гипотезы?

Рассмотрим пока $$Q(2^m)$$

.

omega · Сообщение **omega** » 15 июн 2011, 09:24

Заглянула в Википедию, в статью "Задача о восьми ферзях".

Там дана такая математическая формулировка задачи:

«Заполнить матрицу размером 8х8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».

Я бы сформулировала задачу так:

Заполнить матрицу 8х8 нулями и единицами таким образом, чтобы сумма элементов в любой строке и в любом столбце матрицы была равна 1, а сумма элементов в главных диагоналях равна 0 или 1.

Получается близкий мне полумагический квадрат 8х8.

Понравился в статье эвристический алгоритм. Он даёт возможность найти хотя бы одну расстановку. Попробовала по этому алгоритму для n=16. Получилось очень просто, расстановка самая простая и очевидная:

Код: Выбрать все

_ _ _ _ _ _ _ _ x _ _ _ _ _ _ _
x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
_ _ _ _ _ _ _ _ _ x _ _ _ _ _ _
_ x _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ x _ _ _ _ _
_ _ x _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ x _ _ _ _
_ _ _ x _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ x _ _ _
_ _ _ _ x _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ x _ _
_ _ _ _ _ x _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ x _
_ _ _ _ _ _ x _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x
_ _ _ _ _ _ _ x _ _ _ _ _ _ _ _

Ну вот, одна расстановка есть для n=16. Кто ещё найдёт?

Похоже моя гипотеза $$Q(16) = 40$$

абсолютно не верна. Сейчас посмотрела в книге Гарднера: $$Q(9) = 46, Q(10) = 92$$

.
Забираю свою плохую гипотезу назад.

СергейП

Темы объединены. Теперь удобнее стало.

Посмотрел, что было посчитано. По ферзям табличка такая

n - размерность доски
K - число расстановок
Из них - 2 - дваждысимметричные, 1 - симметричные, 0 - простые.
Обычно считают принято считать общее число позиций с поворотами и отражениями, это последний столбец.

Таблица по магараджам такая

omega · Сообщение **omega** » 15 июн 2011, 17:48

Хорошие результаты.
Однако моя задача о расстановке с пустым центральным квадратом пока осталась не решённой.

Я тут сейчас искала шаблоны для построения пандиагональных квадратов 7-го порядка из простых чисел. Нашла два классных шаблона из вычетов по модулю 7, один для регулярных квадратов, другой для не регулярных.
Так вот ведь чудеса какие: в обоих шаблонах вычеты 4 и 6 расставлены как ферзи, не бьющие друг друга

Шаблон для регулярного квадрата:

Код: Выбрать все

4 5 5 6 3 3 3
6 3 3 3 4 5 5
3 4 5 5 6 3 3
5 6 3 3 3 4 5
3 3 4 5 5 6 3
5 5 6 3 3 3 4
3 3 3 4 5 5 6

Шаблон для не регулярного квадрата:

Код: Выбрать все

4 6 3 5 3 5 3
3 5 3 4 6 3 5
6 3 5 3 5 3 4
5 3 4 6 3 5 3
3 5 3 5 3 4 6
3 4 6 3 5 3 5
5 3 5 3 4 6 3

omega · Сообщение **omega** » 16 июн 2011, 02:19

Если порядок доски n не делится на 2 или на 3, то n решений можно наложить друг на друга так, что ферзи заполнят все клетки доски. Например, на доске 5х5 можно разместить 25 ферзей (по 5 ферзей 5 различных цветов) так, что никакие ферзи одного цвета не будут атаковать друг друга.

(из книги М. Гарднера "Математические досуги")

Как такая задачка? Простая или не очень? Между прочим, получается ...
Не скажу пока, что получается

Итак, начали...

Код: Выбрать все

_ 1 _ _ _
_ _ _ _ 1
_ _ 1 _ _
1 _ _ _ _
_ _ _ 1 _

Это одно решение, дважды симметричное.

Пусть будет:
0 - красные ферзи, 1 - оранжевые, 2 - жёлтые, 3 - зелёные, 4 - голубые.

Расставить остальные 20 ферзей.

Сколько разных решений для порядка 5?

Для порядка 7 49 ферзей надо расставить 7 различных цветов, чтобы ферзи одинакового цвета не били друг друга. Сколько разных решений?

7 цветов - это как раз радуга

0 - красные
1 - оранжевые
2 - жёлтые
3 - зелёные
4 - голубые
5 - синие
6 - фиолетовые

Сделаем радугу на шахматной доске :rolleyes:

Ukor · Сообщение **Ukor** » 15 фев 2012, 17:38

omega писал(а):Source of the post
Если порядок доски n не делится на 2 или на 3, то n решений можно наложить друг на друга так, что ферзи заполнят все клетки доски. Например, на доске 5х5 можно разместить 25 ферзей (по 5 ферзей 5 различных цветов) так, что никакие ферзи одного цвета не будут атаковать друг друга.

(из книги М. Гарднера "Математические досуги")

Как такая задачка? Простая или не очень? Между прочим, получается ...
Не скажу пока, что получается

Итак, начали...

Код: Выбрать все
_ 1 _ _ _ _ _ _ _ 1 _ _ 1 _ _ 1 _ _ _ _ _ _ _ 1 _

Это одно решение, дважды симметричное.

Пусть будет:
0 - красные ферзи, 1 - оранжевые, 2 - жёлтые, 3 - зелёные, 4 - голубые.

Расставить остальные 20 ферзей.

Сколько разных решений для порядка 5?

Для порядка 7 49 ферзей надо расставить 7 различных цветов, чтобы ферзи одинакового цвета не били друг друга. Сколько разных решений?

7 цветов - это как раз радуга

0 - красные
1 - оранжевые
2 - жёлтые
3 - зелёные
4 - голубые
5 - синие
6 - фиолетовые

Сделаем радугу на шахматной доске :rolleyes:

Ukor
Для доски 5*5 имеется 2 решения.
Все 10 позиций участвуют.

1 : 1 3 5 2 4
2 : 1 4 2 5 3
3 : 2 4 1 3 5
4 : 2 5 3 1 4
5 : 3 1 4 2 5
6 : 3 5 2 4 1
7 : 4 1 3 5 2
8 : 4 2 5 3 1
9 : 5 2 4 1 3
10 : 5 3 1 4 2

1 3 5 2 4 :1
2 4 1 3 5 :3
3 5 2 4 1 :6
4 1 3 5 2 :7
5 2 4 1 3 :9

1 4 2 5 3 :2
2 5 3 1 4 :4
3 1 4 2 5 :5
4 2 5 3 1 :8
5 3 1 4 2 :10

Для доски 7*7 имеется 4 решения.
Сначала все позиции для доски 7*7:

1 a 1 b 3 c 5 d 7 e 2 f 4 g 6

2 a 1 b 4 c 7 d 3 e 6 f 2 g 5

3 a 1 b 5 c 2 d 6 e 3 f 7 g 4

4 a 1 b 6 c 4 d 2 e 7 f 5 g 3

5 a 2 b 4 c 1 d 7 e 5 f 3 g 6

6 a 2 b 4 c 6 d 1 e 3 f 5 g 7

7 a 2 b 5 c 1 d 4 e 7 f 3 g 6

8 a 2 b 5 c 3 d 1 e 7 f 4 g 6

9 a 2 b 5 c 7 d 4 e 1 f 3 g 6

10 a 2 b 6 c 3 d 7 e 4 f 1 g 5

11 a 2 b 7 c 5 d 3 e 1 f 6 g 4

12 a 3 b 1 c 6 d 2 e 5 f 7 g 4

13 a 3 b 1 c 6 d 4 e 2 f 7 g 5

14 a 3 b 5 c 7 d 2 e 4 f 6 g 1

15 a 3 b 6 c 2 d 5 e 1 f 4 g 7

16 a 3 b 7 c 2 d 4 e 6 f 1 g 5

17 a 3 b 7 c 4 d 1 e 5 f 2 g 6

18 a 4 b 1 c 3 d 6 e 2 f 7 g 5

19 a 4 b 1 c 5 d 2 e 6 f 3 g 7

20 a 4 b 2 c 7 d 5 e 3 f 1 g 6

21 a 4 b 6 c 1 d 3 e 5 f 7 g 2

22 a 4 b 7 c 3 d 6 e 2 f 5 g 1

23 a 4 b 7 c 5 d 2 e 6 f 1 g 3

24 a 5 b 1 c 4 d 7 e 3 f 6 g 2

25 a 5 b 1 c 6 d 4 e 2 f 7 g 3

26 a 5 b 2 c 6 d 3 e 7 f 4 g 1

27 a 5 b 3 c 1 d 6 e 4 f 2 g 7

28 a 5 b 7 c 2 d 4 e 6 f 1 g 3

29 a 5 b 7 c 2 d 6 e 3 f 1 g 4

30 a 6 b 1 c 3 d 5 e 7 f 2 g 4

31 a 6 b 2 c 5 d 1 e 4 f 7 g 3

32 a 6 b 3 c 1 d 4 e 7 f 5 g 2

33 a 6 b 3 c 5 d 7 e 1 f 4 g 2

34 a 6 b 3 c 7 d 4 e 1 f 5 g 2

35 a 6 b 4 c 2 d 7 e 5 f 3 g 1

36 a 6 b 4 c 7 d 1 e 3 f 5 g 2

37 a 7 b 2 c 4 d 6 e 1 f 3 g 5

38 a 7 b 3 c 6 d 2 e 5 f 1 g 4

39 a 7 b 4 c 1 d 5 e 2 f 6 g 3

40 a 7 b 5 c 3 d 1 e 6 f 4 g 2

Теперь позиции заполнения:

1 3 5 7 2 4 6 :1

2 4 6 1 3 5 7 :6

3 5 7 2 4 6 1 :14

4 6 1 3 5 7 2 :21

5 7 2 4 6 1 3 :28

6 1 3 5 7 2 4 :30

7 2 4 6 1 3 5 :37

1 4 7 3 6 2 5 :2

2 5 1 4 7 3 6 :7

3 6 2 5 1 4 7 :15

4 7 3 6 2 5 1 :22

5 1 4 7 3 6 2 :24

6 2 5 1 4 7 3 :31

7 3 6 2 5 1 4:38

1 5 2 6 3 7 4 :3

2 6 3 7 4 1 5 :10

3 7 4 1 5 2 6 :17

4 1 5 2 6 3 7 :19

5 2 6 3 7 4 1 :26

6 3 7 4 1 5 2 :34

7 4 1 5 2 6 3 :39

1 6 4 2 7 5 3 :4

2 7 5 3 1 6 4 :11

3 1 6 4 2 7 5 :13

4 2 7 5 3 1 6 :20

5 3 1 6 4 2 7 :27

6 4 2 7 5 3 1 :35

7 5 3 1 6 4 2 :40

omega · Сообщение **omega** » 17 фев 2012, 06:23

Ukor писал(а):Source of the post
Для доски 5*5 имеется 2 решения.

1 3 5 2 4 :1
2 4 1 3 5 :3
3 5 2 4 1 :6
4 1 3 5 2 :7
5 2 4 1 3 :9

1 4 2 5 3 :2
2 5 3 1 4 :4
3 1 4 2 5 :5
4 2 5 3 1 :8
5 3 1 4 2 :10

Да! И получились ортогональные диагональные латинские квадраты 5-го порядка. Их как раз два и существует в природе

Ukor · Сообщение **Ukor** » 19 фев 2012, 08:33

omega писал(а):Source of the post
Ukor писал(а):Source of the post
Для доски 5*5 имеется 2 решения.

1 3 5 2 4 :1
2 4 1 3 5 :3
3 5 2 4 1 :6
4 1 3 5 2 :7
5 2 4 1 3 :9

1 4 2 5 3 :2
2 5 3 1 4 :4
3 1 4 2 5 :5
4 2 5 3 1 :8
5 3 1 4 2 :10

Да! И получились ортогональные диагональные латинские квадраты 5-го порядка. Их как раз два и существует в природе

И из них можно получить магические квадраты, по известнсй формуле:
c=n*(a-1)+b
c - число в клетке магического квадрата
n - порядок квадрата
a и b - числа в соответствующих клетках ортогональных
латинских квадратов

1 18 10 22 14
7 24 11 3 20
13 5 17 9 21
19 6 23 15 2
25 12 4 16 8

1 14 22 10 18
7 20 3 11 24
13 21 9 17 5
10 2 15 23 6
25 8 16 4 12

Эти магические квадраты -- пандиагональные.

Для доски 7*7 латинские квадраты тоже получаются
диагональные и ортогональные.

omega · Сообщение **omega** » 21 фев 2012, 14:48

Ukor писал(а):Source of the post
И из них можно получить магические квадраты, по известнсй формуле:
c=n*(a-1)+b

Это вы метод латинских квадратов рассказали
Он очень хорошо известен (по крайней мере, всем, кто занимается квадратами).

Ukor · Сообщение **Ukor** » 22 апр 2012, 13:33

omega писал(а):Source of the post
Ukor писал(а):Source of the post
И из них можно получить магические квадраты, по известнсй формуле:
c=n*(a-1)+b

Это вы метод латинских квадратов рассказали
Он очень хорошо известен (по крайней мере, всем, кто занимается квадратами).

Программу получающую эти группы и другие программы на тему форума можно посмотреть
на сайте: nabasice.narod2.ru

yourdomain.com