Сколько таких позиций есть? (шахматная / математическая загадка)

18

Я заинтересован в такой позиции:

На доске всего 4 фигуры. Если Белые идут первыми, они могут поставить мат за один ход. Если черные идут первыми, они могут поставить мат одним ходом. Например:

пример

Вопрос в том, сколько таких позиций?

Я нахожу 3 основных позиции:

введите описание изображения здесь

Каждый из них дает нам еще 6 позиций. Мы можем переместить начальную позицию чёрной королевы на 6 других 6 клеток. Итак, у нас есть 21 базовая позиция.

введите описание изображения здесь

Есть ли другие основные позиции?

Для каждой базовой позиции мы можем:

1) переключатель цвета х2

2) повернуть доску х4

3) положение зеркала х2

Таким образом, одна базовая позиция генерирует 2x4x2 = 16 позиций. И окончательный ответ: 16x21 = 336 таких позиций.

Это правильно?

Майк
источник

Ответы:

9

Ваша вторая базовая позиция допускает еще 4 варианта помимо тех, которые вы уже дали, обозначенных следующей диаграммой:

NN - NN

Это приводит к подсчету «базовых позиций» до 25. Независимо от того, делает ли это дополнение исчерпывающий список или нет, я не совсем уверен (хотя я думаю, что это так).

В любом случае, каким бы ни было количество базовых позиций, ваша экстраполяция общего количества позиций оттуда (x2 для переключателя цвета и x8 для преобразования доски) верна, так как группа симметрии шахматной доски действительно имеет порядок 8 как подтверждено на стр. 344 этой главы, например, из Руководства по программированию ограничений . (Тем не менее, нужно быть осторожным с пересчетом здесь; см. Ниже.) Так что на данный момент я предполагаю, что ответ 25 x 16 = 400.


Я добавляю это математическое отступление, потому что вижу из вашего профиля, что вы заинтересованы в дальнейшем изучении математики. Возможно, я не говорю здесь ничего, о чем вы еще не знаете, но все равно здесь.

Обратите внимание, что есть некоторые шахматные позиции, которые будут одинаковыми при разных симметриях доски. Например, рассмотрим акт отражения по диагонали a1-h8. Эта симметрия доски, как правило, изменит данную позицию, например

Позиция

становится

Измененная позиция

Но, конечно, некоторые позиции (а именно те, которые имеют фигуры только по диагонали a1-h8) не изменяются при этой симметрии, например, позиция

Другая позиция

остается неизменным, когда мы отражаем по этой диагонали.

Из-за такого поведения, как правило, нужно быть осторожным, чтобы не переусердствовать в такой проблеме подсчета. Для вашей проблемы это означает, что вы должны быть уверены, что ни одна из ваших базовых позиций не повторяется ни при одной из (неидентичных) симметрий, поэтому наш "x 16" при получении общего количества позиций из числа базовых позиций не будет завышению. В данном случае ваши базовые позиции достаточно сложны / асимметричны, так что интуитивно понятно, что ни одна из них не будет повторяться в соответствии с этими симметриями, поэтому не о чем беспокоиться, но в математике часто бывает, когда все «интуитивно понятно», что нужно больше всего беспокоиться об ошибках. (На самом деле, есть поговорка, что если вы хотите найти ошибки в математическом доказательстве, начните с того, что говорит: «Понятно, что ...»)

расчетное время отправления
источник
1
С помощью компьютерного поиска я подтвердил, что эти 400 являются единственными такими позициями KkQq, и я не вижу никаких «хитрых» способов (например, KkPqили KkNq), поэтому я также считаю, что приведенное выше решение является полным и ответ "ровно 400".
Quuxplusone