Красиво расставляем 8 ферзей на доске — Журнал «Код» программирование без снобизма

Чем больше базовых алгоритмов знает программист, тем проще ему написать код для разных ситуаций. Один из таких алгоритмов — поиск с возвратом, или бэктрекинг. Мы его подробно разбирали в прошлой статье, вот короткая версия:

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

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

Что делаем

Сегодня будем решать задачу о расстановке ферзей на доске. Вкратце она звучит так:

как расставить на шахматной доске 8 ферзей так, чтобы они не пересекались по горизонтали, вертикали и диагонали?

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

Чтобы было нагляднее, сделаем веб-проект: страницу с шахматной доской и кнопкой поиска вариантов. При нажатии на кнопку компьютер будет показывать новый вариант расстановки ферзей, если он будет. Для этого нам понадобится HTML, CSS для страницы и JavaScript, на котором мы напишем основной скрипт. В итоге получится такое:

Готовим страницу

Страница будет состоять из трёх блоков:

заголовок и описание;
шахматная доска;
кнопка со счётчиком решений.

Ещё нам понадобится нормализатор, чтобы страница выглядела одинаково во всех браузерах, и jQuery, чтобы получить доступ к элементам страницы из скрипта. Доску пока пропустим и создадим страницу с первым и последним блоками:

Зачем нужен нормализатор CSS

<!DOCTYPE html>
<html lang="en" >
<head>
  <meta charset="UTF-8">
  <title>Расставляем 8 ферзей на доске</title>
  <!-- подключаем нормализатор -->
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/normalize/5.0.0/normalize.min.css">
  <!-- и свои стили -->
<link rel="stylesheet" href="style.css">

</head>
<body>
<!-- основной блок -->
<main class="container">
  <!-- шапка страницы -->
  <section class="header">
    <h1>Задача про 8 ферзей на доске</h1>
    <h3>Решение с использованием алгоритма бэктрекинга</h3>
  </section>
  <!-- раздел с доской -->
  <section class="board">
    
  </section>
  <!-- раздел с элементами управления -->
  <section class="control">
    <!-- кнопка поиска следующего решения -->
    <button class="next-btn">Следующее решение</button>
    <!-- сразу подписываем первое решение -->
    <p class="counter"> <span>Решение </span><span id="sol">1</span></p>
  </section>
</main>
  <!-- подключаем jQuery -->
  <script src='https://cdnjs.cloudflare.com/ajax/libs/jquery/3.1.0/jquery.min.js'></script>
  <!-- и свой скрипт -->
  <script  src="script.js"></script>

</body>
</html>

Чтобы создать доску, используем простую HTML-таблицу. Каждая ячейка этой таблицы — одна клетка на доске. В шахматах 8 рядов по 8 клеток, получается, нужно сделать таблицу из 8 строк и 8 столбцов. Так как доска чёрно-белая, сразу пометим цвет каждой ячейки. Если бы мы пользовались препроцессором, то создали бы доску за пару строк кода, но сейчас распишем всё полностью:

За что ты послал нам препроцессоры? Чем мы тебя прогневали?

<table class="chessboard">
  <!-- рисуем шахматную доску -->
  <tbody>
    <tr>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
    </tr>
    <tr>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
    </tr>
    <tr>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
    </tr>
    <tr>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
    </tr>
    <tr>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
    </tr>
    <tr>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
    </tr>
    <tr>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
    </tr>
    <tr>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
      <td class="black space"></td>
      <td class="white space"></td>
    </tr>
  </tbody>
</table>

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

Создаём стили

Задача стилей — сделать так, чтобы содержимое страницы выглядело красиво. Для этого мы делаем такое:

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

Оформим всё, кроме доски — ей займёмся отдельно. Единственная команда, которую мы ещё не использовали в других проектах — это border-collapse: collapse. Её смысл в том, что если у двух элементов таблицы есть общая граница, то вместо двух отдельных границ браузер нарисует одну.

/* общие настройки страницы */
.container {
  /* цвет и шрифт */
  color: #333;
  font-family: "Helvetica", sans-serif;
  /* выравнивание */
  text-align: center;
  align-items: center;
  /* включаем гибкую вёрстку и указываем направление */
  display: flex;
  flex-direction: column;
}

/* настройки блока с доской */
.board .chessboard {
  /* размеры доски */
  width: 400px;
  height: 400px;
  /* границы  */
  border: 2px solid #333;
  border-radius: 3px;
  /* пусть соседние границы отображаются как одна граница */
  border-collapse: collapse;
}

