Приветствую, любознательные умы и начинающие искатели приключений в коде! 🌟 Сегодня мы отправляемся в путешествие, чтобы разгадать головоломку 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.
- Инициализируйте шахматную доску и начните со строки 0.
- Исследуйте каждую позицию в первом ряду, размещая ферзей там, где это безопасно.
- Перейдите ко второму ряду, разместите ферзей и повторяйте, пока не будут исследованы все ряды.
- Решения добавляются в массив
res
. - Код завершается, и
res
содержит конфигурации платы.
Поздравляем! 🎉
Вы разобрались с загадкой N-Queens и открыли для себя магию кода и стратегии. Каждое решение отражает гармоничное правление ферзей на шахматной доске. Ваши навыки кодирования одержали победу над этой королевской задачей.
Но путешествие продолжается! Головоломка N-Queens — это только начало. Погрузитесь в новые задачи, примите участие в сообществах программистов и позвольте вашей кодовой одиссее процветать.
Несколько важных/полезных ссылок 🔗
Ключевые слова SEO: N-Queens Puzzle, Coding Challenge, Logic, Solution, Chessboard, Backtracking, Решение проблем, Начинающие программисты, Code Adventure