Время: 3 недели (9 июня — 30 июня 2011 г.) Конкурс завершён досрочно. посмотреть рейтинг. Читать итоги.

Обсудить на форуме.

Предлагаю отдохнуть от метода матрицы переноса и перейти к задаче более переборной. Как понятно из названия, предлагаю снова заняться проблемой расстановки 6 ферзей, но на этот раз не на обычной доске, а на тороидальной. Прежде чем возразить, что похожая задача уже была и что повторяться не хорошо, ознакомьтесь с моими аргументами в её пользу, которые записаны ниже в этом посте. Я никогда не выбираю задачу по принципу «просто так».

Постановка задачи

Имеется шахматная доска размером n×n (n≥0, целое). Доска свёрнута в тор, то есть левая граница соединена с правой, а верхняя — с нижней. Сколькими способами можно расположить на такой доске 6 не бьющих друг друга ферзей? Когда ферзь доходит до края доски, он появляется с противоположной стороны. В качестве иллюстрации на рисунке ниже показано, какие клетки будет бить установленный на доске ферзь (звёздочка).

Как бьёт один ферзь на тороидальной доске

Здесь все пробиваемые клетки главной диагонали обозначены голубым цветом, а побочной — оранжевым. По вертикали и горизонтали ферзь бьёт так же, как если бы он стоял на обычной доске.

Пример одной правильной расстановки на доске 7×7 приводится на следующем ресунке. Всего их 196 штук для n=7.

Правильная расстановка на доске 7 на 7

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

Почему выбрана эта задача?

Во-первых, я учёл результаты голосования. Была выбрана задача на расстановку шахматных фигур, в которой придётся колдовать как над скоростью работы программы, так и серьёзно потрудиться над усовершенствование алгоритма, поскольку O(n7), как в алгоритме прошлого такого конкурса для наших целей, скорее всего, не подойдёт (да и не получится его так просто обобщить на случай тора). Здесь действительно придётся решать задачу «кто дальше» и она действительно является трудной. Хотя сложность решения полиномиальная, но степень полинома великовата для конечной цели (см. ниже).

Во-вторых. Предыдущий конкурс, связанный с ферзями, который проходил больше года назад закончился выводом формулы. Благодаря этой формуле один из самых известных в Мире любителей задач на расстановки шахматных фигур Vaclav Kotesovec из Чехии смог сформулировать ряд интересных гипотез о том, как будет выглядеть рекуррентное соотношение для любого фиксированного числа ферзей. Например, для 7 ферзей на обычной доске рекуррентное соотношение должно иметь 197-й порядок. Вряд ли это кто-то сможет проверить в ближайшем будущем, а само по себе соотношение без начальных данных мало о чём говорит.

Когда мы вывели формулу для 6 ферзей, Vaclav спросил, есть ли у меня какие-либо соображения по поводу 6 ферзей на тороидальной доске. Тогда я ответил «нет», и у меня действительно не было желания решать эту задачу. Но Vaclav всё равно смог угадать вид рекуррентного соотношения для этого случая. По его мнению порядок соотношения для 6 ферзей на торе равен 142. Само соотношение записано в его электронной книге на слайде 53 (качать с этой страницы). А на следующем записаны первые 35 начальных данных к нему. Не совсем понятно, начиная с какого номера работает рекуррентное соотношение, но для его проверки нам потребуется досчитать где-то до n=150 (хотя на странице 47 автор утверждает, что достаточно n=80, но пока не совсем ясно что это даст в плане вывода формулы, хотя это сильная подсказка к эффективному алгоритму). Разумеется, эта проверка будет не строгой, но если она будет пройдена, то это будет сильным подтверждением гипотезы. В таких задачах если что-то с чем-то сходится и это кажется красивым, то это почти всегда оказывается правильным.

В-третьих. В прошлом конкурсе принимало участие два человека. Нет, это не означает, что было скучно, было как раз-таки весело. Но спустя год пришли новые люди, думаю, им тоже интересно порешать такую задачу. Решать её придётся не с нуля, а скорее всего будет более оптимальным взять за основу алгоритм со сложностью O(n7), описанный здесь и ломать голову над его значительным ускорением (а перед этим придумать обобщение на случай тора, если это вообще возможно). Там мы еле-еле добрались до n=81 (хотя я помню, что машинной оптимизацией тогда не занимался).

В-четвёртых. В отличие от задачи про королевский баян, в этой вполне реально дойти до конца, до такого значения n, для которого либо гипотетическая формула начнёт работать (или не работать), либо вывести свою. Как выводить свою — не берите в голову, если не знаете, я это сделаю сам, и когда-нибудь расскажу об этом сверх наглом методе угадывания. Главная задача участников — соревноваться между собой по принципу «кто дальше». А там видно будет. Но конечная цель, которую преследую я — дойти до границ, где начинает работать рекуррентное соотношение.

