N ферзей - это увлекательная задача алгоритма: учитывая размер доски n x n, сколькими различными способами вы можете разместить n ферзей на доске так, чтобы ни одна из них не угрожала друг другу?

На этой неделе мы реализовали JavaScript-решение в Hack Reactor. В качестве дополнительного удовольствия нас познакомили с этим очень умным алгоритмом, созданным выпускником Hack Reactor. Этот алгоритм не только записывает nQueens в объявлении функции и включает H и R в качестве переменных (для Hack Reactor), но также был сделан достаточно коротким, чтобы поместиться в твит! Сначала я был полностью озадачен этим твитом. Потом я заинтересовался (читай: одержим) его пониманием. Давайте разберем то, что я с любовью назвал на этой неделе этим сумасшедшим твитом, чтобы мы могли понять магию 125 символов.

Что вам нужно знать, чтобы эта статья была содержательной:

  1. Что такое загадка N Queens. Эта замечательная статья Мартина Ричардса также окажется неоценимой для визуализации концепций, используемых в этом алгоритме, поскольку решение, которое он представляет, очень похоже на твит.
  2. Как байты информации представлены в виде битов с использованием двоичного кода.

3. Побитовые операторы, а именно |, ^, &, ~

4. Средний / продвинутый JavaScript

5. Будьте немного мазохистом 😜

За алгоритм, Бэтмен!

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

Изображение Ричардса ниже поможет лучше представить себе проблему.

Переменные

Q = Первоначально установленный на размер доски, которую вы хотите решить, эта переменная изменяется, чтобы стать маской, которую мы будем использовать, чтобы вычислить, где безопасно разместить нового ферзя.

u = Это набор битов, которые представляют любые левые диагональные конфликты, эквивалент переменной ld (левая диагональ) на изображении Ричардса выше. Любые из них, помещенные в этот набор битов, представляют конфликт для диагоналей этого поля - другими словами, ферзь уже находится в этом диагональном пространстве. Мы также можем представить этот набор битов в виде десятичного числа. На изображении Ричардса выше переменная ld на этом снимке во времени также может быть представлена ​​как десятичное число 24, так как оно оценивается как двоичное число 00011000.

ee = Это набор битов, которые представляют столбцы с ферзями, что эквивалентно переменной cols на изображении Ричардса выше. Любые, помещенные в эту коллекцию, представляют королеву, присутствующую где-то в соответствующем столбце. Эта коллекция также может быть представлена ​​в виде десятичного числа. Для начала это будет десятичное число 0, поскольку мы еще не поставили ферзя. Если мы в конце концов найдем верное решение, каждое пространство в этой коллекции будет иметь значение 1, что означает, что мы поместили ровно по одному ферзю в каждый столбец.

n = Это набор битов, которые представляют любые правые диагональные конфликты, эквивалент переменной rd (правая диагональ) на изображении выше. Любые из них, помещенные в этот массив, представляют собой конфликт - другими словами, ферзь уже находится в этом диагональном пространстве. Его тоже можно представить в виде десятичного числа.

s = счетчик решений. Это то, что мы в конечном итоге вернем, количество подходящих решений для платы любого размера, с которой мы работаем.

H = Это набор битов, представляющих безопасные места для размещения ферзя в нашей текущей строке, эквивалентный массиву Poss на диаграмме Ричардса. Нули означают, что мы не можем поместить ферзя в соответствующее пространство строки, потому что он будет конфликтовать либо с другим ферзем в этом столбце, либо с одной из левой или правой диагоналей. Значит, безопасно! Мы можем разместить здесь королеву. Эта коллекция также может быть представлена ​​в виде десятичного числа. Если H всегда равно 00000000, это означает, что ферзь не может быть безопасно размещен в текущем ряду - мы либо вышли за доску (нашли решение), либо зашли в тупик и должны вернуться назад и проверить другое решение.

R = Это единственный бит, место, которое мы обнаружили, было доступно в массиве H, где мы решаем разместить ферзя. Этот бит также может быть представлен как десятичное число, и он всегда будет степенью двойки, потому что один бит в двоичном формате всегда будет степенью двойки.

