Время: 4 недели (12 апреля — 10 мая 2010 г.) Конкурс завершён. Смотрите итоги.

Продолжаю делать конкурсы для программистов-математиков. Это второй конкурс. Предыдущий был посвящён перемножению матриц, и результатами я был очень доволен. Судя по отзывам, некоторые участники тоже. На этот раз задача чуть сложнее, а призовой фонд 3000 р. (на два призовых места: 2000 р. + 1000 р.). Задача довольно специфическая: сколькими способами можно расположить на шахматной доске размером n×n шесть не бьющих друг друга шахматных ферзей? Предупреждаю, решать эту задачу «в лоб» не получится, конечно, если у Вас нет под рукой мощного кластера. Но если Вы хорошо разбираетесь в переборных задачах, то участвуйте!

В чём смысл и кому это нужно?

Такого рода задачи относятся к категории так называемых «общих проблем науки». Это задача перечислительной комбинаторики. Все задачи из этой области, которые легко решаются перебором, уже давно решены, поэтому сейчас сражение идёт не за то, у кого кластер мощнее, а за то, кто умнее сможет организовать подсчёт. Решениями таких задач разные научные коллективы демонстрируют друг другу свои возможности. Сама по себе она, конечно, не имеет практической пользы, но смысл в том, что при решении таких задач иногда возникают новые методы, идеи и даже целые теории, которые затем дополняют текущую научную картину Мира. Например, когда решали задачу о расстановке n ферзей на доске n×n для n=26, разработали несколько новых теорий, на которых защитилось несколько человек.

Месяц назад была актуальной проблема пяти ферзей, но мне удалось вывести общую формулу, закрыв этот вопрос. К сожалению, пока я эту формулу упрощал, ещё один исследователь её опубликовал, причем в неупрощённом виде. Формулу можно посмотреть в энциклопедии целочисленных последовательностей: A108792 (моя формула проще, так как не содержит тригонометрических функций). Это, конечно, замечательно, но следующим шагом может быть только решение задачи о шести ферзях. Решить задачу — это значит вывести формулу или предложить другой эффективный способ получения ответа для любого значения n. Вот этим я и занимаюсь. Задачу я решу в любом случае, но конкурс поможет сделать это правильно и лучше. Все-таки, в одиночку можно и ошибиться, а когда решаешь вместе с кем-то, то вряд ли.

Что нужно для вывода формулы? Нужно получить примерно 80 чисел, тогда можно угадать закономерность. Для 5 ферзей мне нужно было знать ответ лишь до n=38.

Положения

Общие правила и ограничения

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

  1. Предоставляя ответ для некоторого n участник обязан сказать ответ также для всех значений k<n. Разумеется, не надо повторять те числа, которые уже записаны в таблице результатов ниже. Например, если лидер сказал ответ для n=20, а Вы посчитали до n=23, то ответ засчитывается только если Вы также называет ответ для n=21 и n=22.
  2. Победители конкурса обязуются предоставить мне полный исходный код (не важно, на каком языке, только, пожалуйста, не на эзотерическом типа BrainFuck : ) ) после его окончания.
  3. Я, автор конкурса, тоже принимаю в нём участие на равных с остальными. Почему? Объясню ниже.
  4. Конкурс завершается 10 мая 2010 г. ровно в 12 ч. 00 м.
  5. Приз можно получить только через Яндекс.Деньги или WebMoney.
  6. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой «6 Ферзей — Конкурс». В письме необходимо указать свой ник, значение n, для которого был посчитан ответ и сам ответ. Также требуется указать, на чём выполнялось вычисление (сколько ядер) и сколько минут (или часов (или дней)) заняли расчёты для указанного n.
  2. Будет вестись рейтинговая таблица, в которой указываются все участники и их результаты.
  3. Чтобы переместиться по рейтинговой таблице вверх, нужно указать ответ для того значения n, которое больше, чем у текущего лидера. То есть, если у лидера n=20, то Вам надо как минимум сказать ответ для n=21, иначе попытка не засчитывается.
  4. Почта проверяется случайным образом (не меньше одного раза в сутки), поэтому может возникнуть ситуация, когда несколько участников предоставляют одно и то же число, но кто-то раньше, а кто-то позже. В этом случае сравнивается дата попадания письма в ящик конкурса.
  5. Победителем считается тот, кто назвал ответ к задаче для наибольшего возможного n, а также прислал полный исходный код программы по истечении конкурса. За победу 2000 р.
  6. Второе место занимает тот, кто окажется в финальной рейтинговой таблице под номером два (если под номером два тот же, кто и под номером один, то берётся следующая позиция и т. д.) и пришлёт полный исходный код программы по окончании конкурса. За второе место 1000 р.

