Ферзи на доске 6×6

Автор темы xenia1996 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
28.03.2021 23:44
Ферзи на доске 6×6
Какое наибольшее число ферзей можно расставить на шахматной доске размером 6×6 так, чтобы каждый из них бил ровно 1 ферзя?

-----------------------------------------------------

И не ракета орлиная Таню берегла, и дни лежат в небе тем лесом.

Наш Вася Тараканечкин променял-таки Кацечку на Тацечку (Кацечка и Тацечка — это общеславянские ласкательные варианты имён Екатерина и Татьяна (Тетяна) соответственно).
29.03.2021 11:17
//
Цитата
xenia1996
Какое наибольшее число ферзей можно расставить на шахматной доске размером 6×6 так, чтобы каждый из них бил ровно 1 ферзя?

Неинтересная задача для тупого компьютерного перебора..
07.04.2021 18:46
Матрицы
Лучше подумайте какой модулярной конструкцией пользовался создатель шахмат ?

Думаю никто такой вопрос не ставил ,но знание этой конструкций может решит многие

проблемы теории чисел.



Редактировалось 1 раз(а). Последний 07.04.2021 18:47.
10.04.2021 23:16
Решение в Maple
Ниже компьютерное решение в Maple. Процедура Qweens работает для произвольной доски m x n и возвращает полный набор решений. Положение ферзей кодируется их координатами на целочисленной решётке от (1,1) до (n,m) .

restart;
Qweens:=proc(m,n)
local S, P, P1,S1, S2, L, k, s, i, t, j, n1, n2, N, L1;
uses combinat;
S:={seq(seq([i,j],j=1..m),i=1..n)};

P:=proc(p,q)
if p[1]=q[1] or p[2]=q[2] or p[2]-p[1]=q[2]-q[1] or p[2]+p[1]=q[2]+q[1] then return true else false fi;
end proc;
P1:=proc(s,t)
if (not P(s[1],t[1])) and (not P(s[1],t[2])) and (not P(s[2],t[1])) and (not P(s[2],t[2])) then true else false fi;
end proc;

S1:=choose(S,2);
S2:=select(t->P(t[1],t[2]), S1);
n1:=nops(S2);

L[0]:={}; L[1]:=map(t->{t},S2);

for k from 1 while L[k-1]<>L[k] do
n2:=nops(L[k]);
N:=0:
for i from 1 to n1 do
for j from 1 to n2 do
if andmap(p->P1(S2,p), L[k][j]) then N:=N+1; L[k+1][N]:={S2} union L[k][j] fi;
od: od:
L[k+1]:=`if`(N<>0,convert(L[k+1],set),L[k]):
od;

L[k];

end proc:


Пример работы процедуры для доски 6 на 6:

L:=Qweens(6,6);
nops(L);

L := { {{[1, 2], [1, 3]}, {[2, 6], [3, 6]}, {[4, 1], [5, 1]}, {[6, 4], [6, 5]}},
{{[1, 2], [1, 4]}, {[2, 6], [4, 6]}, {[3, 1], [5, 1]}, {[6, 3], [6, 5]}},
{{[1, 3], [1, 5]}, {[2, 1], [4, 1]}, {[3, 6], [5, 6]}, {[6, 2], [6, 4]}},
{{[1, 4], [1, 5]}, {[2, 1], [3, 1]}, {[4, 6], [5, 6]}, {[6, 2], [6, 3]}} }
4

Мы получаем 4 решения. Для каждого решения бьющие друг друга ферзи объединены в пары.

Картинка по ссылке:
https://b.radikal.ru/b01/2104/f9/a9aae3b4deb2.png

Процедура основана на полном переборе всех вариантов, поэтому для достаточно больших m и n время работы процедуры может оказаться значительным. Если для доски 6 на 6 требуется примерно 15 секунд, то для доски 8 на 8 уже примерно 1,5 часа. Для такой доски будет 376 решений с 10 ферзями. Ниже одно из решений:

https://c.radikal.ru/c20/2104/b1/330dfc5fa079.png



Редактировалось 3 раз(а). Последний 11.04.2021 09:25.
11.04.2021 06:36
..
Нормально..
Можно для конкретной доски устанавливать очевидные верхние и нижние границы, чтобы уменьшить перебор.
Вот их обоснование может иметь какой-то интерес..



