Comments 16
Возникло несколько соображений.
ну, все не так плохо. Г-н Кнут, я читал, выложил себе дома узор из какой-то уникальной плитки. Причем он ошибся в одной из веток своего «меандра». Зато реально уникально и красиво
www.youtube.com/watch?v=v678Em6qyzk
Поэтому как минимум фрагмент бесконечной доски с ферзями у себя можно разместить дома.
В остальном — а нельзя ли эту задачу выполнять по индукции? Ну, т.е. нашли решения для доски n x n, а затем придумываем как перейти к решению для (n + 1) x (n + 1). Явно, что это правило перехода должно быть универсальным. Или… нет?
Думаю, что в компании родственников, вы, скорее всего, будете единственным, кто получил в подарок такое «интеллектуальное изделие». Будет весело, если вы расскажете тёще о таком подарке: «Представьте себе мамо шахматную доску размером 50 000 км на 50 000 км, на которой распределены 1 миллиард ферзей таким образом, что один другого в упор не видит…». Кто знает, может после этого, будут больше ценить зятя, раз ему такой странный подарок вручают.
ну, все не так плохо. Г-н Кнут, я читал, выложил себе дома узор из какой-то уникальной плитки. Причем он ошибся в одной из веток своего «меандра». Зато реально уникально и красиво
www.youtube.com/watch?v=v678Em6qyzk
Поэтому как минимум фрагмент бесконечной доски с ферзями у себя можно разместить дома.
В остальном — а нельзя ли эту задачу выполнять по индукции? Ну, т.е. нашли решения для доски n x n, а затем придумываем как перейти к решению для (n + 1) x (n + 1). Явно, что это правило перехода должно быть универсальным. Или… нет?
В остальном — а нельзя ли эту задачу выполнять по индукции? Ну, т.е. нашли решения для доски n x n, а затем придумываем как перейти к решению для (n + 1) x (n + 1). Явно, что это правило перехода должно быть универсальным. Или… нет?
Доказательство такой возможности, даже без алгоритма, потянет на серьезную математическую премию.
Спасибо за грамотный вопрос! Ее можно сформулировать в виде следующей задачи:«На доске размера (n+1) x (n+1) правильно расставлены ферзи в n последовательных строках таким образом, что остались свободными первая (последняя) строка и первый (последний) столбец. Можно ли расположить еще один (последний) ферзь таким образом, чтобы получить правильное решение? Это один из частных вариантов формулировки общей задачи о „Комплектации произвольной композиции из k ферзей до полного решения“. В таком виде задача была сформулирована F. Nauck в 1850 году. В сентябре 2017 года I.P. Gent, C. Jefferson, P. Nightingale доказали, что данная проблема относится к классу NP-Complete. Ссылки на эти статьи есть в публикации. Повторюсь, речь идет конкретно о задаче „Комплектации ...“. Ценю, вы человек проницательный, спокойно сформулировали вопрос, который относится к одному частному случаю решения NP-Complete задачи. Дополнительно могу сказать следующее. Большую часть 2018 года я был занят разработкой алгоритма решения этой NP-Complete задачи. Я был на творческой диете и почти каждый день был занят только этой задачей. Спустя 4 месяца я получил удовлетворительный результат. Еще через 4 месяца я добился того, что алгоритм выполняет решение данной задачи за линейное время, для произвольного значения n и произвольных k ферзей не противоречиво расположенных на доске n x n. После этого я, в течение следующих трех месяцев вел исследования, чтобы добиться правильного решения в этом „лабиринте“ не с 5-го или 30-го раза, а чтобы решение преимущественно было получено с первого раза. Удивительно, но и в этом вопросе удалось получить положительных результатов. Ваш вопрос интересный и „задел за живое“. Поэтому все и рассказал. Я подготовил большую статью для отправки в Journal of Artificial Intelligence Research. Однозначно, после выхода публикации я приведу подробное описание полученных результатов. Там много чего интересного.
Когда-то тоже баловался решением этой задачи. Использовал обычный поиск с возвратом — у меня получалось находить решения на досках до 30х30. Времени на поиск одного решения уходило где-то в районе одного часа. Из оптимизаций использовал отказ от рекурсии и оптимизирующую компиляцию. Понял, что дальнейшее увеличение размера доски ведет к экспоненциальному росту сложности и оставил задачу на долгие годы.
Как же у Вас получилось найти решение на такой огромной доске? Поделитесь секретом?
Как же у Вас получилось найти решение на такой огромной доске? Поделитесь секретом?
Я искренне считаю, что если вы в свое время построили алгоритм и получали решение для 30 х 30, пусть даже за час, то вы относитесь к особой категории программистов, которые не боятся сложных задач, и, скорее всего, используют девиз «Вижу цель — не вижу преграду». Будем объективны, это, все таки, достаточно сложная задача. И если программист-исследователь ее решил, то можно считать, что он сдал «Очередную норму ГТО» в области программирования. Я выше уже писал, что в течение почти всего 2018 года занимался исследованием и разработкой алгоритма для решения «n-Queens Completion Problem». Я так долго и «нагло» с одной и той же задачей не сидел. В итоге, спустя много-много месяцев мне удалось разработать алгоритм который решает эту проблему за линейное время. (Среднее время получения решения одного решения для доски размером миллион на миллион составляет меньше 9 секунд). После этого я решил получить решение для больших значений n. Для n=(100, 300, 500 — миллионов) проблем не возникало. Когда начал рассматривать n=одному миллиарду, возникли проблемы. Оперативной памяти 32 Gb не хватило. (Я большие массивы в алгоритме не использую. Но наличие контрольных векторов размером с миллиард, перекрыло кислород). Пришлось остановиться, переосмыслить. После этого разделил алгоритм на три части, с сохранением промежуточных результатов. И в итоге, если не учесть время загрузки и выгрузки промежуточных фалов, то решение было получено, примерно за 3.5-4 часа. Хочу сказать, что я осознанно и целенаправленно искал это решение как подарок для членов Хабро-Сообщества к новому году. Статья была подготовлена в стандарте HTML-5 еще в конце декабря 2018, но Хабро-Приемник не пропустил. Я не знал, что там немного иные «стандарты». В итоге, пришлось, как сказал бы Лукашенко, «перетрахивать» набранный текст, и уже подавать после нового года. Спасибо Хабро-Sis-Админам, успели подать материал к «старому новому году»
Спасибо за ответ, я действительно в свое время несколько «подсел» на эту задачу и даже реализовал ее на ассемблере. Откомпилированный файл составлял 182 байта. Затем был обход конем всех клеток шахматного поля, затем построение обобщенного алгоритма в виде абстрактного класса на C++, затем реализация его же с использованием шаблонов, затем меня отпустило :) Однако все это время я использовал полный перебор.
Поэтому, по моему мнению, решение такой задачи за линейное время это мягко говоря, очень круто. Не рассматривали возможность переноса принципов заложенных в вашем алгоритме на другие задачи, например применение к задаче коммивояжера?
Кстати, если судить по этой статье, вы можете претендовать на миллион долларов.
Задачу о N ферзях признали NP-полной задачей
Поэтому, по моему мнению, решение такой задачи за линейное время это мягко говоря, очень круто. Не рассматривали возможность переноса принципов заложенных в вашем алгоритме на другие задачи, например применение к задаче коммивояжера?
Кстати, если судить по этой статье, вы можете претендовать на миллион долларов.
Задачу о N ферзях признали NP-полной задачей
В начале скажу, что «Задачу о N ферзях признали NP-полной задачей» не является верным высказыванием и один из уважаемых членов Хабра-Сообщества достаточно подробно об этом писал. С другой стороны задача «n-Queens Completion Problem» относится к множеству NP-Complete.
По поводу линейного алгоритма решения этой задачи — вы правы, если бы год назад мне об этом сказал бы кто-то другой, я бы тоже не поверил. Видимо, это тот редкий случай, когда много месяцев живешь внутри задачи, и наступает момент, когда становится прозрачным то, что раньше «не было видно». Могу «подтвердить», что Будда был прав, когда сидел в уединении и долго оставался в состоянии медитации. Да, алгоритм линейный. За все время исследования я несколько десятков миллионов раз проводил расчеты для различных значений n, и алгоритм оставался линейным. Диапазон значений n в исследовании менялся от 7 до пятидесяти миллионов.
По поводу возможности разработки полиномиального (а еще лучше — линейного) алгоритма для решения других сложных задач из множества NP-Complete, могу сказать следующее:
a) задача, которую я решал, связана с разработкой оптимального алгоритма формирования ветви поиска решения, в условиях меняющихся, с каждым шагом, ограничений.
b) решение удалось получить только после того, когда в результате многочисленных экспериментов (Computational Simulation) были установлены важные правила, которые являются неотъемлемым свойством данной задачи.
c) ряд задач, из множества NP-Complete можно попытаться решить, используя установленные правила, или иные правила «в том же русле». Есть большая вероятность того, что некоторые задачи будут успешно решены «по аналогии». Но лучше решить, а потом об этом сказать. А пока, это только уверенное предположение. Тут уместна поговорка:«Не скажи гоп, пока не перепрыгнешь». Поэтому следует подождать.
По поводу всяких призов. Признаюсь честно — я об этом не думал. Удовольствие, которое получаешь, решая сложные задачи «достаточно дорого стоят». Но тут важно другое. Дело в том, что одним наиболее важных, принципиальных выводов, которые были получены в результате исследования, состоит в том, что «данную задачу и задачи, ей подобные, невозможно решить на основе привычных методов математики: на основе определений, формулировки лемм и доказательства теорем. Эту и подобные ей задачи можно решить только на основе „алгоритмической математики“. Думаю, что нашим уважаемым коллегам математикам „это может не понравиться“. Однако это не ограничивает возможности математики, а наоборот — расширяет эти возможности через направление „алгоритмической математики“.
Вряд ли „вектор моих мыслей“ будет направлен в сторону каких либо премий. Это было бы не рационально и мешало бы работать. В настоящий момент, я больше нуждаюсь в том, чтобы устроиться на работу у кого нибудь на пол-ставки в качестве разработчика сложных и ответственных алгоритмов, или других сложных задач, где я могу принести реальную пользу. Уже 4 года нахожусь в Марселе, и, к сожалению, так и не удалось устроиться на работу. На простые задачи не хотел терять время, а сложные задачи они не хотели ставить. (Интересный факт: после долгого перерыва у меня вышла публикация, в которой, в позиции, где указывается место работы я честно написал „безработный“. Ответственный сотрудник редакции написал, что „безработные у нас не публикуются“ и что „безработный не может делать такие публикации“. Пришлось согласиться на фразу „независимый исследователь“. Так, что я теперь в статусе: безработный — независимый исследователь.
По поводу линейного алгоритма решения этой задачи — вы правы, если бы год назад мне об этом сказал бы кто-то другой, я бы тоже не поверил. Видимо, это тот редкий случай, когда много месяцев живешь внутри задачи, и наступает момент, когда становится прозрачным то, что раньше «не было видно». Могу «подтвердить», что Будда был прав, когда сидел в уединении и долго оставался в состоянии медитации. Да, алгоритм линейный. За все время исследования я несколько десятков миллионов раз проводил расчеты для различных значений n, и алгоритм оставался линейным. Диапазон значений n в исследовании менялся от 7 до пятидесяти миллионов.
По поводу возможности разработки полиномиального (а еще лучше — линейного) алгоритма для решения других сложных задач из множества NP-Complete, могу сказать следующее:
a) задача, которую я решал, связана с разработкой оптимального алгоритма формирования ветви поиска решения, в условиях меняющихся, с каждым шагом, ограничений.
b) решение удалось получить только после того, когда в результате многочисленных экспериментов (Computational Simulation) были установлены важные правила, которые являются неотъемлемым свойством данной задачи.
c) ряд задач, из множества NP-Complete можно попытаться решить, используя установленные правила, или иные правила «в том же русле». Есть большая вероятность того, что некоторые задачи будут успешно решены «по аналогии». Но лучше решить, а потом об этом сказать. А пока, это только уверенное предположение. Тут уместна поговорка:«Не скажи гоп, пока не перепрыгнешь». Поэтому следует подождать.
По поводу всяких призов. Признаюсь честно — я об этом не думал. Удовольствие, которое получаешь, решая сложные задачи «достаточно дорого стоят». Но тут важно другое. Дело в том, что одним наиболее важных, принципиальных выводов, которые были получены в результате исследования, состоит в том, что «данную задачу и задачи, ей подобные, невозможно решить на основе привычных методов математики: на основе определений, формулировки лемм и доказательства теорем. Эту и подобные ей задачи можно решить только на основе „алгоритмической математики“. Думаю, что нашим уважаемым коллегам математикам „это может не понравиться“. Однако это не ограничивает возможности математики, а наоборот — расширяет эти возможности через направление „алгоритмической математики“.
Вряд ли „вектор моих мыслей“ будет направлен в сторону каких либо премий. Это было бы не рационально и мешало бы работать. В настоящий момент, я больше нуждаюсь в том, чтобы устроиться на работу у кого нибудь на пол-ставки в качестве разработчика сложных и ответственных алгоритмов, или других сложных задач, где я могу принести реальную пользу. Уже 4 года нахожусь в Марселе, и, к сожалению, так и не удалось устроиться на работу. На простые задачи не хотел терять время, а сложные задачи они не хотели ставить. (Интересный факт: после долгого перерыва у меня вышла публикация, в которой, в позиции, где указывается место работы я честно написал „безработный“. Ответственный сотрудник редакции написал, что „безработные у нас не публикуются“ и что „безработный не может делать такие публикации“. Пришлось согласиться на фразу „независимый исследователь“. Так, что я теперь в статусе: безработный — независимый исследователь.
Да, алгоритм линейный.
Для какой конкретно задачи алгоритм линейный — для нахождения одного решения для заданного n, для нахождения всех решений для заданного n, или для задачи дополнения? Если дополнения, то в каком варианте?
Речь идет об алгоритме решения n-Queens Completion Problem. Данная задача относится к классу NP-Complete. Об этом была публикация на Хабре. Суть ее состоит в следующем. На шахматной доске размера n x n не противоречиво расставлены k ферзей. Требуется разработать алгоритм, который «достроит» данную композицию до полного решения, либо доказать, что данная композиция не может быть комплектована до полного решения. Именно о линейном алгоритме решения данной задачи я писал в своем комментарии. Я нереально долго сидел над решением этой задачи. Настолько долго, что как-то стыдно было «соскочить» не получив положительного результата. Результаты исследования по данному проекту подготовлены к публикации. После выхода статьи, я обязательно выложу на Хабре подробное описание. Там очень много интересного.
Так вот, данный алгоритм я использовал для того, чтобы найти одно решение задачи о «распределении одного миллиарда ферзей на шахматной доске размером миллиард на миллиард». Это было в декабре и мне хотелось преподнести всем членам Хабра-Сообщества небольшой новогодний подарок в виде такого «интеллектуального изделия».
Сама задача нахождения одного решения является интересной алгоритмической задачей, но к классу NP-Complete не относится.
Задача нахождения всех решений для заданного n формулируется немного иначе. Никто не требует найти «подряд» все решения для заданного значения n. Требуется только определить количество всех решений для каждого значения n. Это достаточно сложная задача и относится к классу NP-Complete. Методом прямого вычисления всех полных решений, в предыдущие годы был найден размер списка всех решений вплоть до значения n=27. После этого подобные расчеты не проводились, так как это требует значительных вычислительных ресурсов и временных затрат. Кстати, нет необходимости в том, чтобы найти последовательный список всех полных решений. Достаточно найти только первую половину этого списка. Вторая половина списка полных решений симметрична и комплементарна к первой половине списка. Поэтому, все найденные значения размера списка полных решений являются четными числами.(Sloane N.J.A. (2016). The on-line encyclopedia of integer sequences. oeis.org/search?q=A000170&language=english&go=Search). Я об этом писал в публикации.
Так вот, данный алгоритм я использовал для того, чтобы найти одно решение задачи о «распределении одного миллиарда ферзей на шахматной доске размером миллиард на миллиард». Это было в декабре и мне хотелось преподнести всем членам Хабра-Сообщества небольшой новогодний подарок в виде такого «интеллектуального изделия».
Сама задача нахождения одного решения является интересной алгоритмической задачей, но к классу NP-Complete не относится.
Задача нахождения всех решений для заданного n формулируется немного иначе. Никто не требует найти «подряд» все решения для заданного значения n. Требуется только определить количество всех решений для каждого значения n. Это достаточно сложная задача и относится к классу NP-Complete. Методом прямого вычисления всех полных решений, в предыдущие годы был найден размер списка всех решений вплоть до значения n=27. После этого подобные расчеты не проводились, так как это требует значительных вычислительных ресурсов и временных затрат. Кстати, нет необходимости в том, чтобы найти последовательный список всех полных решений. Достаточно найти только первую половину этого списка. Вторая половина списка полных решений симметрична и комплементарна к первой половине списка. Поэтому, все найденные значения размера списка полных решений являются четными числами.(Sloane N.J.A. (2016). The on-line encyclopedia of integer sequences. oeis.org/search?q=A000170&language=english&go=Search). Я об этом писал в публикации.
На шахматной доске размера n x n не противоречиво расставлены k ферзей.
В произвольных ячейках, или в первых k строчках и k колонках?
Требуется разработать алгоритм, который «достроит» данную композицию до полного решения, либо доказать, что данная композиция не может быть комплектована до полного решения. Именно о линейном алгоритме решения данной задачи я писал в своем комментарии.
Ну то есть вы утверждаете, что вы сделали корректный линейный алгоритм для NP-полной задачи?
Так вот, данный алгоритм я использовал для того, чтобы найти одно решение задачи о «распределении одного миллиарда ферзей на шахматной доске размером миллиард на миллиард».
В смысле, найти одно любое решение задачи n-queen placement, где n = миллиард?
1. В задаче идет речь о «произвольных» k ферзях «произвольно» расположенных на шахматной доске размера n x n. В ходе исследования я рассматривал значения n от 7 до 50 миллионов.
2. К моему удивлению, алгоритм оказался линейным.
3. Вы правы, речь идет о «найти одно любое решение задачи n-queen placement, где n = миллиард». Это решение в виде 1-мерного массива (файла) доступно для скачивания. Об этом написано в публикации
2. К моему удивлению, алгоритм оказался линейным.
3. Вы правы, речь идет о «найти одно любое решение задачи n-queen placement, где n = миллиард». Это решение в виде 1-мерного массива (файла) доступно для скачивания. Об этом написано в публикации
К моему удивлению, алгоритм оказался линейным.
Оказался ли он доказано правильным?
Вы правы, речь идет о «найти одно любое решение задачи n-queen placement, где n = миллиард».
Вы же знаете, да, что для этой задачи есть хорошо описанное решение за линейное время? Не требующее решения задачи n-queens completion?
Когда я выложил на Хабр публикацию: «One Billion Queens Problem Solution или, «Исследование закономерностей в списке решений задачи распределения n-Ферзей», я не думал, что дискуссия перекинется на проект, который еще не опубликован. Как я уже писал, результаты исследования «разработка алгоритма решения n-Queens Completion Problem», подготовлены к публикации. После выхода статьи, я приведу достаточно подробное описание алгоритма для Хабра. Давайте подождем немного.
По поводу вопросов:
1.«Оказался ли он доказано правильным?»
-Да, алгоритма решения n-Queens Completion Problem» является линейным. Так как это принципиально, расчеты проводились несколько десятков миллионов раз. Результаты это подтверждают.
2.«Вы же знаете, да, что для этой задачи есть хорошо описанное решение за линейное время? Не требующее решения задачи n-queens completion?»
-Как я уже писал в комментарии, a) разработка алгоритма решения n-Queens Completion Problem», и b) поиск хотя бы одного решения для заданного значения n, это разные задачи.
Первая задача — n-Queens Completion Problem, относится к множеству NP-Complete, и является достаточно сложной. Я не нашел публикацию, где приводилось бы решение данной проблемы.
По поводу второй задачи «поиск хотя бы одного решения…» — имеется большое количество различных публикаций, которые прямо или косвенно касаются этой задаче. Посмотрите (W. Kosters and dll, n-Queens — 339 references, (September 11, 2017),
www.liacs.leidenuniv.nl/~kosterswa/nqueens, возможно, что-то интересное найдете для себя. Есть различные алгоритмы «поиска хотя бы одного решения…». Одни работают быстро, другие медленно.
Я тоже разрабатывал алгоритм «поиска хотя бы одного решения…» для целей исследования, но об этом, в своей публикации на Хабре я ничего не писал. Хотя, алгоритм получился интересный и работает достаточно быстро. Среднее время поиска одного решения для доски размером миллион на миллион составляет около 9 секунд. Спасибо!
В связи с выше изложенным, я прошу дискуссию по поводу проекта «разработка алгоритма решения n-Queens Completion Problem» приостановить, до выхода соответствующей публикации на Хабре.
По поводу вопросов:
1.«Оказался ли он доказано правильным?»
-Да, алгоритма решения n-Queens Completion Problem» является линейным. Так как это принципиально, расчеты проводились несколько десятков миллионов раз. Результаты это подтверждают.
2.«Вы же знаете, да, что для этой задачи есть хорошо описанное решение за линейное время? Не требующее решения задачи n-queens completion?»
-Как я уже писал в комментарии, a) разработка алгоритма решения n-Queens Completion Problem», и b) поиск хотя бы одного решения для заданного значения n, это разные задачи.
Первая задача — n-Queens Completion Problem, относится к множеству NP-Complete, и является достаточно сложной. Я не нашел публикацию, где приводилось бы решение данной проблемы.
По поводу второй задачи «поиск хотя бы одного решения…» — имеется большое количество различных публикаций, которые прямо или косвенно касаются этой задаче. Посмотрите (W. Kosters and dll, n-Queens — 339 references, (September 11, 2017),
www.liacs.leidenuniv.nl/~kosterswa/nqueens, возможно, что-то интересное найдете для себя. Есть различные алгоритмы «поиска хотя бы одного решения…». Одни работают быстро, другие медленно.
Я тоже разрабатывал алгоритм «поиска хотя бы одного решения…» для целей исследования, но об этом, в своей публикации на Хабре я ничего не писал. Хотя, алгоритм получился интересный и работает достаточно быстро. Среднее время поиска одного решения для доски размером миллион на миллион составляет около 9 секунд. Спасибо!
В связи с выше изложенным, я прошу дискуссию по поводу проекта «разработка алгоритма решения n-Queens Completion Problem» приостановить, до выхода соответствующей публикации на Хабре.
Да, алгоритма решения n-Queens Completion Problem» является линейным.
Про то, линейный ли он, вы ответили комментарием выше. А я спрашивал, доказана ли корректность алгоритма.
Как я уже писал в комментарии, a) разработка алгоритма решения n-Queens Completion Problem», и b) поиск хотя бы одного решения для заданного значения n, это разные задачи.
Это не помешало вам написать "Речь идет об алгоритме решения n-Queens Completion Problem. [...] Так вот, данный алгоритм я использовал для того, чтобы найти одно решение задачи о «распределении одного миллиарда ферзей на шахматной доске размером миллиард на миллиард»."
Так зачем вам понадобилось использовать n-queens completion для решения простой задачи одиночной расстановки?
Хотя, алгоритм получился интересный и работает достаточно быстро.
Чем вас не устроил существующий?
спасибо.
сохранил на диск цэ
сохранил на диск цэ
Я рад, что вы «забрали подарок домой». Мне нравится наше Хабро-Сообщество, и мне хотелось сделать что нибудь приятное для членов сообщества. И вообще, показать, что в Хабро-Сообществе такие «подарки» могут преподнести, а в других сообществах — вряд ли.
Чтобы эти 3.7 Gb не простаивали зря на вашем диске, предлагаю простую задачу для творчества и отдыха. Все числа в этом массиве, это числа от 1 до одного миллиарда, перечисленные в особой последовательности в соответствии с ограничениями, согласно условиям задачи. Возьмем последовательно любой миллион чисел из этого списка и разнесем их в обнуленный 1-мерный массив размером миллиард, т.е. в соответствующую ячейку запишем номер ячейки. Теперь, если «сжать» этот массив, т.е. убрать нули, то получим 1 миллион чисел, которые, как было сказано, меняются от 1 до одного миллиарда. Теперь, на основе «проекции» сведем изменение чисел от 1 до миллиарда к изменению — от 1 до миллиона. Таким образом мы получим все числа от 1 до миллиона, но имеющих особый порядок перечисления. Поставим каждому из этих миллионов чисел, некий «цвет» из последовательной гаммы цветов и выведем это на экран в виде изображения 1000 х 1000 пикселей. Учитывая, что в решении есть определенная гармония, то просматривая сотню произвольных таких изображений, вы найдете хотя бы одну, которая вам понравится. Это будет некоторой, своеобразной визуализацией определенной части общего решения. Я этого не делал, но думаю, что это будет весело. Успехов!
Чтобы эти 3.7 Gb не простаивали зря на вашем диске, предлагаю простую задачу для творчества и отдыха. Все числа в этом массиве, это числа от 1 до одного миллиарда, перечисленные в особой последовательности в соответствии с ограничениями, согласно условиям задачи. Возьмем последовательно любой миллион чисел из этого списка и разнесем их в обнуленный 1-мерный массив размером миллиард, т.е. в соответствующую ячейку запишем номер ячейки. Теперь, если «сжать» этот массив, т.е. убрать нули, то получим 1 миллион чисел, которые, как было сказано, меняются от 1 до одного миллиарда. Теперь, на основе «проекции» сведем изменение чисел от 1 до миллиарда к изменению — от 1 до миллиона. Таким образом мы получим все числа от 1 до миллиона, но имеющих особый порядок перечисления. Поставим каждому из этих миллионов чисел, некий «цвет» из последовательной гаммы цветов и выведем это на экран в виде изображения 1000 х 1000 пикселей. Учитывая, что в решении есть определенная гармония, то просматривая сотню произвольных таких изображений, вы найдете хотя бы одну, которая вам понравится. Это будет некоторой, своеобразной визуализацией определенной части общего решения. Я этого не делал, но думаю, что это будет весело. Успехов!
Sign up to leave a comment.
One Billion Queens Problem Solution или, «Исследование закономерностей в списке решений задачи распределения n-Ферзей»