/* настройки кнопки */
.next-btn {
  /* отступы */
  margin-top: 2rem;
  padding: 0.5em 1rem;
  /* цвета */
  background-color: #3286a1;
  color: white;
  /* скругление кнопки */
  border: none;
  border-radius: 2px;
}

Теперь сделаем доску: пропишем цвета для классов чёрных и белых клеток и добавим общие настройки клеток. Содержимое клеток тоже пусть располагается по центру — сделаем это с помощью простого стиля для текста text-align: center. При желании можно было бы добавить диагональную штриховку, чтобы было совсем по-шахматному, но пока оставим так:

/* настройки клеток */
.board .space {
  /* высота и ширина каждой клетки */
  width: 50px;
  height: 50px;
  /* размер фигуры на клетке */
  font-size: 40px;
  /* выравниваем по центру */
  text-align: center;
  /* радиус скругления клетк */
  border-radius: 2px;
}

/* чёрная клетка */
.board .black.space {
  background-color: #a8a8a8b3;
}

/* белая клетка */
.board .white.space {
  background-color: #fff;
}

Прототипы

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

Мы делаем класс — это инструкция по созданию объектов.
У каждого класса есть какие-то методы. Метод — это то, что этот класс умеет делать.
Внутри этих методов мы вызываем другие внутренние методы класса.
Когда мы создаём объект, то он умеет всё, что умеет наш класс, но может появиться проблема с вызовом внутренних методов, которые относятся именно к классу, а не к этому объекту.
Чтобы объект мог всё равно вызывать нужные ему методы, используют прототипы.

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

👉 Если хотите лучше узнать про методы, классы и объекты, почитайте нашу статью про ООП — там всё проще и с примерами.

Теперь покажем, как это работает на практике. Первое, что мы напишем в скрипте, — общую функцию, которая будет отвечать за все элементы решения задачи. Задача этой функции — хранить в себе базовые настройки и решения:

// общая функция с решением
var nQueensSolver = function(n) {
  // количество ферзей
  this.queens_num = n;
  // столбцы на доске
  this.board_cols = [];
  // решения
  this.solutions = [];
  // стартовые настройки
  this.init();
};

// функция со стартовыми настройками
nQueensSolver.prototype.init = function() {
  // сколько ферзей — столько шагов в цикле
  for (var i = 0; i < this.queens_num + 1; i++) {
    // обнуляем столбцы
    this.board_cols[i] = 0;
  }
};

Разберём, что здесь происходит:

Мы создали функцию nQueensSolver() — она на вход получает количество ферзей, которые нужно расставить на доске.
Внутри этой функции появляются три переменные, с которыми она будет работать, — количество ферзей, столбцы на доске и решения с расстановками.
В конце функция вызывает свой внутренний метод init(), которой мы описываем сразу ниже.
Сейчас этот метод — внутренний для функции, и если мы создадим новую функцию на основе nQueensSolver()— она уже не получит доступа к этой функции.
Чтобы этот внутренний метод init()можно было вызвать из другой функции на основе старой, используют прототип с помощью команды .prototype — она поможет взять этот метод из исходной функции.

⭐ Логика работы скрипта

Общая логика работы будет такой:

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

Решения будем хранить так: раз на одном столбце доски может стоять только один ферзь, то позицию ферзя будем хранить в таком виде: номер столбца → номер строки в нём. Всего у нас 8 ферзей, поэтому будет 8 столбцов и каждый будет хранить всего одну цифру.

Пишем алгоритм поиска с возвратом

Алгоритм состоит из трёх базовых частей:

Функции проверки решения — подходит оно или нет.
Функции-генератора, которая предлагает новые решения.
Главной функции, которая запускает генератор и сохраняет найденные решения.

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

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

Задача главной функции — указать стартовую клетку, запустить генератор и вернуть все найденные решения.

Теперь запишем всё это на JavaScript:

// функция, которая проверяет очередное решение, если мы добавим нового ферзя на доску
nQueensSolver.prototype.promising = function(idx) {
  // получаем доступ к столбцам
  var col = this.board_cols; 
  // перебираем все варианты от нуля до указанного
  for (var k = 0; k < idx; k++) {
    // если новый ферзь стоит на той же строке, что и один из старых
    if (col[idx] === col[k] ||
      // или стоит на той же диагонали
      Math.abs(col[idx] - col[k]) === idx - k) {
      // возвращаем, что решение не подходит
      return false;
    }
  }
  // если скрипт дошёл досюда, то все проверки прошли и предложенное решение подходит
  return true;
};

// основная функция бэктрекинга
// на вход получает номер 
nQueensSolver.prototype.backtrack = function(i) {
  // добавляем в будущее решение очередного ферзя
  // если решение срабатывает — идём дальше
  if (this.promising(i)) {
    // если это был последний ферзь
    if (i === this.queens_num) { 
      // то сохраняем решение целиком
      this.solutions.push(this.board_cols.slice(1));
    // если ферзи ещё остались
    } else {
      // перебираем оставшихся ферзей
      for (var j = 0; j < this.queens_num + 1; j++) {
        // добавляем их на доску по одному на следующую клетку в колонке
        this.board_cols[i + 1] = j;
        // и рекурсисно запускаем эту же функцию
        this.backtrack(i + 1);
      }
    }
  }
};

// функция, которая решит задачу
nQueensSolver.prototype.solve = function() {
  // начинаем с первой клетки
  var starting_index = 0; 
  // запускаем бэктрекинг и ждём, пока он соберёт все решения
  this.backtrack(starting_index);
  // возвращаем все найденные решения
  return this.solutions;
};

Подготавливаем переменные

Чтобы скрипту было с чем работать, зададим нужные переменные и создадим виртуальную шахматную доску. Виртуальная доска нам нужна для того, чтобы мы могли расставить на ней ферзей, а затем легко отобразить это на странице. Здесь пригодится jQuery — с его помощью мы получим доступ ко всем клеткам таблицы и занесём их в отдельный массив.

Также мы сразу создадим новую функцию на основе старой и с её помощью сразу получим все решения — здесь как раз пригодятся прототипы, о которых мы говорили раньше. Они помогут новой функции получить доступ к методам с решениями.

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

// символ ферзя
var queen_piece = '♛';
// количество ферзей
var _n = 8;
// создаём новый объект, с помощью которого решим задачу
var solver = new nQueensSolver(_n);
// получаем сразу список решений
var result = solver.solve();

// создаём виртуальную доску для работы скрипта
function makeGrid() {
  // внутренняя функция, чтобы получить доступ к конкретной клетке
  function getCell(i, j) {
    return $("table tr").eq(i).find("td").eq(j);
  }
  // тут будет храниться виртуальная доска
  var $grid = []
  // перебираем все строки
  for (var i = 0; i < _n; i++) {
    // делаем их массивом
    var $row = []
    // перебираем отдельные клетки
    for (var j = 0; j < _n; j++) {
      // отправляем все клетки в строку
      $row.push(getCell(i, j))
    }
    // добавляем новую строку в виртуальную доску
    $grid.push($row);
  }
  // возвращаем виртуальную доску
  return $grid;
}

// очищаем предыдущее решение
function clearLastSolution(last) {
  // перебираем все столбцы
  for (var i = 0; i < last.length; i++) {
    // получаем номер строки
    var j = last[i];
    // очищаем клетку с этим адресом
    $grid[j - 1][i].html('');
  }
}

Рисуем ферзей и запускаем скрипт

Чтобы при запуске страницы мы сразу увидели первое решение, выберем первое решение из найденных и расставим ферзей на доске. За расстановку отвечает функция putQueenOnSolutionPieces() — она берёт очередное решение, перебирает столбцы и ставит ферзей на те клетки, которые указаны в столбцах.

Ещё сразу привяжем обработчик нажатия к кнопке, чтобы она сама убирала старое решение с доски, брала новое и расставляла ферзей по местам.

// основная функция
function initGrid() {
  // выбираем первое решение 
  var first = result[iter]; 
  // ставим ферзей на места из первого решения
  putQueenOnSolutionPieces(first);
}
// привязываем обработчик нажатия к кнопке
$('.next-btn').click(function() {
  // если на экране последнее решение
  if (iter === result.length - 1) {
    // выводим сообщение
    alert("Решения закончились! Обновите страницу, чтобы посмотреть их заново.");
  // если решения ещё есть 
  } else {
    // получаем текущее решение
    var last = result[iter];
    // убираем его с доски
    clearLastSolution(last);
    // берём следующее решение
    var next = result[++iter];
    // меняем номер решения в тексте под кнопкой
    $('#sol').text(iter + 1);
    // ставим ферзей по местам
    putQueenOnSolutionPieces(next);
  }
});

// функция, которая ставит ферзей по нужным местам
function putQueenOnSolutionPieces(solution) {
  // перебираем все строки в решении
  for (var i = 0; i < solution.length; i++) {
    // получаем позицию в столбце
    var j = solution[i];
    // ставим ферзя на клетку с полученными координатами
    $grid[j - 1][i].html(queen_piece);
  }
}

Последнее, что осталось сделать, — создать виртуальную доску и запустить скрипт:

// получаем виртуальную доску var $grid = makeGrid(); // номер текущего решения var iter = 0; // запускаем основную функцию initGrid();

Обновляем страницу и смотрим, как быстро алгоритм нашёл все возможные варианты расстановок:

Посмотреть работу алгоритма на странице проекта.

<!DOCTYPE html>
<html lang="en" >
<head>
  <meta charset="UTF-8">
  <title>Расставляем 8 ферзей на доске</title>
  <!-- подключаем нормализатор -->
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/normalize/5.0.0/normalize.min.css">
  <!-- и свои стили -->
<link rel="stylesheet" href="style.css">

</head>
<body>
<!-- основной блок -->
<main class="container">
  <!-- шапка страницы -->
  <section class="header">
    <h1>Задача про 8 ферзей на доске</h1>
    <h3>Решение с использованием алгоритма бэктрекинга</h3>
  </section>
  <!-- раздел с доской -->
  <section class="board">
    <table class="chessboard">
      <!-- рисуем шахматную доску -->
      <tbody>
        <tr>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
        </tr>
        <tr>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
        </tr>
        <tr>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
        </tr>
        <tr>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
        </tr>
        <tr>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
        </tr>
        <tr>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
        </tr>
        <tr>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
        </tr>
        <tr>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
          <td class="black space"></td>
          <td class="white space"></td>
        </tr>
      </tbody>
    </table>
  </section>
  <!-- раздел с элементами управления -->
  <section class="control">
    <!-- кнопка поиска следующего решения -->
    <button class="next-btn">Следующее решение</button>
    <!-- сразу подписываем первое решение -->
    <p class="counter"> <span>Решение </span><span id="sol">1</span></p>
  </section>
</main>
  <!-- подключаем jQuery -->
  <script src='https://cdnjs.cloudflare.com/ajax/libs/jquery/3.1.0/jquery.min.js'></script>
  <!-- и свой скрипт -->
  <script  src="script.js"></script>

</body>
</html>

/* общие настройки страницы */
.container {
  /* цвет и шрифт */
  color: #333;
  font-family: "Helvetica", sans-serif;
  /* выравнивание */
  text-align: center;
  align-items: center;
  /* включаем гибкую вёрстку и указываем направление */
  display: flex;
  flex-direction: column;
}

/* настройки блока с доской */
.board .chessboard {
  /* размеры доски */
  width: 400px;
  height: 400px;
  /* границы  */
  border: 2px solid #333;
  border-radius: 3px;
  /* пусть соседние границы отображаются как одна граница */
  border-collapse: collapse;
}

/* настройки кнопки */
.next-btn {
  /* отступы */
  margin-top: 2rem;
  padding: 0.5em 1rem;
  /* цвета */
  background-color: #3286a1;
  color: white;
  /* скругление кнопки */
  border: none;
  border-radius: 2px;
}

/* настройки клеток */
.board .space {
  /* высота и ширина каждой клетки */
  width: 50px;
  height: 50px;
  /* размер фигуры на клетке */
  font-size: 40px;
  /* выравниваем по центру */
  text-align: center;
  /* радиус скругления клетк */
  border-radius: 2px;
}

/* чёрная клетка */
.board .black.space {
  background-color: #a8a8a8b3;
}

/* белая клетка */
.board .white.space {
  background-color: #fff;
}

// общая функция с решением
var nQueensSolver = function(n) {
  // количество ферзей
  this.queens_num = n;
  // столбцы на доске
  this.board_cols = [];
  // решения
  this.solutions = [];
  // стартовые настройки
  this.init();
};

// функция со стартовыми настройками
nQueensSolver.prototype.init = function() {
  // сколько ферзей — столько шагов в цикле
  for (var i = 0; i < this.queens_num + 1; i++) {
    // обнуляем столбцы
    this.board_cols[i] = 0;
  }
};

// функция, которая проверяет очередное решение, если мы добавим нового ферзя на доску
nQueensSolver.prototype.promising = function(idx) {
  // получаем доступ к столбцам
  var col = this.board_cols; 
  // перебираем все варианты от нуля до указанного
  for (var k = 0; k < idx; k++) {
    // если новый ферзь стоит на той же строке, что и один из старых
    if (col[idx] === col[k] ||
      // или стоит на той же диагонали
      Math.abs(col[idx] - col[k]) === idx - k) {
      // возвращаем, что решение не подходит
      return false;
    }
  }
  // если скрипт дошёл досюда, то все проверки прошли и предложенное решение подходит
  return true;
};

// основная функция бэктрекинга
// на вход получает номер 
nQueensSolver.prototype.backtrack = function(i) {
  // добавляем в будущее решение очередного ферзя
  // если решение срабатывает — идём дальше
  if (this.promising(i)) {
    // если это был последний ферзь
    if (i === this.queens_num) { 
      // то сохраняем решение целиком
      this.solutions.push(this.board_cols.slice(1));
    // если ферзи ещё остались
    } else {
      // перебираем оставшихся ферзей
      for (var j = 0; j < this.queens_num + 1; j++) {
        // добавляем их на доску по одному на следующую клетку в колонке
        this.board_cols[i + 1] = j;
        // и рекурсисно запускаем эту же функцию
        this.backtrack(i + 1);
      }
    }
  }
};

// функция, которая решит задачу
nQueensSolver.prototype.solve = function() {
  // начинаем с первой клетки
  var starting_index = 0; 
  // запускаем бэктрекинг и ждём, пока он соберёт все решения
  this.backtrack(starting_index);
  // возвращаем все найденные решения
  return this.solutions;
};

// символ ферзя
var queen_piece = '♛';
// количество ферзей
var _n = 8;
// создаём новый объект, с помощью которого решим задачу
var solver = new nQueensSolver(_n);
// получаем сразу список решений
var result = solver.solve();

// создаём виртуальную доску для работы скрипта
function makeGrid() {
  // внутренняя функция, чтобы получить доступ к конкретной клетке
  function getCell(i, j) {
    return $("table tr").eq(i).find("td").eq(j);
  }
  // тут будет храниться виртуальная доска
  var $grid = []
  // перебираем все строки
  for (var i = 0; i < _n; i++) {
    // делаем их массивом
    var $row = []
    // перебираем отдельные клетки
    for (var j = 0; j < _n; j++) {
      // отправляем все клетки в строку
      $row.push(getCell(i, j))
    }
    // добавляем новую строку в виртуальную доску
    $grid.push($row);
  }
  // возвращаем виртуальную доску
  return $grid;
}

// очищаем предыдущее решение
function clearLastSolution(last) {
  // перебираем все столбцы
  for (var i = 0; i < last.length; i++) {
    // получаем номер строки
    var j = last[i];
    // очищаем клетку с этим адресом
    $grid[j - 1][i].html('');
  }
}

// основная функция
function initGrid() {
  // выбираем первое решение 
  var first = result[iter]; 
  // ставим ферзей на места из первого решения
  putQueenOnSolutionPieces(first);
}
// привязываем обработчик нажатия к кнопке
$('.next-btn').click(function() {
  // если на экране последнее решение
  if (iter === result.length - 1) {
    // выводим сообщение
    alert("Решения закончились! Обновите страницу, чтобы посмотреть их заново.");
  // если решения ещё есть 
  } else {
    // получаем текущее решение
    var last = result[iter];
    // убираем его с доски
    clearLastSolution(last);
    // берём следующее решение
    var next = result[++iter];
    // меняем номер решения в тексте под кнопкой
    $('#sol').text(iter + 1);
    // ставим ферзей по местам
    putQueenOnSolutionPieces(next);
  }
});

// функция, которая ставит ферзей по нужным местам
function putQueenOnSolutionPieces(solution) {
  // перебираем все строки в решении
  for (var i = 0; i < solution.length; i++) {
    // получаем позицию в столбце
    var j = solution[i];
    // ставим ферзя на клетку с полученными координатами
    $grid[j - 1][i].html(queen_piece);
  }
}

// получаем виртуальную доску
var $grid = makeGrid();
// номер текущего решения
var iter = 0;
// запускаем основную функцию
initGrid();

Алгоритмы — основа разработки

Изучите алгоритмы, чтобы легко проходить ИТ-собеседования и делать более совершенный софт. Старт — бесплатно. После обучения — помощь с трудоустройством.

Новый уровень тут