В-пятых, среди ответов есть достаточно красивые числа. Интересно, их там ещё много в первой сотне? : )

Положения

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

Ограничений почти нет: делайте что хотите, считайте на чём угодно и как угодно. Побеждает тот, кто предоставит ответ для наибольшего возможного значения n. Задача сложная, поэтому я буду доверять участникам: считать их ответ правильным, если сам их ещё не получил. Чтобы ответы были действительно правильными конкурс будет проходить в полузакрытом режиме: таблица участников и новых значений будет обновляться раз в 4 дня.

  1. Предоставляя ответ для некоторого n участник должен сказать ответ также для всех значений k<n. Разумеется, не надо повторять те числа, которые уже записаны в таблице результатов ниже. Например, если лидер сказал ответ для n=20, а Вы посчитали до n=23, то ответ засчитывается только если Вы также называет ответ для n=21 и n=22.
  2. Конкурс завершается 30 июня 2011 г.
  3. Прошу не выкладывать на форуме ответы, которые ещё не опубликованы в этом посте, а также не обмениваться идеями решения задачи во время конкурса.
  4. Конкурс начинается с n=36, так как до n=35 ответы известны из книги, процитированной выше. Этих начальных данных вполне достаточно для проверки правильности работы программ участников. Повторить эти результаты не очень трудно.
  5. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

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

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

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

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

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

Таблица ниже будет обновляться раз в 4 дня.

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