Гарантии

Я гарантирую, что победитель(и) получит(ат) приз в соответствии с правилами. Я уже проводил конкурсы и никого обманывать не собираюсь. Во-вторых, участие бесплатное и никто ничего не теряет. Заметьте, что я не запрещаю пользоваться самыми продвинутыми на сегодняшний день средствами программирования, в том числе кластерами. Мне нужны только ответы. Не надо, пожалуйста, думать, что я ищу дешёвую рабочую силу. Поверьте, мне не надо сдавать курсовую или диплом или что-то кому-то продавать. Да, согласен, приз не очень большой. Ну а сколько по-вашему получает преподаватель университета? Единственное, что может быть не очень честно: участники конкурса не будут указаны в научной статье об этой задаче, если я такую когда-нибудь напишу. Чтобы потом никто не обижался! Хотя ссылку на эту страницу, где все перечислены, я попробую сделать, если позволит рецензент.

Пожелания

По мере проведения конкурса привлекайте новых участников. Мой блог не так сильно раскручен, поэтому участие хотя бы 10 человек я буду считать большим успехом. Не надо думать, что этим конкурсом я оптимизирую блог (как меня обвинили в прошлый раз). Если бы я хотел это сделать, то на 3000 р. просто купил бы ссылок.

После окончания конкурса я, по вашему желанию, установлю ссылки с этой страницы на главные страницы вашего сайта, при условии, что Вы установите ссылку со своей не главной страницы на эту. Все ссылки без noindex и nofollow.

Если пишете комментарии, то подписывайтесь тем ником, который у вас отображается в таблице рейтинга (если отображается).

FAQ

Некоторые участники форумов программистов начинают задавать одни и те же вопросы (или высказывать соображения), на которые тяжело отвечать одно и то же. Поэтому делаю список часто задаваемых вопросов. Сюда входят даже те вопросы, которые ещё никто не задал, но хотел.

  1. Что за тупой конкурс? Ответ: идите нафиг.
  2. Вы правда думаете, что за 3000 р. люди сразу побегут к вам писать программы? Ответ: не нравится — не участвуйте. Конкурс не для всех, а для тех, кому интересно писать оптимальный код. Мне думается, что промышленные программисты и web-программисты не должны тратить на это время.
  3. А у меня под рукой сто тысяч ядер, я напишу тупейший перебор и всё равно выиграю! Ответ: посмотрим : ) Я совершенно не ограничиваю Вас в выборе инструмента. Да, отчасти тут есть элемент неравенства, особенно если Вы имеете доступ к кластеру. Но работу мозга ещё никто не отменял. Так даже интереснее: мозги против железа! А у кого есть и то и другое… в общем, посмотрим. Самому интересно, что будет.
  4. Я 5 лет работаю программистом и понятия не имею как решать эту задачу, если только не перебором. Ответ: программисты бывают разными, например, web-программисты и т. д. Конечно же, если Вы не понимаете в чем состоит задача и почему в ней надо думать — это конкурс не для Вас. Это для тех, кто умеет писать оптимальный код для вычислительных задач, то есть для тех, кто на этом специализируется. Конечно же этим конкурсом я не хочу обидеть остальных программистов, которые сильны в какой-то своей области. Это просто не для них и всё.
  5. Как Вы собираетесь проверять ответ? Ответ: скорее всего, к концу конкурса я выведу формулу, как сделал это месяц назад для задачи о пяти ферзях. В любом случае, я с большой вероятностью могу сказать, правильное дано число или нет. Поэтому, кстати, и требую помимо одного числа указать все предшествующие.
  6. То, что Вы являетесь участником и организатором дает Вам те или иные преимущества — это нечестно. Например, вдруг Вы уже вывели формулу? Ответ: ничего подобного. Да, у меня есть опыт решения трудных задач. Если бы я вывел формулу, то уже давно опубликовал бы её, а конкурс бы сделал для семи ферзей. Единственное моё преимущество в том, что до начала конкурса я уже написал перебор и посчитал с его помощью несколько чисел. Они опубликованы на этой странице ниже. Подумайте, кстати, почему я проиграл в прошлом конкурсе? Всё честно, а если Вам что-то не нравится, просто не обращайте на меня внимания и покиньте эту страницу. Разойдёмся с Миром.
  7. А если я выведу формулу, что делать? Ответ: когда выведете, тогда и поговорим. Если кто-то выведет формулу раньше окончания конкурса, то он завершится досрочно, а автор формулы, видимо, победит.
  8. Это «баян». В интернете полно исходников, мы в школе ещё эту задачу делали. Ответ: Даже если Вы в школе что-то делали, то максимум до n=10 или 15 (для совсем продвинутых). Эту задачу ещё никто не решил. В Интернете Вы не найдете ничего такого, что позволило бы Вам продвинуться хоть немного. «Баяном» это станет тогда, когда будет предоставлена явная формула. А сейчас такого рода рассуждения не более чем трёп пустой разговор.

