Теперь когда награда обещанная уважаемым @vvvphoenixв исходной статье здесь нашла своего героя, можно рассмотреть действительный способ решения задачи, а заодно посмотреть как красивые картинки и умные слова уводят нас в сторону от настоящего решения задачи.
На самом деле я не изменил своего мнения и предыдущая статья:
Винтик и Шпунтик осваивают квантовые вычисления
заслуживает самой высокой оценки, потому что это все таки статья, а не математический труд. Но я все таки предлагаю попробовать рассмотреть один из математических методов решения задачи которая там рассматривается только в качестве вступления к основной теме более подробно.
Есть такая широко известная в узких кругах книжка
The Leprechauns of Software Engineering
про то как создаются мифы в IT отрасли. В этой книжке говорится что ошибки в статье с красивыми картинками и формулами приносят индустрии гораздо больше вреда, потому что глядя на красивую обертку люди более склонны верить в качество содержимого.
Красивые термины
Начнем пожалуй с рассмотрения красивого названия задачи, расстановка не бьющих друг друга ладей (имеется ввиду на поле квадратной матрицы). Согласитесь звучит красиво и даже романтично, только мы должны определить чисто математически что же это значит. Но как раз математического определения почему то нигде не приводится. Ведь с точки зрения математики важно именно посчитать что ладьи не бьют друг друга при расстановке на поле, как это сделать? Очень просто, если в клетки-ячейки расположения ладей записать единицы, а в свободные клетки нули, то если сумма посчитанная для каждого столбца и строки не превышает единицы это как раз и значит что ладьи стоят так, что не бьют друг друга.
Другой замечательный термин, который совершенно обоснованно приводит автор предыдущей статьи это перманент матрицы. Термин звучит настолько научно и даже я бы сказал аристократично, что мы невольно проникаемся абсолютным доверием ко всему что напишет дальше автор, то есть такого рода термины очень способствует отключению критического восприятия у читателя (я конечно описываю только свое восприятие, но думаю в какой то степени так происходит у многих, но наверняка не у всех).
Так вот как раз с этим самым многоуважаемым перманентом связана первая может быть не совсем ошибка, но неточность тем не менее не допустимая для математических построений. Автор предлагает нам искать перманент матрицы, хотя в рамках нашей задачи мы должны искать количество слагаемых в составе перманента.
Нетрудно увидеть что количество слагаемых в перманенте матрицы 3х3 равно 6:
И это и есть количество возможных расстановок не бьющих друг друга ладей на доске размером 3х3.
Матрица разрешений
И тут мы подходим к еще одному важному с математической точки зрения определению необходимому для решения данной задачи, дело в том что нам придется работать с двумя типами матриц (а кто говорил что задача простая?), назовем их матрица разрешений и матрица решений.
Матрица разрешений – это матрица в которой единицами отмечены ячейки в которые МОЖНО ставить ладью, то есть можно ставить единицу в матрице решения. А матрица решения – это матрица с расставленными ладьями (тоже единицами, но указывающих выбранную позицию ладьи из разрешенных с помощью матрицы разрешений).
Легко видеть что для произвольной квадратной единичной матрицы размерностью N в которой разрешены все ячейки количество расстановок ладей определяется простым факториалом N (N!).
Анализ минимального троичного варианта
И с этим знанием мы переходим к анализу матрицы составленной автором задачи в его телеграме:
Во первых надо заметить что это именно матрица разрешений, а задача состоит в том чтобы найти количество уникальных матриц решений. Матрицей решением в данном случае будет матрица с расставленными в темные ячейки единицами такая что для всех ее столбцов и строк сумма элементов в них должна быть равна тоже единице.
Тут надо обязательно уточнить что если сумма хоть в одном столбце или строке равна нулю это значит там не оказалось ладьи и такая матрица НЕ является решением, так как соответствие должно быть обеспечено для всех без исключения строк чисел с одной пропущеной цифрой.
Теперь те, кто имел хоть какое то дело с вычислениями и анализом матриц должны вспомнить что анализ матриц в большой мере связан с перестановкой строк или столбцов в матрице и первое что мы должны сделать это попробовать переставить например строки так чтобы увидеть некоторую регулярность в расположении единиц в матрице разрешений. Такая регулярность может нам помочь понять способ подсчета интересующих нас уникальных расстановок.
Можно преобразовать нашу матрицу например вот так:
Можно предположить что количество уникальных расстановок в одном из выделенных квадратов поможет нам понять как посчитать количество расстановок в полной матрице, поэтому как минимум стоит попробовать выполнить это упражнение вручную. Например вот так:
Здесь приведен пример ручной расстановки сверху вниз. Мы видим(знаем) что выбор позиции одной ладьи запрещает использование разрешенных ячеек в соответствующих столбце (черные линии) и строке, поэтому легко посчитать что существует всего 6 (шесть!) вариантов заполнения трех верхних строчек, с каждым из которых может стыковаться только 2 (два!) варианта заполнения трех средних строчек. Значения в последних трех строчках однозначно определяются распределением в верхних шести. Итого существует всего 6 * 2 = 12 вариантов расстановки в этом сегменте матрицы!
Когда мы определились с выбранной позицией в трех последних строчках, у нас остается всего два варианта задать значение в правой смежной матрице в которой всего три разрешенных ячейки, то есть для каждого из 12 вариантов есть 2 варианта справа, которые управляют столбцами центрального сегмента 9х9.
И оказывается что у нас есть только один вариант задать значение в нижней смежной матрице в которой тоже всего три разрешенных ячейки, то есть 12 вариантов из верхнего сегмента однозначно определяют единственную свободную строку из трех в центральном сегменте 9х9.
Следующая картинка показывает как запреты из верхнего левого сегмента распространяются в средний сегмент через нижний и правый смежные сегменты верхнего левого сегмента.
Таким образом переход к центральному сегменту дает нам размножение вариантов расстановок два раза по два раз, итого получается 12 * 2 * 2 = 48 вариантов расстановок в матрице 18х18, а дальше уже все становится детерменировано так как распространяется максимальное количество запретов из возможных, то есть остается один детерменированный вариант заданный одним из выбранных выше 48 вариантов.
Заключение
Я не исключаю что где то допустил ошибку поэтому проверяйте. Но я практически уверен что нет ошибки для первого сегмента 9х9 и поэтому общее число вариантов не может очень далеко уйти от числа 12 и поэтому результат озвученный в предыдущей статье
расчеты для N=3 (матрица 27х27) на питоне занимают около часа и дают 10 752
представляется мне крайне сомнительным, особое подозрение вызывает число 7 в составе разложения на множители этого результата, которое вроде как не имеет источника в числах исходных условий задачи. Я думаю никто не заложил в программу на Питоне хотя бы проверку того, что все суммы строк и столбцов каждого из 10 752 вариантов расстановок дают единицы. Не говоря уже о проверке на уникальность расстановок.
Мне честно говоря не очень нравится решать подобные задачи которые по моему совершенно не имеют практического смысла, но еще больше мне не нравится наблюдать ВОЗМОЖНО неправильные решения математических задач, поэтому решил разработать и поделиться основаниями для своих сомнений с аудиторией.
Примером практической задачи с похожим методом решения (анализ матрицы по сегментам), решением которой мне тоже довелось заниматься, является декодирование LDPC кодов в реальных системах связи, например для Wi-Fi. Там также анализируются матрицы размерами до тысыч на тысячи, причем наполненные действительными числами, а не нулями и единицами. Программы которые обрабатывают эти матрицы работают в реальном времени в реальных приемо-передатчиках реальных сигналов, то есть матрицы обрабатываются за микросекунды без всяких квантовых-нано вычислений. О чем эти LDPC коды можно посмотреть например здесь: