Задачка о восьми ферзях



Рассмотрим такую любимую задачу на понимание алгоритмов, как «Задача о восьми ферзях». Классическое определение: «расставить на шахматной доске 8 ферзей так, чтобы ни один из них не бил другого». Ок, задачка очень популярная на разных собеседованиях, и Википедия нам сразу дает решение на моем любимом Python'е.

И это наверняка правильное решение с точки зрения обычного человека, но абсолютно бессмысленное с точки зрения хакера, и вот я вам расскажу почему:

Проанализируем алгоритм: используется классический поиск с возвратом, мы представляем область решений в виде графа, каждая вершина которого — это такое положение ферзя, в котором он не находится под боем, и не бьет уже расставленных на доске ферзей, т.е. нам надо только собрать все «ветки» состоящей ровно из восьми вершин. В качестве метода поиска этих «веток» автор нам предлагает классический алгоритм поиска в ширину, т.е. порядок обхода графа будет выглядеть так:



И как только алгоритм отработает мы получим все возможные решения.

Так в чем же проблема? В нашем случае, для доски 8х8, мы получим 92 различные решения, а представим, что, как это часто бывает в реальных задачах, мы не знаем размера доски. Если доска будет 25x25, как в тай сёги, тогда количество решений уже будет 275,986,683,743,434.

Таблица, зависимость количества решений от размера доски:
n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 .. 24 25 26
уникальных: 1 0 0 1 2 1 6 12 46 92 341 1,787 9,233 45,752 .. 28,439,272,956,934 275,986,683,743,434 2,789,712,466,510,289
различных: 1 0 0 2 10 4 40 92 352 724 2,680 14,200 73,712 365,596 .. 227,514,171,973,736 2,207,893,435,808,352 22,317,699,616,364,044

Что это будет значить для нашего скрипта? А то, что он уйдет в очень долгий поиск, и так-как все решения ему придется держать в уме, то уже через 15 мин Python будет съедать 300 мегабайтов памяти. Кто обладает мощным процессором и большим объемом оперативной памяти может проверить, завершиться ли этот процесс вообще...

А все, что нам требовалось при решении подобной задачи — подобрать правильный алгоритм обхода графа, которым в нашем случае оказался бы обычный поиск в глубину, тогда обход графа происходил бы в таком порядке:



А код был бы на много проще, и даже бы через 15 мин скрипт съедал бы ровно столько же памяти, как и через секунду после запуска. И вот бы как его реализация выглядела бы на Python'е:

def rc_queens(n_col, width, sol):
    if len(sol) == width:
        print sol
    else:
        for n_row in range(width):
            if (safe_queen(n_row, n_col, sol)):
                rc_queens(n_col+1, width, sol+[n_row])

def safe_queen(new_row, new_col, sol):
    for col in range(len(sol)):
        if (sol[col] == new_row or
            abs(col - new_col) == abs(sol[col] - new_row)):
                return 0
    return 1

if __name__ == "__main__":
    for n in range(8):
        rc_queens(1, 8, [n])

P.S. Это всего лишь взгляд на проблему со стороны хакера, может кто-то предложит взгляд со стороны «theoretical computer science»?
Метки:
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 25
  • +13
    Позвольте полюбопытствовать, за какие заслуги Вы называете себя «хакером»?
    • +7
      Наверное автор имеет ввиду полностью всесторонний взгляд. На любой случай, так сказать, потому что хакер никогда не может быть уверен, что его ждёт впереди.
    • +10
      Он въедливый и находит лучшее решение. Это и есть определение хакера.
    • +2
      Ох, извините, вы наверное не так поняли, я лишь написал, что «абсолютно бессмысленное с точки зрения хакера», что считаю, что настоящий специалист так бы к задаче не подходил.
      • +1
        А какая разница между «уникальными» и «различными» решениями?
        • +1
          «Различные» решения получаются из «уникальных» с помощью т.н. операций симметрии — т.е. переворотов доски или ее зеркального отражения.
        • +2
          Вся разница в том, что в википедии «теоретическое» решение, которое не учитывает окружающую среду (тобишь кто где и как будет запускать код), а у автора «практическое» решение. Т.е. предназначенное для применения в реальной жизни…

          Это что-то типа прототипирования… чтобы проверить идею я пишу скажем так «странный» код, в котором многие вещи захардкоденны и т.д. Но когда идея проверена и жизнеспособна, она реализуется в нормальном виде для реально применения с учетом расхода различных ресурсов…

          С этой точки зрения на мой взгляд пост странный, так как в Википедии дают торию… и того что там дают достаточно чтобы сделать выводы и «правльно» реализовать на практике.

          В общем К.О. в деле ??
          • –1
            Возможно и так, но интересно, почему они выбрали именно тот алгоритм?
            • 0
              потому что на первом курсе ее дают на backtracking
          • +4
            Извините, вы придумали сначала BFS, а потом героически заменили его на DFS. В чём суть? При чём даже картинки с вики стырили…
            • +5
              И за что минусуете человека? Он всё правильно пишет, данный «хакир» заменил поиск в ширину на поиск в глубину. Странно, что человек, называющий себя хакером, не знает таких элементарных вещей.
            • 0
              может кто-то предложит взгляд со стороны «theoretical computer science»?

              ладейные полиномы.
              • 0
                Ладейные полиномы — для решения задачи о ладьях.
                • 0
                  Здесь же достаточно хорошие решения дают алгоритмы с минимальными конфликтами и построенные на схожем принципе ГА. Не могу ручаться что решения лучшие, т.к. более детально эту задачу не исследовал, но работают они лучше обычных поисков.
              • +4
                Я не приметил, объект травли на википедии уже поправлен на православный вариант? Или потыкали предыдущего википедиста, а статью оставили в прежнем виде?
                • +1
                  Шахматная доска на картинке — просто чудо! :)
                  • 0
                    Человек, человеку — волк. А хакер, хакер — хакер.)
                    • +1
                      Зомби зомби зомби
                    • 0
                      Ооох помню делал на первом курсе курсовую по этой теме. Вот хоть убей не могу сейчас вспомнить алгоритм. Точно помню что если хорошенько проанализировать готовые решения можно сформулировать общую схему нахождения вариантов расстановки не тупым брутфорсом, а именно алогоритмом поиска. Также я использовал тот факт, что реально уникальных вариантов расстановки гораздо меньше. Их кажется 14 было или 12. Остальные получаются последовательным поворотом доски на 90 градусов и ее отражением. Жаль что это давно было и найти что-либо уже не возможно. А так было бы интересно сейчас взглянуть на свою стародавнюю программку на паскале.
                      • +4
                        автор не имеет представления о таких понятиях как алгоритм, википедия и хакер.
                        • +2
                          А я лет пятнадцать назад эту задачу решил на программируемом калькуляторе МК-52. Всю ночь зараза работала, вроде бы для доски 7х7 находила первое решение :)
                          • +8
                            > for col in range(len(sol))

                            Да когда ж вы все запомните-то?

                            for num, item in enumerate(seq)!
                            for num, item in enumerate(seq)!
                            for num, item in enumerate(seq)!
                            for num, item in enumerate(seq)!
                            for num, item in enumerate(seq)!
                            for num, item in enumerate(seq)!
                            for num, item in enumerate(seq)!
                            • 0
                              С точки зрения «theoretical computer science» проблему заездили уже вдоль и поперёк.
                              • +3
                                Я ничего не понял, о чём статья то? Автор разобрался в различиях алгоритмов поиска в глубину и в ширину? Какой ешё взгляд со стороны «theoretical computer science»? Обходы графов изучают на первом курсе универа.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.