Текущий рейтинг

Таблица ниже будет постоянно обновляться по мере поступления новых чисел. Внимание: прежде чем присылать число, убедитесь, пожалуйста, что до Вас его ещё никто не вывел. Удачи!

Таблица участников

Конкурс завершён.

  1. Zealint :: 07.05 :: n = 80 :: 56 ядер (2,6 GHz) :: 10 ч.
  2. Zealint :: 07.05 :: n = 75 :: 56 ядер (2,6 GHz) :: 6 ч. 6 м.
  3. Zealint :: 06.05 :: n = 70 :: 64 ядра (2,6 GHz) :: 2 ч. 53 м.
  4. Zealint :: 05.05 :: n = 60 :: 60 ядер (2,6 GHz) :: 53 м.
  5. Zealint :: 05.05 :: n = 55 :: 55 ядер (2,6 GHz) :: 30 м.
  6. Zealint :: 04.05 :: n = 54 :: 8 ядер (2,6 GHz) :: 2 ч. 20 м.
  7. alexBlack :: 03.05 :: n = 53 :: 1 ядро (1,6 GHz) :: 13 ч. 15 м.
  8. alexBlack :: 01.05 :: n = 52 :: 1 ядро (1,6 GHz) :: 16 ч.
  9. alexBlack :: 30.04 :: n = 51 :: 2 ядра (2,9 GHz) :: 5 ч. 10 м.
  10. Zealint :: 29.04 :: n = 50 :: 64 ядра (2,6 GHz) :: 26 ч. 34 м.
  11. Zealint :: 26.04 :: n = 42 :: 8 ядер (2,6 GHz) :: 33 ч. 25 м.
  12. alexBlack :: 24.04 :: n = 41 :: 2 ядра (2,9 GHz)::17ч. 20м. (с 38 по 41)
  13. alexBlack :: 24.04 :: n = 40 :: 2 ядра (2,9 GHz) ::
  14. alexBlack :: 24.04 :: n = 39 :: 2 ядра (2,9 GHz) ::
  15. alexBlack :: 24.04 :: n = 38 :: 2 ядра (2,9 GHz) ::
  16. alexBlack :: 23.04 :: n = 37 :: 2 ядра (2,9 GHz) :: 4 ч. 20 м.
  17. Zealint :: 23.04 :: n = 36 :: 8 ядер (2,6 GHz) :: 4 ч. 53 м.
  18. Zealint :: 22.04 :: n = 35 :: 2 ядра (3 GHz) :: 16 ч. 14 м.
  19. alexBlack :: 21.04 :: n = 34 :: 1 ядро (2,9 GHz) :: 4 ч.
  20. alexBlack :: 19.04 :: n = 33 :: 1 ядро (2,9 GHz) :: 4 ч. 10 м.
  21. alexBlack :: 19.04 :: n = 32 :: 1 ядро (2,9 GHz) :: 3 ч.
  22. alexBlack :: 18.04 :: n = 31 :: 1 ядро (1,6 GHz) :: ~8 ч.
  23. alexBlack :: 18.04 :: n = 30 :: 1 ядро (1,6 GHz) :: ~8 ч.
  24. Zealint :: 16.04 :: n = 29 :: 1 ядро (2,6 GHz) :: 6 ч. 6 м.
  25. alexBlack :: 15.04 :: n = 28 :: 1 ядро (2,9 GHz) :: 3687 с.
  26. alexBlack :: 15.04 :: n = 27 :: 1 ядро (2,9 GHz) :: 2602 с.
  27. alexBlack :: 15.04 :: n = 26 :: 1 ядро (2,9 GHz) :: 1706 с.
  28. Zealint :: 15.04 :: n = 25 :: 1 ядро (3 GHz) :: 5405 с.
  29. Zealint :: 14.04 :: n = 24 :: 1 ядро (3 GHz) :: 3798 с.
  30. alexBlack :: 13.04 :: n = 23 :: 1 ядро (1,6 GHz) :: 2052 с.
  31. alexBlack :: 13.04 :: n = 22 :: 1 ядро (1,6 GHz) :: 1123 с.
  32. alexBlack :: 13.04 :: n = 21 :: 1 ядро (1,6 GHz) :: 654 с.
  33. Zealint :: 12.04 :: n = 20 :: 1 ядро (2,67 GHz) :: 1680 с.
  34. Zealint :: 12.04 :: n = 15 :: 1 ядро (3 GHz) :: 130 с.

Для ориентира: программа, которая считала ответ для n=15 работала со сложностью O(n12). Для n=20 уже работала программа со сложностью O(n11). Чтобы ориентироваться в сложности лучше, можно обсуждать время работы программ в комментариях.

Таблица значений

  1. 4
  2. 832
  3. 22708
  4. 312956
  5. 2716096
  6. 17117832
  7. 84871680
  8. 349093856
  9. 1239869972
  10. 3905117168
  11. 11139611892
  12. 29224290600
  13. 71402912960
  14. 164029487484
  15. 357164398040
  16. 741835920276
  17. 1477798367368
  18. 2836053660668
  19. 5263672510684
  20. 9478352925488
  21. 16606678238496
  22. 28378012168908
  23. 47398421913600
  24. 77522788818316
  25. 124365738451680
  26. 195977208395580
  27. 303748457927000
  28. 463582807382736
  29. 697434075907504
  30. 1035256352634420
  31. 1517521355687872
  32. 2198354851112760
  33. 3149525540545556
  34. 4465340754179496
  35. 6268789672000200
  36. 8718985543275112
  37. 12020393279930400
  38. 16433877629761792
  39. 22290259302807700
  40. 30006374870365136
  41. 40104595602917300
  42. 53235736336244300
  43. 70206658745546392
  44. 92012392107526748
  45. 119874540287319196
  46. 155285624835663096
  47. 200061731591400456
  48. 256402868739653996
  49. 326964160566718884
  50. 414936937933564876
  51. 524143826614930088
  52. 659146400314780240
  53. 825370726096096944
  54. 1029248723087783480
  55. 1278382175175730400
  56. 1581726455456457436
  57. 1949802708715765760
  58. 2394934394370749612
  59. 2931519277634600260
  60. 3576331321283597364
  61. 4348866396076652064
  62. 5271724407012487004
  63. 6371045245979662116
  64. 7676988784016499040
  65. 9224280528369282176
  66. 11052810248193489712
  67. 13208310203912865056
  68. 15743096674420482872
  69. 18716907492532573788
  70. 22197814778572880876

Следите за конкурсами на моём блоге. Дальше будет сложнее и интереснее.

Информационные спонсоры

КиберФорум — форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных. Компьютерный форум.

Клуб ПРОграммистов — Форум программистов.

dxdy — Научный форум.

Обсуждение конкурса на форуме в этой теме.