Небьющие друг друга

НЕБЬЮЩИЕ ДРУГ ДРУГА ФЕРЗИ И ДРУГИЕ

С 1848г. ведет свою историю задача: расставить на шахматной
доске 8 ферзей так, чтобы ни один из них не бил другого. Десяток-другой
решений этой задачи нетрудно найти непосредственно за шахматной
доской. Для нахождения всех 92 решений, нужны логика и упорство (чего
хватало и в XIX веке), либо ЭВМ. Не случайно только в 1874г. ученым
удалось доказать, что решений ровно 92. Правда, после удаления
зеркальных и получаемых поворотом из них остается только 12.
На схожий мотив появилась следующая задача: расставить на
шахматной доске 6 ферзей, 6 ладей, 6 коней и 6 слонов так, чтобы ни
одна из фигур не била более или равноценную. Т.е. разрешается, например,
чтобы ладья била коня или слона, но ладья не должна бить другую ладью
или ферзя. Здесь тоже немало решений можно найти вручную. Но чтобы
посчитать их общее количество - без ЭВМ нечего делать. Всего их
108234248 штук. Подсчет на Pentium-1 занимает 45 минут. (А может быть,
у вас меньше?)
Если увеличить количество фигур каждого вида до семи, то
решений вообще не оказывается. Промежуточные варианты тоже приводят
либо к слишком большому числу решений, либо к их полному отсутствию.

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

Наиболее примечательным и трудоемким (13 часов расчета)
оказался случай 11 коней и 13 ферзей. Такая задача имеет единственное
(с точностью до поворота и симметрии) расположение ферзей, а размещение
коней допускает назначительные вариции (указанные в скобках).
Ферзи: a2,a6,a8,b4,c1,c7,d4,f1,f7,g3,g5,h1,h7;
табун коней: a4,a7,b7,c4,d1(e1),d7(e7),f4,g1,g4,g7,h4.
Со всеми вариациями и поворотами получается 32 решения.

Заслуживают внимания также следующие случаи, где решения
единственны или "почти единственны".

16 коней, 18 ладей - 2 решения (1 час).
А с точностью до поворота 1 решение:
Кa2,a6,b1,b5,c4,c8,d3,d7,e2,e6,f1,f5,g4,g8,h3,h7;
Лa1,a4,a8,b3,b7,c2,c6,d1,d5,e4,e8,f3,f7,g2,g6,h1,h5,h8.

9 слонов, 7 коней, 7 ферзей - 32 решения (3 мин.).
Сa1,a5,b1,b8,c1,f8,g1,h1,h4; Кb5,c8,d1,e8,f1,f7,g4;
Фa4,a6,d7,e2,g8,h3,h5.

9 слонов, 8 коней, 8 ладей - 16 решений (2 мин.).
Сa1,a7,c1,d1,d8,e1,e8,f8,h2; Кa6,a8,c4,d5,e4,f5,h1,h3;
Лa2,b1,c8,d3,e6,f1,g8,h7.

10 слонов, 9 коней - 32 решения (2 мин.).
Сa1,a5,b1,b8,c1,c8,f1,f8,g1,h4; Кa4,a8,d1,d5,e8,f7,g8,h1,h5.

32 коня - 2 решения (0 мин.). Надо расставить коней по всем
черным полям, либо по всем белым. С точностью до поворота решение
единственно. Впрочем, до него нетрудно догадаться и без ЭВМ. Те же
рисунки можно посмотреть при помощи программы CH.COM, которую надо
вызывать с параметром. Например:
CH P1

Может быть, вы знаете другие оригинальные комбинации?
Или, еще лучше, умеете делать более быстрые расчеты по названным
и другим наборам фигур?
Может быть, вам знаком интересный алгоритм? Или у вас
другие достижения? Я не спрашиваю про объем программы, так как
в данном случае он не имеет большого значения. Все же по его
величине можно судить о сложности алгоритма. Для сведения: все
упомянутые выше расчеты сделаны одной программой объемом менее
2 КБ. Она же показывает шахматную доску, найденные решения,
ход расчета.

Невесенко Н.В.
12 ноября 2002 г.