Решение головоломки N-ферзей с помощью TypeScript
Задача N-ферзей — это классическая задача о размещении N ферзей на шахматной доске NxN таким образом, чтобы никакие два ферзя не атаковали друг друга. В этой статье мы рассмотрим решение этой головоломки с помощью TypeScript.
Проблема
Головоломка N-Queens — известная головоломка, которую изучали на протяжении веков. Впервые он был введен в 1848 году шахматистом Максом Беззелем и с тех пор пользуется популярностью. Задача проста: расставить N ферзей на шахматной доске NxN так, чтобы никакие два ферзя не атаковали друг друга. Проблема сложная, потому что ферзи могут двигаться по горизонтали, вертикали и диагонали, а это значит, что они могут атаковать любого другого ферзя в поле зрения.
Решение
Решение, которое мы рассмотрим, — это алгоритм поиска с возвратом. Поиск с возвратом — это общий алгоритмический метод, который включает поиск в наборе возможных решений до тех пор, пока не будет найдено правильное. В случае головоломки с N-ферзями мы будем использовать возврат для поиска всех возможных мест размещения ферзей, пока не найдем правильное решение.
Вот код TypeScript для нашего решения:
function solveNQueens(n: number): string[][] {
// create a 2D array to represent the board
const board: string[][] = Array.from(Array(n), () => new Array(n).fill("."));
// create a result array to store the final result
const result: string[][] = [];
// function backtrack to find all possible solutions
function backtrack(board: string[][], row: number): void {
// if we have reached the end of the board, we have found a solution
if (row === n) {
// add the solution to the result array
result.push(board.map((row) => row.join("")));
return;
}
// iterate through all the columns
for (let col = 0; col < n; col++) {
// if the position is valid (no queens in the same column or diagonal)
if (isValid(board, row, col)) {
// place a queen at the current position
board[row][col] = "Q";
// recursively move to the next row
backtrack(board, row + 1);
// remove the queen from the current position after we have finished exploring
board[row][col] = ".";
}
}
}
// helper function isValid to check if the current position is valid
function isValid(board: string[][], row: number, col: number): boolean {
// iterate through all the rows above the current row
for (let i = 0; i < row; i++) {
// if there is a queen in the same column, return false
if (board[i][col] === "Q") {
return false;
}
}
// iterate through the left diagonal
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
// if there is a queen in the same diagonal, return false
if (board[i][j] === "Q") {
return false;
}
}
// iterate through the right diagonal
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
// if there is a queen in the same diagonal, return false
if (board[i][j] === "Q") {
return false;
}
}
// if we have not found any queens in the same column or diagonal, return true
return true;
}
// call the backtrack function to start exploring all the possible solutions
backtrack(board, 0);
// return the result array
return result;
}
Разберем код построчно.
Объявление функции
function solveNQueens(n: number): string[][] {
Функция solveNQueens принимает целое число n в качестве входных данных и возвращает массив массивов строк, представляющих все различные решения головоломки N-ферзей.
Определение результата
const result: string[][] = [];
Мы определяем пустой массив result для хранения наших решений.
Функция возврата
function backtrack(board: string[][], row: number): void {
В функции backtrack реализован алгоритм поиска с возвратом. Он принимает двумерный массив board, представляющий шахматную доску, и целое число row, представляющее текущую оцениваемую строку.
if (row === n) {
result.push(board.map((row) => row.join('')));
return;
}
Если row равно n, мы нашли правильное решение, поэтому мы помещаем копию доски в result и возвращаемся.
for (let col = 0; col < n; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrack(board, row + 1);
board[row][col] = '.';
}
}
Если мы еще не нашли действительного решения, мы перебираем каждый столбец в текущей строке и проверяем, допустимо ли размещение ферзя в этой позиции, используя функцию isValid. Если размещение допустимо, мы помечаем эту позицию ферзем (board[row][col] = 'Q') и рекурсивно вызываем backtrack в следующем ряду (backtrack(board, row + 1)). После возврата рекурсивного вызова мы убираем ферзя с позиции (board[row][col] = '.') и переходим к следующему столбцу.
Функция isValid
function isValid(board: string[][], row: number, col: number): boolean {
Функция isValid проверяет, является ли данная позиция допустимым размещением ферзя на шахматной доске.
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') {
return false;
}
}
Сначала мы проверяем, есть ли ферзь в том же столбце, что и данная позиция. Если есть, размещение недействительно.
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') {
return false;
}
}
Затем мы проверяем, есть ли ферзь на той же диагонали, идущей из верхнего левого угла в нижний правый, что и данная позиция. Если есть, размещение недействительно.
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') {
return false;
}
}
Наконец, мы проверяем, есть ли ферзь на той же диагонали, идущей из верхнего правого угла в нижний левый, что и данная позиция. Если есть, размещение недействительно. Если ни одно из этих условий не выполняется, размещение считается действительным.
Инициализация платы
const board: string[][] = Array.from(Array(n), () => new Array(n).fill('.'));
Мы определяем массив board как двумерный массив n на n, заполненный '.'.
Вызов функции возврата
backtrack(board, 0);
Мы вызываем функцию backtrack с board и начальным row из 0.
Возврат результата
return result;
Мы возвращаем result, содержащее все различные решения головоломки N-Queens.
Пример использования
Вот несколько примеров использования функции solveNQueens:
console.log(solveNQueens(4)); // Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] console.log(solveNQueens(1)); // Output: [["Q"]]
Заключение
В этой статье мы рассмотрели решение головоломки N-Queens на TypeScript с использованием поиска с возвратом. Хотя решение относительно короткое, оно довольно сложное и включает много рекурсий. Однако, приложив немного практики и терпения, вы справитесь с этой и другими задачами поиска с возвратом.