Редактировалось 1 раз(а). Последний 11.04.2021 06:41.
11.04.2021 06:46
..
Кстати, насчет 4-рех решений, - по-моему, здесь 2 решения, так как, думается, свойство зеркальной симметрии для этой задачи является фундаментальным. По-крайней мере, для квадратных досок. Вроде бы и для прямоугольных то же должно соблюдаться..
Интересно, что там для 6х7, например?..
11.04.2021 07:44
Re
Для доски 6x7 будет 50 решений. Конечно среди них будет много симметричных, но этот вопрос требует отдельного исследования. Я знаю как это автоматизировать, просто возиться с этим не хочется.

{{{[1, 1], [3, 1]}, {[2, 4], [2, 5]}, {[5, 6], [7, 6]}, {[6, 2], [6, 3]}}, {{[1, 1], [5, 1]}, {[2, 3], [4, 3]}, {[3, 5], [3, 6]}, {[6, 4], [7, 4]}}, {{[1, 2], [1, 3]}, {[2, 6], [3, 6]}, {[4, 1], [5, 1]}, {[6, 4], [6, 5]}}, {{[1, 2], [1, 3]}, {[2, 6], [3, 6]}, {[4, 1], [5, 1]}, {[6, 4], [7, 5]}}, {{[1, 2], [1, 3]}, {[2, 6], [3, 6]}, {[4, 1], [5, 1]}, {[6, 5], [7, 5]}}, {{[1, 2], [1, 3]}, {[2, 6], [3, 6]}, {[4, 1], [6, 1]}, {[5, 5], [7, 5]}}, {{[1, 2], [1, 3]}, {[2, 6], [3, 6]}, {[5, 1], [6, 1]}, {[7, 4], [7, 5]}}, {{[1, 2], [1, 4]}, {[2, 6], [4, 6]}, {[3, 1], [5, 1]}, {[6, 3], [6, 5]}}, {{[1, 2], [1, 4]}, {[2, 6], [4, 6]}, {[3, 3], [5, 1]}, {[6, 5], [7, 5]}}, {{[1, 2], [2, 2]}, {[3, 6], [4, 6]}, {[5, 1], [5, 3]}, {[6, 5], [7, 4]}}, {{[1, 2], [2, 2]}, {[3, 6], [4, 6]}, {[5, 1], [6, 1]}, {[7, 4], [7, 5]}}, {{[1, 2], [2, 2]}, {[3, 6], [5, 4]}, {[4, 1], [6, 1]}, {[7, 3], [7, 5]}}, {{[1, 2], [2, 3]}, {[3, 6], [4, 6]}, {[5, 1], [6, 1]}, {[7, 4], [7, 5]}}, {{[1, 2], [3, 2]}, {[2, 4], [2, 6]}, {[5, 5], [7, 5]}, {[6, 1], [6, 3]}}, {{[1, 2], [3, 2]}, {[2, 6], [4, 6]}, {[5, 1], [6, 1]}, {[7, 4], [7, 5]}}, {{[1, 2], [7, 2]}, {[2, 4], [2, 6]}, {[3, 1], [4, 1]}, {[5, 5], [6, 5]}}, {{[1, 2], [7, 2]}, {[2, 5], [3, 5]}, {[4, 1], [5, 1]}, {[6, 4], [6, 6]}}, {{[1, 2], [7, 2]}, {[2, 5], [6, 5]}, {[3, 1], [5, 1]}, {[4, 4], [4, 6]}}, {{[1, 2], [7, 2]}, {[2, 5], [6, 5]}, {[3, 3], [5, 3]}, {[4, 1], [4, 6]}}, {{[1, 3], [1, 5]}, {[2, 1], [4, 1]}, {[3, 4], [5, 6]}, {[6, 2], [7, 2]}}, {{[1, 3], [1, 5]}, {[2, 1], [4, 1]}, {[3, 6], [5, 6]}, {[6, 2], [6, 4]}}, {{[1, 3], [2, 2]}, {[3, 4], [3, 6]}, {[4, 1], [5, 1]}, {[6, 5], [7, 5]}}, {{[1, 3], [2, 3]}, {[3, 6], [7, 6]}, {[4, 4], [6, 4]}, {[5, 1], [5, 2]}}, {{[1, 3], [7, 3]}, {[2, 1], [6, 1]}, {[3, 6], [5, 6]}, {[4, 2], [4, 4]}}, {{[1, 3], [7, 3]}, {[2, 6], [6, 6]}, {[3, 4], [5, 4]}, {[4, 1], [4, 2]}}, {{[1, 4], [1, 5]}, {[2, 1], [3, 1]}, {[4, 6], [5, 6]}, {[6, 2], [6, 3]}}, {{[1, 4], [1, 5]}, {[2, 1], [3, 1]}, {[4, 6], [5, 6]}, {[6, 2], [7, 2]}}, {{[1, 4], [1, 5]}, {[2, 1], [3, 1]}, {[4, 6], [5, 6]}, {[6, 3], [7, 2]}}, {{[1, 4], [1, 5]}, {[2, 1], [3, 1]}, {[4, 6], [6, 6]}, {[5, 2], [7, 2]}}, {{[1, 4], [1, 5]}, {[2, 1], [3, 1]}, {[5, 6], [6, 6]}, {[7, 2], [7, 3]}}, {{[1, 4], [2, 4]}, {[3, 1], [7, 1]}, {[4, 3], [6, 3]}, {[5, 5], [5, 6]}}, {{[1, 4], [2, 5]}, {[3, 1], [3, 3]}, {[4, 6], [5, 6]}, {[6, 2], [7, 2]}}, {{[1, 4], [7, 4]}, {[2, 1], [6, 1]}, {[3, 3], [5, 3]}, {[4, 5], [4, 6]}}, {{[1, 4], [7, 4]}, {[2, 6], [6, 6]}, {[3, 1], [5, 1]}, {[4, 3], [4, 5]}}, {{[1, 5], [2, 4]}, {[3, 1], [4, 1]}, {[5, 6], [6, 6]}, {[7, 2], [7, 3]}}, {{[1, 5], [2, 5]}, {[3, 1], [4, 1]}, {[5, 4], [5, 6]}, {[6, 2], [7, 3]}}, {{[1, 5], [2, 5]}, {[3, 1], [4, 1]}, {[5, 6], [6, 6]}, {[7, 2], [7, 3]}}, {{[1, 5], [2, 5]}, {[3, 1], [5, 3]}, {[4, 6], [6, 6]}, {[7, 2], [7, 4]}}, {{[1, 5], [3, 5]}, {[2, 1], [2, 3]}, {[5, 2], [7, 2]}, {[6, 4], [6, 6]}}, {{[1, 5], [3, 5]}, {[2, 1], [4, 1]}, {[5, 6], [6, 6]}, {[7, 2], [7, 3]}}, {{[1, 5], [7, 5]}, {[2, 1], [2, 3]}, {[3, 6], [4, 6]}, {[5, 2], [6, 2]}}, {{[1, 5], [7, 5]}, {[2, 2], [3, 2]}, {[4, 6], [5, 6]}, {[6, 1], [6, 3]}}, {{[1, 5], [7, 5]}, {[2, 2], [6, 2]}, {[3, 4], [5, 4]}, {[4, 1], [4, 6]}}, {{[1, 5], [7, 5]}, {[2, 2], [6, 2]}, {[3, 6], [5, 6]}, {[4, 1], [4, 3]}}, {{[1, 6], [3, 6]}, {[2, 2], [2, 3]}, {[5, 1], [7, 1]}, {[6, 4], [6, 5]}}, {{[1, 6], [5, 6]}, {[2, 4], [4, 4]}, {[3, 1], [3, 2]}, {[6, 3], [7, 3]}}, {{[2, 2], [2, 3]}, {[3, 6], [4, 6]}, {[5, 1], [6, 1]}, {[7, 4], [7, 5]}}, {{[2, 2], [2, 4]}, {[3, 6], [5, 6]}, {[4, 1], [6, 1]}, {[7, 3], [7, 5]}}, {{[2, 3], [2, 5]}, {[3, 1], [5, 1]}, {[4, 6], [6, 6]}, {[7, 2], [7, 4]}}, {{[2, 4], [2, 5]}, {[3, 1], [4, 1]}, {[5, 6], [6, 6]}, {[7, 2], [7, 3]}}}
11.04.2021 08:04
..
kitonum, спасибо!
Да, похоже, из-за симметрии, общее количество решений всегда будет четным..



Редактировалось 1 раз(а). Последний 11.04.2021 08:05.
13.04.2021 09:30
a^30
Если построить неким модулем то намного интереснее и увидите абстракцию
математика который на базе модулярной конструкции создал шахматы .
А комбинаторика внутри модуля почти полностью известна теории чисел и конечно получите истинную симметрию чисел .
Какой модулярный строй чисел вы бы выбрали для шахмат ?
14.04.2021 17:58
.
.



Редактировалось 1 раз(а). Последний 14.04.2021 18:53.
14.04.2021 18:39
.
.



Редактировалось 2 раз(а). Последний 14.04.2021 18:53.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти