Приветствую, любознательные умы и начинающие искатели приключений в коде! 🌟 Сегодня мы отправляемся в путешествие, чтобы разгадать головоломку N-Queens. Представьте себе ферзей, управляющих шахматной доской без конфликтов — головоломка, одновременно интригующая и сложная. Наша миссия состоит в том, чтобы демистифицировать эту загадку, и в конце концов вы овладеете искусством гармоничного размещения ферзей.

Королевский вызов 🧐

Стратегическое размещение ферзей

Головоломка с N-ферзями ставит перед нами задачу разместить N ферзей на шахматной доске N x N так, чтобы ни один ферзь не атаковал другого. Проще говоря, в каждом ряду, столбце и диагонали может находиться только один ферзь. Не волнуйтесь, если это звучит сложно; мы разберем его шаг за шагом.

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

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

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

Пример 1:

Вход: n = 4

Вывод: [[«.Q..»,…Q», «Q…»,»..Q.»] , [«..Q.», «Q…», «…Q», «Q». ..»]]

Пример 2:

Вход: n = 1

Вывод: [["Q"]]

Наша стратегия 💃

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

Кодовое путешествие 🚀

Теперь давайте изучим код, который воплощает нашу стратегию в жизнь. Взгляните на следующий фрагмент кода JavaScript. Он создает различные конфигурации доски — решение головоломки N-Queens. Представьте, как ферзи элегантно выходят на шахматную доску, образуя красивые узоры.

const solveNQueens = function (n) {
  const arr = [...new Array(n)].map(ele => new Array(n).fill('.'));
  const row = 0;
  const res = [];
function nQueen(arr, row) {
    if (row >= n) {
      res.push([...arr].map(ele => ele.join('')));
      return res;
    }
    for (let j = 0; j < n; j++) {
      if (isSafe(arr, row, j)) {
        arr[row][j] = 'Q';
        nQueen(arr, row + 1);
        arr[row][j] = '.';
      }
    }
  }
  nQueen(arr, row, n);
  function isSafe(arr, row, column) {
    // Check in same column
    const columnArr = arr.map(curr => curr[column]);
    if (columnArr.includes('Q')) {
      // console.log(
      //  `Here's the array = ${arr} and not safe for ${row}, ${column} at column check`
      //);
      return false;
    }
    // Check in same row
    if (arr[row].includes('Q')) {
      // console.log(
      //  `Here's the array = ${arr} and not safe for ${row}, ${column} at row check`
      //);
      return false;
    }
    // Check in top left diagnal
    let i = row,
      j = column;
    while (i >= 0 && j >= 0) {
      if (arr[i--][j--] === 'Q') {
        // console.log(
        //  `Here's the array = ${arr} and not safe for ${row}, ${column} at top left check`
        //);
        return false;
      }
    }
    // Check in bottom right diagnal
    (i = row), (j = column);
    while (i < n && j < n) {
      if (arr[i++][j++] === 'Q') {
        // console.log(
        //  `Here's the array = ${arr} and not safe for ${row}, ${column} at bottom right check`
        //);
        return false;
      }
    }
    // Check in top right diagnal
    (i = row), (j = column);
    while (i >= 0 && j < n) {
      if (arr[i--][j++] === 'Q') {
        // console.log(
        //  `Here's the array = ${arr} and not safe for ${row}, ${column} at top right check`
        //);
        return false;
      }
    }
    // Check in bottom left diagnal
    (i = row), (j = column);
    while (i < n && j >= 0) {
      if (arr[i++][j--] === 'Q') {
        // console.log(
        //  `Here's the array = ${arr} and not safe for ${row}, ${column} at bottom left check`
        //);
        return false;
      }
    }
    return true;
  }
  return res;
};

Давайте разберем код шаг за шагом:

1. `constsolveNQueens = function (n) {`: Эта строка определяет функцию с именем `solveNQueens`, которая принимает целое число `n` в качестве аргумента.

2. `const arr = […new Array(n)].map(ele =› new Array(n).fill('.'))`: эта строка инициализирует двумерный массив `arr` size `n` x `n`, где каждый элемент изначально установлен в `'.'`. Этот массив будет представлять шахматную доску.

3. `function nQueen(arr, row) {`: определяет внутреннюю функцию `nQueen`, которая принимает `arr` (массив шахматной доски) и текущую `строку` в качестве параметров. Эта функция будет рекурсивно исследовать позиции для размещения ферзей на шахматной доске.

4. `if (row ›= n) { …`: это условие проверяет, все ли ферзи размещены (когда `row` достигает `n`). Если значение равно true, решение помещается в массив res путем преобразования двухмерного массива arr в визуальное представление шахматной доски с ферзями, использующими Q, и пустыми местами, использующими Q.

5. `for (пусть j = 0; j ‹ n; j++) { …`: этот цикл перебирает каждый столбец текущей строки. Он проверяет безопасность размещения ферзя в текущей позиции с помощью функции `isSafe`.

8. `nQueen(arr, row, n)`: вызывает функцию `nQueen`, чтобы начать процесс размещения ферзей на шахматной доске. Начальная `строка` установлена ​​на 0.

9. `function isSafe(arr, row, column) { … }`: определяет функцию `isSafe`, которая проверяет, безопасно ли размещать ферзя в заданных `строке` и `столбце` на шахматная доска.

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

11. `return true`: если текущая позиция безопасна, функция возвращает `true`.

12. Оператор `return res` вне внутренней функции возвращает массив решений (`res`) после изучения всех возможных конфигураций.

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

Пожалуйста, дайте мне знать, если у вас есть какие-либо вопросы или если вы хотите, чтобы я объяснил какую-то конкретную часть более подробно!

Пример пробного прогона

Следуя Пути Королевы 🎲. Давайте запустим код для n = 4.

  1. Инициализируйте шахматную доску и начните со строки 0.
  2. Исследуйте каждую позицию в первом ряду, размещая ферзей там, где это безопасно.
  3. Перейдите ко второму ряду, разместите ферзей и повторяйте, пока не будут исследованы все ряды.
  4. Решения добавляются в массив res.
  5. Код завершается, и res содержит конфигурации платы.

Поздравляем! 🎉

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

Но путешествие продолжается! Головоломка N-Queens — это только начало. Погрузитесь в новые задачи, примите участие в сообществах программистов и позвольте вашей кодовой одиссее процветать.

Несколько важных/полезных ссылок 🔗

Ключевые слова SEO: N-Queens Puzzle, Coding Challenge, Logic, Solution, Chessboard, Backtracking, Решение проблем, Начинающие программисты, Code Adventure