Конкурс завершён досрочно (21-го июня).
Итоги.

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

  1. halyavin :: 21.06 :: n=81 :: 4 потока с ГТ (2.67 ГГц) :: 3043 с.
  2. halyavin :: 21.06 :: n=80 :: 4 потока с ГТ (2.67 ГГц) :: 4177 с.
  3. halyavin :: 21.06 :: n=79 :: 4 потока с ГТ (2.67 ГГц) :: 2680 с.
  4. halyavin :: 21.06 :: n=78 :: 4 потока с ГТ (2.67 ГГц) :: 3607 с.
  5. halyavin :: 21.06 :: n=77 :: 4 потока с ГТ (2.67 ГГц) :: 2343 с.
  6. halyavin :: 21.06 :: n=76 :: 4 потока с ГТ (2.67 ГГц) :: 3189 с.
  7. halyavin :: 21.06 :: n=75 :: 4 потока с ГТ (2.67 ГГц) :: 2049 с.
  8. halyavin :: 21.06 :: n=74 :: 4 потока с ГТ (2.67 ГГц) :: 2730 с.
  9. halyavin :: 21.06 :: n=73 :: 4 потока с ГТ (2.67 ГГц) :: 1791 с.
  10. halyavin :: 21.06 :: n=72 :: 4 потока с ГТ (2.67 ГГц) :: 2362 с.
  11. halyavin :: 21.06 :: n=71 :: 4 потока с ГТ (2.67 ГГц) :: 1546 с.
  12. halyavin :: 21.06 :: n=70 :: 4 потока с ГТ (2.67 ГГц) :: 2050 с.
  13. halyavin :: 21.06 :: n=69 :: 4 потока с ГТ (2.67 ГГц) :: 1332 с.
  14. halyavin :: 21.06 :: n=68 :: 4 потока с ГТ (2.67 ГГц) :: 1180 с.
  15. halyavin :: 21.06 :: n=67 :: 4 потока с ГТ (2.67 ГГц) :: 1123 с.
  16. halyavin :: 21.06 :: n=66 :: 4 потока с ГТ (2.67 ГГц) :: 1526 с.
  17. halyavin :: 21.06 :: n=65 :: 4 потока с ГТ (2.67 ГГц) :: 1009 с.
  18. halyavin :: 21.06 :: n=64 :: 4 потока с ГТ (2.67 ГГц) :: 1313 с.
  19. halyavin :: 21.06 :: n=63 :: 4 потока с ГТ (2.67 ГГц) :: 856 с.
  20. halyavin :: 21.06 :: n=62 :: 4 потока с ГТ (2.67 ГГц) :: 1116 с.
  21. halyavin :: 21.06 :: n=61 :: 4 потока с ГТ (2.67 ГГц) :: 729 с.
  22. halyavin :: 21.06 :: n=60 :: 4 потока с ГТ (2.67 ГГц) :: 950 с.
  23. halyavin :: 21.06 :: n=59 :: 4 потока с ГТ (2.67 ГГц) :: 616 с.
  24. halyavin :: 21.06 :: n=58 :: 4 потока с ГТ (2.67 ГГц) :: 784 с.
  25. halyavin :: 17.06 :: n=57 :: 4 потока с ГТ (2.67 ГГц) :: 6215 с.
  26. halyavin :: 17.06 :: n=56 :: 4 потока с ГТ (2.67 ГГц) :: 6647 с.
  27. halyavin :: 17.06 :: n=55 :: 4 потока с ГТ (2.67 ГГц) :: 4998 с.
  28. halyavin :: 17.06 :: n=54 :: 4 потока с ГТ (2.67 ГГц) :: 5122 с.
  29. halyavin :: 17.06 :: n=53 :: 4 потока с ГТ (2.67 ГГц) :: 4026 с.
  30. halyavin :: 17.06 :: n=52 :: 4 потока с ГТ (2.67 ГГц) :: 4015 с.
  31. halyavin :: 17.06 :: n=51 :: 4 потока с ГТ (2.67 ГГц) :: 3075 с.
  32. halyavin :: 17.06 :: n=50 :: 4 потока с ГТ (2.67 ГГц) :: 2949 с.
  33. Shamil :: 17.06 :: n=52 :: 4 поток c ГТ (3.00 ГГц) :: 413 м.
  34. Shamil :: 17.06 :: n=51 :: 4 поток c ГТ (3.00 ГГц) :: 335 м.
  35. Shamil :: 17.06 :: n=50 :: 4 поток c ГТ (3.00 ГГц) :: 299 м.
  36. halyavin :: 13.06 :: n=49 :: 4 потока с ГТ (2.67 ГГц) :: 3975 с.
  37. halyavin :: 13.06 :: n=48 :: 4 потока с ГТ (2.67 ГГц) :: 3600 с.
  38. halyavin :: 13.06 :: n=47 :: 4 потока с ГТ (2.67 ГГц) :: 3086 с.
  39. halyavin :: 13.06 :: n=46 :: 4 потока с ГТ (2.67 ГГц) :: 2724 с.
  40. halyavin :: 13.06 :: n=45 :: 4 потока с ГТ (2.67 ГГц) :: 2245 с.
  41. halyavin :: 13.06 :: n=44 :: 4 потока с ГТ (2.67 ГГц) :: 2069 с.
  42. halyavin :: 13.06 :: n=43 :: 4 потока с ГТ (2.67 ГГц) :: 1679 с.
  43. halyavin :: 13.06 :: n=42 :: 4 потока с ГТ (2.67 ГГц) :: 1535 с.
  44. halyavin :: 13.06 :: n=41 :: 4 потока с ГТ (2.67 ГГц) :: 1284 с.
  45. halyavin :: 13.06 :: n=40 :: 4 потока с ГТ (2.67 ГГц) :: 1124 с.
  46. halyavin :: 13.06 :: n=39 :: 4 потока с ГТ (2.67 ГГц) :: 907 с.
  47. halyavin :: 13.06 :: n=38 :: 4 потока с ГТ (2.67 ГГц) :: 806 с.
  48. halyavin :: 13.06 :: n=37 :: 4 потока с ГТ (2.67 ГГц) :: 670 с.
  49. halyavin :: 13.06 :: n=36 :: 1 поток (2.67 ГГц) :: 2995 с.

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

  1. 0
  2. 196
  3. 3072
  4. 42768
  5. 550000
  6. 3573856
  7. 25009344
  8. 102800672
  9. 454967744
  10. 1441238400
  11. 4811118592
  12. 12616778208
  13. 34692705648
  14. 79514466480
  15. 189770459200
  16. 392908083876
  17. 842040318416
  18. 1610365515264
  19. 3172863442176
  20. 5692888800000
  21. 10481865438304
  22. 17850315939984
  23. 31090665289152
  24. 50683412713024
  25. 84276635943600
  26. 132395024982128
  27. 211664845709312
  28. 322114921688736
  29. 497905815659648
  30. 737104418684900
  31. 1106567765992512
  32. 1599037256095344
  33. 2339918645810448
  34. 3309836284628640
  35. 4735336861548800
  36. 6572025179131344
  37. 9215856321962976
  38. 12574431761849888
  39. 17319514793330816
  40. 23271519881109600
  41. 31540135998722736
  42. 41794354001606032
  43. 55823671917333504
  44. 73043317150756036
  45. 96276650854650000
  46. 124527357217571040
  47. 162161669093668608
  48. 207533216147746320
  49. 267272302145494464
  50. 338730446364970000
  51. 431807970838585600
  52. 542344140105697008
  53. 684894582864672992
  54. 853060121971234176
  55. 1067936027669395200
  56. 1319865341334551936
  57. 1639017094598388208
  58. 2011069407505480308
  59. 2478635597540655104
  60. 3020807159075290000
  61. 3697084597825125936
  62. 4477382792276525648
  63. 5443887514000282624
  64. 6553883497784179392
  65. 7919746598354351600
  66. 9481574722259654112
  67. 11391569517886140672
  68. 13566681246288833424
  69. 16211215932802193184
  70. 19211258706514560000
  71. 22838749787442772608
  72. 26938986141359362532
  73. 31871064973340530080
  74. 37426844396562190544
  75. 44076950917288627200
  76. 51543789262830379008

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

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

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

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

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