Классическая диаграмма проблем с рекурсивным возвратом во внешнем интерфейсе "N Queen"

алгоритм JavaScript

предисловие

в моей последней статье«Сложен ли полный алгоритм перестановки артикула внешнего интерфейса электронной коммерции? Изучите эту процедуру и полностью овладейте перестановкой и комбинацией. 》Рекурсивное решение перестановки и комбинации подробно объясняется в книге Я считаю, что друзья, которые видели его, в определенной степени овладели этой процедурой (студенты, которые не видели этого, вернутся и узнают~).

Это сложная задача на LeetCode, звучит страшно, но студенты, которые читали мою последнюю статью, должны помнить, что я упоминал, что использовал универсальный шаблон перестановки и комбинации для решения проблемы sku электронной коммерции.Можно ли этот универсальный шаблон быть используется для решения классической компьютерной задачи "N Queens"? Ответ положительный.

вопрос

Давайте сначала посмотрим на проблему.На самом деле, проблема не сложна для понимания:

Задача о n ферзях изучает, как разместить n ферзей на шахматной доске размером n на n так, чтобы ферзи не могли атаковать друг друга.

На рисунке выше показано решение задачи о восьми ферзях.

По заданному целому числу n выведите решения всех различных задач с n ферзями.

Каждое решение содержит явную схему размещения пешек для задачи с n ферзями, где «Q» и «.» обозначают ферзей и вакансии соответственно.

Пример:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

намекать:

Ферзь, пешка в шахматах, означает жену короля. Королева делает только одно: «ест детей». Когда она встречает пешку, которую можно съесть, она быстро бросается за ней. Конечно, она может делать от одного до семи шагов по горизонтали, вертикали и диагонали, а также может наступать или отступать. (Цитата из энциклопедии Baidu - Queen)

Исходный адрес LeetCode

идеи

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

То есть:

  1. В одном столбце неправильно.
[
  'Q', 0
  'Q', 0
]
  1. В левом верхнем углу -> правая нижняя диагональ, неправильно.
[
  'Q', 0
   0, 'Q'
]
  1. В нижней левой -> верхней правой диагонали, неправильно.
[
   0, 'Q'
  'Q', 0
]

Затем, основываясь на этой идее, мы можем превратить эту проблему в задачу «расставить ферзей ряд за рядом» и подумать о том, как проектировать рекурсивные функции?

дляn皇后для решения мы можем разработать функцию, которая принимает следующие параметры:

  1. rowIndexПараметр, представляющий ряд, в котором в данный момент пытается разместить ферзя.
  2. prevПараметр, представляющий положение ферзя, помещенного в предыдущий ряд, например[1, 3]Это означает, что ферзь строки 0 (индекс массива) помещается в позицию 1, а ферзь строки 1 помещается в позицию 3.

когдаrowIndex === nТо есть эта рекурсивная успешно разместила N Queen, полностью беспрепятственно дойдя до конца, каждый раз, когда размещение проходило наши условия ограничения, то на этот разprevпомещается в результате в глобальнуюresв массиве результатов.

Дерево

Здесь я пытаюсь рисовать инструментами4皇后Одно из решений рекурсивных дендрограмм, первая строка, которую я выбрал непосредственно для размещения ферзя放在2в качестве отправной точки, опуская放在1,放在3,放在4Дендрограмма в качестве отправной точки, иначе рекурсивное дерево будет слишком большим, чтобы соответствовать картинке.

Обратите внимание здесь放在x, для простоты понимания этоxНе индекс массива, а счет, основанный на 1.

После этой рекурсии получается результат:[1, 3, 0, 2].

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

выполнить

Идеалы всегда прекрасны.Хотя наше мышление пока ясно, есть еще несколько головных болей в конкретном кодировании.

После того, как текущая линия сбросила ферзя, следующая линия должна оценить три условия:

  1. Раньше на эту колонку нельзя было ставить ферзей.
  2. На диагональной линии 1, то есть «внизу слева -> вверху справа», ферзя нельзя поставить раньше.
  3. На диагональной линии 2, то есть «вверху справа -> внизу слева», ферзя нельзя поставить раньше.

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

对角线1:

Непосредственно через абсциссу и ординату этой точкиrowIndex + columnIndexПрибавьте, если равны, на той же диагонали 1:

image

对角线2:

Непосредственно через абсциссу и ординату этой точкиrowIndex - columnIndexВычитание, равное на той же диагонали 2:

image

так:

  1. использоватьcolumnsзапись массива размещенаСписокПодстрочный индекс, после его размещения, отметьте его как истинный напрямую.
  2. использоватьdia1запись массива размещенаДиагональ 1Подстрочный индекс, поставьте подстрочный индекс сразу после его размещенияrowIndex + columnIndexПросто отметьте это как истинное.
  3. использоватьdia2запись массива размещенаДиагональ 2Подстрочный индекс, поставьте подстрочный индекс сразу после его размещенияrowIndex - columnIndexПросто отметьте это как истинное.
  4. Аргументы для рекурсивных функцийprevПредставляет количество столбцов, в которых помещаются ферзи в каждой строке, например.prev[0] = 3Представляет ферзей строки 0 в столбце 3 и т. д.
  5. Каждый раз перед входом в рекурсивную функцию сначала ставить соответствующее значение текущего элементаСтолбец, Диагональ 1, Диагональ 2Нижний индекс помечен как истина и входит в рекурсивную функцию с помеченным состоянием. И после выхода из этой рекурсии нужно сбросить эти состояния в false, а затем войти в следующий цикл.

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

Таким образом, если рекурсивная функция прибывает успешноrowIndex === n, что означает выполнение всех предыдущих условий, т.n皇后получается раствор. ПучокprevЭтот одномерный массив можно восстановить до полного «двумерного массива», требуемого заголовком, с помощью вспомогательной функции.

/**
 * @param {number} n
 * @return {string[][]}
 */
let solveNQueens = function (n) {
  let res = []

  // 已摆放皇后的的列下标
  let columns = []
  // 已摆放皇后的对角线1下标 左下 -> 右上
  // 计算某个坐标是否在这个对角线的方式是「行下标 + 列下标」是否相等
  let dia1 = []
  // 已摆放皇后的对角线2下标 左上 -> 右下
  // 计算某个坐标是否在这个对角线的方式是「行下标 - 列下标」是否相等
  let dia2 = []

  // 在选择当前的格子后 记录状态
  let record = (rowIndex, columnIndex, bool) => {
    columns[columnIndex] = bool
    dia1[rowIndex + columnIndex] = bool
    dia2[rowIndex - columnIndex] = bool
  }

  // 尝试在一个n皇后问题中 摆放第index行内的皇后位置
  let putQueen = (rowIndex, prev) => {
    if (rowIndex === n) {
      res.push(generateBoard(prev))
      return
    }

    // 尝试摆第index行的皇后 尝试[0, n-1]列
    for (let columnIndex = 0; columnIndex < n; columnIndex++) {
      // 在列上不冲突
      let columnNotConflict = !columns[columnIndex]
      // 在对角线1上不冲突
      let dia1NotConflict = !dia1[rowIndex + columnIndex]
      // 在对角线2上不冲突
      let dia2NotConflict = !dia2[rowIndex - columnIndex]

      if (columnNotConflict && dia1NotConflict && dia2NotConflict) {
        // 都不冲突的话，先记录当前已选位置，进入下一轮递归
        record(rowIndex, columnIndex, true)
        putQueen(rowIndex + 1, prev.concat(columnIndex))
        // 递归出栈后，在状态中清除这个位置的记录，下一轮循环应该是一个全新的开始。
        record(rowIndex, columnIndex, false)
      }
    }
  }

  putQueen(0, [])

  return res
}

// 生成二维数组的辅助函数
function generateBoard(row) {
  let n = row.length
  let res = []
  for (let y = 0; y < n; y++) {
    let cur = ""
    for (let x = 0; x < n; x++) {
      if (x === row[y]) {
        cur += "Q"
      } else {
        cur += "."
      }
    }
    res.push(cur)
  }
  return res
}

Суммировать

Пока что первая тяжелая проблема молодого фронтенда решена.Ощущение, что у губернатора вскрылись две жилки?

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

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

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

❤️ Всем спасибо

1. Если эта статья была вам полезна, пожалуйста, поддержите ее лайком, ваш "лайк" - движущая сила моего творчества.

2. Подпишитесь на официальный аккаунт «Front-end from advanced to accept», чтобы добавить меня в друзья, я втяну вас в «Front-end группу расширенного обмена», все смогут общаться и добиваться прогресса вместе.

Категории