Алгоритм

Первоначально мы установим s равным нулю. Эта переменная s в самом первом вызове функции будет обновляться, когда рекурсивные вызовы вернутся с успешными решениями.

Чего ждать? Давайте сделаем этот код более читабельным:

Если мы еще не разместили ферзя где-либо на доске, набор диагональных битов u будет равен 0, поэтому оценка будет ложной.

В этом случае мы хотим создать набор битов из n бит, каждый бит которого имеет значение 1, что выполняется в строке 21 расширенного кода. Это будет наша маска, которая пригодится позже в алгоритме.

Если u не равно нулю, то оценка истинна, значит, мы уже разместили ферзя на доске и, следовательно, уже создали нашу маску: Q остается Q.

(u | ee | n) дает нам небольшую коллекцию, которая представляет собой совокупность различных способов, которыми королева может вступить в конфликт. Любой конфликт столбцов, конфликт левой диагонали или конфликт правой диагонали (те, что указаны в ee, u и n соответственно) будут представлены как один в этом новом наборе битов. Оператор ~ выполняет обратную «перестановку битов», при которой единицы становятся нулями, а нули - единицами. Когда мы объединяем этот перевернутый битовый массив с нашей маской, Q, H теперь равняется новому набору битов, где единицы представляют собой безопасные места, которые мы могли бы выбрать для размещения ферзя.

Обратите внимание, что в самый первый раз, когда мы вызываем нашу функцию, в первой строке каждый бит в H равен единице - все пробелы безопасны для размещения ферзя.

Пока есть место для размещения ферзя в текущей строке, представленной набором битов, имеющим хотя бы одну единицу,

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

Эта линия выполняет сразу несколько действий, поэтому давайте разберемся с ней.

Мы рекурсивно вызываем функцию с новыми, обновленными значениями для u, ee и n. Это пример перехода к следующему ряду, поскольку мы уже разместили ферзя в текущем ряду. Вы заметите, что u, ee и n работают с | R. Они обновляются с помощью нашей переменной R - места, которое мы выбрали для размещения нашего ферзя в текущей строке - внутри самого вызова рекурсивной функции. Q остается Q, помните, что это наша маска.

Но подождите, вы протестуете. Третий параметр имеет смысл - нам нужно добавить 1 в коллекцию столбцов в правильном месте, чтобы показать, что мы поместили ферзя в соответствующий столбец. Но во втором и четвертом параметрах есть что-то странное.

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

Наконец, все, что возвращает этот рекурсивный вызов, будет добавлено к s, счетчику наших решений. Если путь, по которому мы идем, возвращает действительное решение, s будет увеличиваться на 1. Если он не возвращает действительное решение, он увеличит s на 0.

И последнее волшебство - если вы подошли к концу возможности разместить ферзя в текущем ряду, то это происходит по одной из двух причин. Возможно, вы нашли верное решение. Поздравляю! В этом случае вы поместили ровно по одному ферзю в каждый столбец, и поэтому переменная столбца ee будет набором битов размером n, заполненным единицами, точно равным нашей маске (Q). Вы можете увеличить счетчик решений на true или на единицу.

С другой стороны, возможно, вы зашли в тупик - текущий путь размещенных вами ферзей никогда не приведет к правильному пути. Вы можете увеличить счетчик на false или на 0. В этом случае текущий рекурсивный вызов завершается, мы возвращаемся к предыдущей строке, все еще находящейся в ее цикле while, и проверяем, есть ли оставшиеся безопасные места, чтобы попробовать нового ферзя. размещение.

Святой побитовый, Бэтмен

Я надеюсь, что эта статья поможет пролить свет на волшебство этого алгоритма. Я определенно чувствую себя немного мудрее после того, как попробую это сделать. Главный реквизит создателю! Если этот алгоритм все еще сбивает с толку, я настоятельно рекомендую этот пошаговый обзор более легко читаемой реализации JavaScript.