В это статье мы на примере шахматной проблемы n-ферзей рассмотрим как соединить наши знания о рекурсивных функциях и представлении данных в виде деревьев для решения сложных проблем. Если вы не читали предыдущие статьи (рекурсия, деревья) то советую их изучить перед продолжением чтения этой статьи. Для решения задачи мы так же изучим еще пару интересных трюков: как с помощью рекурсии создавать деревья и как в них искать данные методом поиска с возвратом. Я надеюсь, что я заинтриговал вас. Приступим.

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

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

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

Ферзь ходит по красным клеткам

Приведем пример почти решенной задачи для доски 4 на 4. Попробуйте сами закончить это решение кликнув на нужной ячейке:

А вот одно из возможных решений для доски 8 на 8:

Задача не такая простая, как может показаться. К примеру, общее число расположения ферзей на доске 8 на 8 равняется 4 426 165 368. Разумеется, человек не будет решать эту задачу за счет простого перебора, но в любом случае при возрастании доски сложность увеличивается во много раз, и тут нам на помощь приходит компьютер.

Анализ проблемы

Разберем нашу проблему на составляющие.

Первое что приходит на ум при разборе любой шахматной проблемы это шахматная доска. Поскольку наша доска квадратная, она имеет только один параметр, который отвечает за высоту и ширину — назовем его размерность и обозначим n. Доска с размерностью n=8 имеет высоту и ширину в 8 клеток. Всего на данной доске 8×8=64 клетки:

Каждая клетка имеет координаты вида ряд:столбец. Она может быть пустой, или на ней может находится ферзь.

Ферзь атакует другого ферзя если они находятся на одном ряду, или на одной колонке, или на одной из диагоналей (слева-направо, справа-налево).

атак(x,y)⇔(ряд(x)=ряд(y))⊕(кол(x)=кол(y))⊕(диа_лп(x)=диа_лп(y))⊕(диа_пл(x)=диа_пл(y))

Решением является доска, которая удовлетворяет следующим условиям:

1. Количество установленных на доске ферзей равно размерности доски.
2. Ни один ферзь не атакует другого.

решена(доска)⇔(колво_ферзей=n)∧∀x.¬∃y.атак(x,y)

Алгоритм решения

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

Мы начинаем с пустой доски. Представьте себе доску с минимальной размерностью. n=1? Нет, слишком тривиально. n=2? Вот этот вариант нам подходит.

Взглянем еще раз на условие решения: на доске должно находиться n ферзей и ни один ферзь не должен атаковать другого. Начнем с первой части этого условия: надо поставить n фигурок. Как мы это сделаем?

Маленький шаг для человека, большой шаг для решения проблемы. Поставим ферзя в клетку с рядом 1 и колонкой 1 (1:1):

Поскольку у нас размерность доски n=2, то по условию нам остается поставить всего одну фигурку. Поставим ее в первую свободную клетку:

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

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

Опять уберем его и поставим в оставшуюся клетку, которую мы не попробовали — 2:2. Но и тут наш воинственный первый ферзь не дает соседу покоя атакуя его по диагонали:

Все ли варианты мы попробовали? Нет, еще можно переставить самого первого ферзя из клетки 1:1 на клетку 1:2 и попробовать решить с этой начальной позицией. Если и так не получится, то можно попробовать еще клетки 2:1 и 2:2 в качестве начальной позиции. Для доски с размерностью n=2 уже по этим вариантам можно заключить что решения не существует, но если мы посмотрим на решение для доски с размерностью n=8, которое мы приводили выше, то заметим, что там первая клетку свободна, следовательно менять позицию первого установленного ферзя имеет смысл.

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

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

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

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

Представим это визуально:

Решение

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

Самое очевидное это представить доску в виде матрицы размером n строк, в каждой строке n элементов. Но это можно сделать проще: в виде одного плоского массива n×n элементов. Каждый элемент этого массива представляет собой клетку. Клетка может иметь два состояния: пустая, с фигурой. Давайте условимся что пустая клетка будет представляться булевой константой false, а клетка с фигурой будет представляется булевой константой true. Для простоты давайте называть такие данные не массив а Board. Давайте попробуем представить доску с размерностью n=4, и решение для этой доски:

/** B представляет пустую клетку
  * @type {CellState}
  */
var B = false;

/** Q представляет клетку с ферзем
  * @type {CellState}
  */
var Q = true;

/** Пустая доска с размерностью n=4
  * @type {Board}
  */
var n4emptBrd = [B, B, B, B,
                 B, B, B, B,
                 B, B, B, B,
                 B, B, B, B];

/** Решение для доски с размерностью 4
  * @type {Board}
  */
var n4solBrd = [B, Q, B, B,
                B, B, B, Q,
                Q, B, B, B,
                B, B, Q, B];

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

Каждый раз вручную создавать доску в виде большого массива не удобно. Поэтому нам бы не помешала функция которая делала бы это за нас. Назовем ее createEmptyBoard. Реализовать ее просто: создаем пустой массив и заполняем его пустыми значениями n×n раз:

/** Создает пустую доску n*n элементов
  * @param  {Natural} n Размерность доски
  * @return {Board}
  */
function createEmptyBoard(n){
  var b = [];
  for(var i=0;i<n*n;i++){ b.push(B); }
  return b;
}
// Тесты для функции createEmptyBoard
(function(){
  console.log("Тест1:", createEmptyBoard(4).length==16);
})();

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

Все приготовления закончены и мы можем приступать к функции которая будет решать проблему n-ферзей. Это уже задачка посложнее. Для начала давайте подумаем что должна принимать и возвращать эта функция. По нашему алгоритму она принимает пустую доску и возвращает доску с решением. А если решения нету, как у доски с размерностью 2? Мы не обговорили этот момент при проектировании алгоритма, так что пусть это будет false.

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

Самый тривиальный случай для этой задачи это n=1. Тот самый, который мы проигнорировали при проектировании алгоритма. Решением для этой доски будет доска с одной клеткой, в которой установлен ферзь. Для доски с размерностью n=2 решения нету, мы это узнали при проектировании алгоритма. А для доски с размерностью n=4 мы уже записали решение в коде чуть выше.

Для того чтобы наши тесты сразу начали приносить пользу нам надо написать заглушку для функции. Кстати, мы забыли ее назвать, пусть она называется solve. Заглушка должна возвращать значение которая реальная функция может вернуть, поэтому пусть это будет false. Перенесем в код то, о чем мы сейчас рассуждали:

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску
  *                         Иначе false
  */
function solve(b){ return false; } // заглушка

(function(){
  console.log("Тест2:",
    solve(createEmptyBoard(1)).toString()==[Q].toString());

  console.log("Тест3:", solve(createEmptyBoard(2))==false);

  console.log("Тест4:",
    solve(createEmptyBoard(4)).toString()==n4solBrd.toString());
})();

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

Теперь самое время подумать над наполнением функции. В процессе разработки алгоритма мы заметили что он генерирует данные с древовидной структурой. Из предыдущей статьи мы научились мастерски обрабатывать такие данные используя функции со взаимной рекурсией. Напоминаю, для того чтобы обработать древовидные данные нам надо создать две функции. Одна из них оперирует над узлом дерева, который в контексте этой проблемы представляет собой доску, с установленными фигурками или без них. Вторая оперирует над потомками данной доски, которые мы получаем устанавливая фигурки в свободные клетки на данной доске. Первую назовем solveBrd, а вторую solveChilds. Обе эти функции вложим в нашу функцию solve с помощью замыкания, так же закомментируем заглушку за ненадобностью:

// function solve(b){return false}; // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){

  }

  // Ищет решения для списка потомков
  // @param {array of Board} lob
  // @return {Board | false}
  function solveChilds(lob){

  }

  return solveBrd(b);
}

Про замыкания можно почитать в Википедии.

Функция solveBrd принимает доску, которая может поступить из функции solve или из функции solveChilds, потому что мы используем взаимную рекурсию. Поскольку доска поступающая из solveChilds содержит в себе фигурки логично было бы узнать является ли она решением. Поэтому давайте пожелаем чтобы у нас была функция isSolved, которая принимает доску и возвращает true если доска является решением. Если поступившая в функцию solveBrd доска является решением задачи тогда ее надо вернуть, и функция solve завершит свою работу. В противном случае поочередно, для каждой свободной клетки на данной доске, надо поставить фигурку. Из получившегося массива досок надо удалить не валидные доски, так как обрабатывать их и их потомков не имеет смысла потому что они не могут содержать решения. Не валидной является доска на которой одна фигурка атакует другую. Давайте представим процесс формирования данных досок, у не валидных досок красный фон:

Функцию которая создает массив потомков данной доски и вырезает из него несостоятельные варианты назовем nextBoards. И наконец реализуем все это в виде кода:

function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {arrayof: Board} lob
  function solveChilds(lob){

  }

  return solveBrd(b);
}

И заглушки для нереализованных функций isSolved и nextBoard:

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
// !!!
function isSolved(b){ return false; } // Заглушка

/** Создает массив потомков данной доски
  * Все несостоятельные доски вырезаются
  * @param  {Board} b
  * @return {array of Board}
  */
// !!!
function nextBoards(b){ return []; } // Заглушка

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

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

Функция solveChilds очень похожа на функцию map, которую мы реализовали в статье о рекурсии. Она так же принимает массив и обрабатывает каждый элемент. Поэтому базовым случаем, как и в функции map, у нас будет пустой массив. А теперь подумаем что мы вернем в базовом случае. Поскольку функция solveChilds возвращается из solveBrd, которая в свою очередь возвращается из solve, получается что наша функция должна возвращать доску или false. Если мы достигли случая когда в solveChilds передается пустой массив значит у доски нету потомков в которых можно искать решения. Следовательно мы возвращаем false в базовом случае.

В рекурсивном случае нам необходимо узнать имеет ли первая доска в данном массиве потомков решение. Для этого мы передадим первую доску в функцию solveBrd, а не в isSolved. Потому что функция solveBrd будет искать решение не только в переданной доске, но и в ее потомках. Вызывая из функции solveChilds функцию solveBrd мы создаем цикл взаимной рекурсии. Если в первой доске нету решения тогда нам необходимо обработать следующую доску в данном массиве. Для этого уберем первую доску из массива потомков и с полученным массивом рекурсивно вызовем функцию solveChilds.

Вот и все, с функцией solve мы закончили. Эту функцию сложно объяснить на словах, поэтому давайте выразим ее в коде:

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску
  *                         Иначе false
  */
// function solve(b){return false}; // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {array of Board} lob
  // @return {Board | false}
  function solveChilds(lob){
    if(lob.length==0){
      return false; // базовый случай
    }else{
      // рекурсивный случай
      var first = lob[0];
      var rest  = lob.slice(1,lob.length);
      var tryBrd = solveBrd(first);
      if(tryBrd!=false){
        return tryBrd;
      }else{
        return solveChilds(rest);
      }
    }
  }

  return solveBrd(b);
}

У нас еще остались две нереализованные функции: isSolved и nextBoards. Давайте начнем с nextBoards. Она принимает доску и возвращает массив потомков этой доски. Этот массив формируется путем установки одной фигурки во все свободные клетки доски. Еще он должен содержать доски в которых ни один ферзь не атакует другого.

Получается что эта функция должна выполнять сразу два действия: заполнять пустые клетки на доске и фильтровать получившийся список. Давайте разделим эту функцию на две функции. Первая будет заполнять клетки на доске и возвращать массив получившихся досок. Назовем ее fillBlanks. Вторая будет фильтровать получившийся список, оставляя только валидные доски. Ее назовем keepOnlyValid. Поскольку наша функция nextBoards является просто комбинацией двух функций напишем к ней простой тест, который проверяет что комбинация этих функций возвращает тоже, что и nextBoards. Реализуем функцию nextBoards и заглушки для fillBlanks и keepOnlyValid:

/** Создает массив потомков данной доски
  * Все не валидные доски вырезаются
  * @param  {Board} b
  * @return {array.}
  */
  // function nextBoards(b){ return []; } // Заглушка
  function nextBoards(b){
  return keepOnlyValid(fillBlanks(b));
  }

  // Тесты для nextBoards
  (function(){
  console.log("Тест5:", (function(){
  var nb = nextBoards(createEmptyBoard(1));
  var fn = keepOnlyValid(fillBlanks(createEmptyBoard(1)));

  return nb.toString()==fn.toString();
  })());
  })();


  /** Создает массив досок в которых в каждой пустой клетке
  исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array of Board}
  */
  // !!!
  function fillBlanks(b){ return []; } // заглушка

  /** Фильтрует массив досок оставляя только те доски
  в которых ни одна фигурка не атакует другую
  * @param  {array of Board} lob
  * @return {array of Board}
  */
  // !!!
  function keepOnlyValid(lob){ return []; } // заглушка

Напишем функцию fillBlanks. Она довольно сложная, поэтому лучше начать с тестов. Самый простой случай это пустая доска с размерностью n=1. В этом случае наша функция должна вернуть массив который содержит одну доску, в единственной клетке которой должен стоять ферзь. Если мы передадим этой функции доску с размерностью n=1 в клетке которой стоит ферзь, тогда наша функция должна вернуть пустой массив. Если мы передадим функции пустую доску с размерностью n=2 тогда она должна вернуть нам четыре доски: в первой доске ферзь стоит в клетке 1:1, во второй в 1:2, в третьей в 2:1, в четвертой в 2:2. Я думаю нам хватит столько тестов, реализуем их:

// Тесты для fillBlanks
(function(){
  console.log(
    "Тест6:",
    (function(){
      var x = fillBlanks(createEmptyBoard(1));
      return x.length==1 && x[0][0]==Q;
    })());
  console.log("Тест7:", fillBlanks([Q]).length==0);
  console.log(
    "Тест8:",
    (function(){
      var x = fillBlanks(createEmptyBoard(2));
      return x.length==4 &&
        x[0].toString()==[Q,B,B,B].toString() &&
        x[1].toString()==[B,Q,B,B].toString() &&
        x[2].toString()==[B,B,Q,B].toString() &&
        x[3].toString()==[B,B,B,Q].toString()
    })());
})();

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

Для удобства так же давайте реализуем функцию которая принимает доску, координаты клетки (ряд и колонку) и значение клетки. В результате функция возвращает доску с установленным значением на клетке с данными координатами. Назовем ее fillSquare.

Реализуем функцию fillBlanks:

/** Создает массив досок в которых в каждой пустой клетке
    исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array of Board}
  */
// function fillBlanks(b){ return []; } // заглушка
function fillBlanks(b){
  // @param {Board}   brd Итерируемая доска
  // @param {Natural} pos Позиция
  function iter(brd, pos){
    if(brd.length==0){
      return []; // базовый случай
    }else{
      var first = brd[0];
      var rest  = brd.slice(1,brd.length);
      if(first!=Q){
        return [fillSquare(b, pos, Q)].concat(iter(rest, pos+1));
      }else{
        return iter(rest, pos+1);
      }
    }
  }

  var clone = b.slice(0, b.length); // Клонируем доску
  return iter(clone, 0);
}

И функцию fillSquare:

/** Ставит на доску в данную позицию данное значение
  * @param {Board}   b Доска
  * @param {Natural} p Позиция
  * @param {Q | B}   v Ферзь или пустая?
  */
function fillSquare(b,p,v){
  var clone = b.slice(0, b.length);
  clone[p]=v;
  return clone;
}

// Тесты для функции fillSquare
(function(){
  console.log("Тест9:",
    fillSquare([B],0,Q).toString()==[Q].toString());
})();

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

Для первого действия в Яваскрипте уже есть встроенная функция filter. Она вызывается у массива и принимает в качестве параметра функцию. В эту функцию поочередно передается каждый элемент данного массива и если она возвращает true то этот элемент будет в результирующем массиве.

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

Начнем с написания тестов:

(function(){
  console.log("Тест10:",
    keepOnlyValid([[B]]).toString()==[[B]].toString());

  console.log("Тест11:",
    keepOnlyValid([[Q]]).toString()==[[Q]].toString());

  console.log("Тест12:", function(){
    var lob = [
      [Q,Q,B,B],
      [B,Q,Q,B],
      [B,Q,B,Q]
    ];
    return keepOnlyValid(lob).length==0;
  }());
})();

В первых двух тестах передаем валидные доски и проверяем что они вернулись в результате. В последнем передаем список не валидных досок и проверяем что вернулся пустой массив. Перейдем к реализации самой функции и заглушки для функции isValid:

/** Фильтрует массив досок оставляя только те доски
    в которых ни одна фигурка не атакует другую
  * @param  {array of Board} lob
  * @return {array of Board}
  */
//function keepOnlyValid(lob){ return []; } // заглушка
function keepOnlyValid(lob){
  return lob.filter(function(b){ return isValid(b); });
}


/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
function isValid(b){ return false; }

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

Последняя и самая сложная функция на нашем пути — isValid. Посмотрим на заглушку которую мы написали выше. Наша функция принимает доску и возвращает true если она валидна, в противном случае false. Для того чтобы узнать валидна ли наша доска мы должны пробежаться по каждой фигурке и посмотреть атакует ли она другую. Фигурка может атаковать по горизонтали, диагонали и вертикали. Начнем с написания тестов для всех этих случаев:

// Тесты для функции isValid
(function(){
  // Не валидна если фигурки на одной горизонтали
  console.log("Тест13:", isValid([Q,Q,
                                  B,B])==false);
  // Не валидна если фигурки на одной вертикали
  console.log("Тест14:", isValid([Q,B,
                                  Q,B])==false);
  // Не валидна если фигурки на одной диагонали
  console.log("Тест15:", isValid([Q,B,
                                  B,Q])==false);
  console.log("Тест16:", isValid([B,Q,
                                  Q,B])==false);
  // Валидные доски
  console.log("Тест17:", isValid([Q])==true);
  console.log("Тест18:", isValid(n4emptBrd)==true);
  console.log("Тест19:", isValid(n4solBrd)==true);
})();

Для того чтобы определить атакует ли фигурка другую фигурку нам понадобятся три функции которые выясняли бы что фигурка не атакует по горизонтали, вертикали и диагоали. Назовем их notAttackByHorizontal, notAttackByVertical, notAttackByDiagonal.

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

С диагональю немножечко посложнее. Посмотрим на пример:

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

И, наконец, для того чтобы определить что фигурка не атакует никакую из других фигурок мы напишем рекурсивную функцию notAttackOthers. Она будет принимать позицию фигурки и массив позиций остальных фигурок и поочередно, используя три функции которые мы описали выше, проверять не атакует ли переданная фигурка кого либо из переданного списка.

Напишем заглушки для этих функций и вложим их внутрь isValid используя замыкание:

function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByHorizontal(pos1, pos2){} // заглушка

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByVertical(pos1, pos2){} // заглушка

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByDiagonal(pos1, pos2){} // заглушка

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  // !!!
  function notAttackOthers(thisPos, othersPos){} // заглушка
}

Поскольку мы имеем дело с плоским массивом нам понадобятся еще две вспомогательные функции которые определяют колонку и столбец по позиции в массиве и размерности доски. Назовем их posToRow и posToCol. Они будут принимать позицию фигурки в массиве и саму доску для определение ее размерности.

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

/** Считает размерность доски исходя из количества элементов
  * @param  {Board}   Доска
  * @return {Natural} Размерность доски
  */
function getBoardSize(board){
  return Math.sqrt(board.length);
}

// Тесты для функции getBoardSize
(function(){
  console.log("Тест20:", getBoardSize(n4emptBrd)==4);
})();

/** Переводит позицию фигурки в строку
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Строка на которой стоит фигурка. Zero-base
  */
function posToRow(pos, board){
  // Тут важно округлить в меньшую сторону
  return Math.floor(pos/getBoardSize(board));
}

// Тесты для функции posToRow
(function(){
  console.log("Тест21:", posToRow(1, n4emptBrd)==0);
})();

/** Переводит позицию фигурки в столбец
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Колонка на которой стоит фигурка. Zero-base
  */
function posToCol(pos, board){
  return pos%getBoardSize(board);
}

// Тесты для функции posToCol
(function(){
  console.log("Тест22:", posToCol(5, n4emptBrd)==1);
})();

Вернемся к нашим функциям проверки атаки. Алгоритм для функции проверки атак мы описали выше. А в функции notAttackOthers мы, используя рекурсию, поочередно проверим атакует ли фигурка другие фигурки из переданного массива позиций используя функции проверки атак. Если фигурка атакует какую-либо другую тогда наша функция вернет false. Реализуем их:

function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }
}

Теперь нам надо каким-то образом получить массив позиций всех фигурок на доске и определить что ни одна фигурка на доске не атакует другую.

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

/** Возвращает массив со всеми позициями фигурок на доске
  * @param  {Integer} curPos Текущая позиция
  * @param  {Board}  board  Доска
  * @return {array of Integer}
  */
function getFiguresPos(curPos, board){
  if(board.length==0){
    return [];
  }else{
    var first = board[0];
    var rest  = board.slice(1, board.length);
    if(first==Q){
      return [curPos].concat(getFiguresPos(curPos+1, rest));
    }else{
      return getFiguresPos(curPos+1, rest);
    }
  }
}

Мы уже близко к развязке. Нам осталось придумать способ как убедится что ни одна фигурка не атакует другую. Давайте подумаем, поскольку все фигурки у нас одинаковые то если одна не атакует ни какую другую, то и никакая другая не может атаковать ее. То есть, если мы проверили одну фигурку с координатами всех других фигурок, то другие фигурки проверять с координатой этой фигурки смысла не имеет. Получается, что мы можем очень удобно организовать данную функцию, давайте назовем ее checkFigures, в рекурсивном стиле:

1. Берем первую фигурку из маcсива позиций.
2. Проверяем не атакует ли она позиции в оставшийся части массива используя функцию notAttackOthers.
3. Рекурсивно вызываем эту же функцию, но с массивом уже без первого элемента.
4. Возвращаем результаты рекурсивного вызова и вызова функции notAttackOthers объединенные логическим оператором И.

Базовый случай у нас это пустой массив, возвращаем true. В противном случае мы проверяем не атакует ли эта фигурка кого-то еще и рекурсивно вызываем эту же функцию для проверки оставшегося массива. Звучит запутанно, но на деле все просто:

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array of Integer} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

Финальный штрих в функции isValid: вызываем функцию checkFigures с массивом позиций который нам отдает функция getFiguresPos и возвращаем результат. Вот полный вид функции isValid:

/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
//function isValid(b){ return false; }
function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array of Integer} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

  return checkFigures(getFiguresPos(0, b));
}

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

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
//function isSolved(b){ return false; } // Заглушка
function isSolved(b){
  return isValid(b) && getFiguresPos(0, b).length==getBoardSize(b);
}

(function(){
  console.log("Тест23:", isSolved(n4emptBrd)==false);
  console.log("Тест24:", isSolved(n4solBrd)==true);
})();

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

Запустим поиск для доски с размерностью 4:

  solve(createEmptyBoard(4));

У меня возвращается вот такой массив:

  [false,true,false,false,
   false,false,false,true,
   true,false,false,false,
   false,false,true,false]

Да, это решение. Попробуем поискать решение для доски с размерностью 2, функция должна вернуть false так как для этой доски нет решения:

  solve(createEmptyBoard(2));
  // > false

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

// Тест производительности,
// @param {Natural} startSizeOfBoard Начальный размер доски
// @param {Natural} endSizeOfBoard   Конечный размер доски
// @return {true} Тест закончился
function benchmark(startSizeOfBoard, maxSizeOfBoard){
  if(startSizeOfBoard>maxSizeOfBoard){
    return true;
  }else{
    console.log("Считаем для доски с размерностью:",
      startSizeOfBoard);

    var startTime = Date.now();
    var solution  = solve(createEmptyBoard(startSizeOfBoard));
    var endTime   = Date.now();

    console.log("Решение:", solution.toString());

    console.log("Затраченное время:",
      endTime - startTime, "миллисекунд");

    return benchmark(startSizeOfBoard+1, maxSizeOfBoard);
  }
}

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

Вот мои результаты для досок от 1 до 9 на компьютере МакБук Эйр (1.8 гигагерц «Intel core i5», 4 гигабайта ОЗУ):

benchmark(1,9);

Создавая такие тесты и строя графики на основе их данных мы можем узнать много интересного о задаче и алгоритме. Например, почему для поиска решения для доски с размерностью n=6 тратится 442 миллисекунды, а для доски с размерностью n=7 всего 5? Посмотрим на найденные решения:

Ага, решение доски с размерностью n=7 лежит прямо в первой ветке дерева, потому что ферзь стоит прямо в самой первой клетке. А вот с доской с размерность n=6 нам не повезло и алгоритму пришлось раскрывать больше ветвей дерева. Получается что с ростом размерности доски скорость поиска в нашем алгоритме не будет расти линейно, а что было бы если бы стояла задача найти все возможные решения? Подумайте над этим.

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

Заключение

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

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

А о методах ускорения поиска по деревьям поговорим в следующих статьях.

Забыл вас предупредить о еще одном замечательном событии в области онлайн-образования. 30 сентября началась сессия курса «Универсальная игровая программа» от Стенфордского университета. В данный момент я уже занимаюсь по двум курсам: «Введение в математическое мышление» и «Введение в историю человечества». Но я просто не могу пропустить этот курс и пожертвую своим временем чтобы приобрести знания, которые возможно помогут построить интеллект основанный исключительно на числах. Я думаю этот курс доставит массу удовольствия любому программисту.

Перевод описания со страницы курса:

Универсальные игровые программы (УИП) это компьютерные системы, которые могут играть в стратегические игры основываясь только на формальном описании игровых правил, которое они получают в процессе работы. Другими словами они не знают правил игры до момента ее начала. В отличии от специализированных компьютерных игроков, таких как «Дип блю», УИП не могут полагаться на алгоритмы которые разработаны специально для отдельных игр, они должны разработать их сами. Успешность игровой программы зависит не только от интеллекта ее разработчиков, но и от нее самой.

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

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

1. Выделить базовый случай.
2. Выделить рекурсивный случай и изменение входных данных.
3. Доказать что изменение данных в рекурсивных случаях в конечном счете приведет к базовому случаю.

Базовый случай это такое состояние входных данных при котором функция завершает свою работу.

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

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

Рассмотрим интересный пример — реализацию функции map. Это классическая функция, которая принимает массив данных d и применяет к каждому элементу функцию fn. В результате получается массив данных которые возвращает fn:

// @param {arrayof: x} d  Данные
// @param {x -> y}     fn Функция 
var map = function(d, fn){
  if(d.length==0){
    return [];
  }else{
    var first = d[0];
    var rest  = d.slice(1,d.length);
    return [fn(d[0])].concat(map(rest, fn));
  } 
};
// Проверим
var data = ["one", "two", "three"];
map(data, function(e){return "contains: " + e});

Разберем эту функцию в соответствии со структурой которую мы описали выше.

Базовый случай у нас это d.length==0, возвращается пустой массив.

В рекурсивной части происходят две интересные вещи:

• Создается массив с первым элементов входного массива и к нему конкатенируется результат рекурсивного вызова функции map.
• При рекурсивном вызове берется оставшаяся часть массива, без первого элемента, то есть количество данных уменьшается.

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

В этой функции рекурсивный вызов образует цикл натуральной рекурсии. Вот он показан наглядно:

Практика

Теперь вы. Попробуйте построить функцию filter которая принимает массив строк и строку поиска и возвращает все элементы массива которые равны этой строке поиска.

Взаимная рекурсия

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

Разобраться в этом трюке попробуем на примере. Представим себе кибер-дерево в узле которого может содержится яблоко в виде 1, 0 обозначает отсутствие яблока. Представим наше дерево визуально:

И в виде кода:

var n1 = {apple: 1, childs: []};
var n2 = {apple: 1, childs: []};
var n3 = {apple: 0, childs: []};
var n4 = {apple: 0, childs: []};

var n5 = {apple: 0, childs: [n1,n2,n3]};
var n6 = {apple: 1, childs: []};
var n7 = {apple: 1, childs: [n4]};

var root = {apple: 1, childs: [n7, n6, n5]};

Наша задача — пройтись по всему дереву и собрать все яблоки (единицы). Результат должен быть в виде массива яблок.

Алгоритм и решение

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

// @param  {object: tree} Дерево              
// @return {arrayof: 1}   Массив яблок
var harvest = function(tree){
  if(tree.apple==1){
    return [1];
  }else{
    // яблока нет
  }
};

А теперь подумаем о потомках нашего дерева. Потомки содержатся в поле childs нашего узла и представлены в виде массива таких же узлов. Давайте пожелаем чтобы у нас была функция harvestChilds которая обрабатывает этих потомков. Сделаем для нее заглушку, так мы сможем закончить нашу функцию harvest, а к новой функции вернемся позже:

// !!! - оставим для себя отметку что эта функция не реализована
var harvestChilds = function(){}

Вернемся к функции harvest. Если у нас есть яблоко сейчас мы возвращаем [1], то есть только яблоко текущего узла, при этом мы никак не учитываем потомков. Давайте представим что наша функция harvestChilds возвращает массив яблок потомков, если это так тогда нам надо к нашей единице прибавить этот массив. Мы это уже делали в функции map используя метод concat, в этом случае поступим так же.

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

// @param  {object: tree} Дерево              
// @return {arrayof: 1}   Массив яблок
var harvest = function(tree){
  if(tree.apple==1){
    return [1].concat(harvestChilds(tree.childs));
  }else{
    return harvestChilds(tree.childs);
  }
};
 
// !!! - оставим для себя отметку что эта функция не реализована
// @param  {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1}           Яблоки, собранные с потомков
var harvestChilds = function(childs){
  return [];
};

С harvest вроде разобрались, перейдем к harvestChilds. Как мы уже знаем она должна обработать каждый элемент массива потомков, который ей был передан, и вернуть массив яблок которые содержат эти потомки. Все это, опять же, похоже на нашу функцию map, поэтому давайте и эту функцию реализуем в рекурсивном стиле.

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

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

Что будем возвращать в базовом случае? Поскольку в процессе разработки функции harvest мы пожелали чтобы наша функция harvestChilds возвращала массив, тогда наш базовый случай будет возвращать пустой массив. Представим наши изменения в виде кода:

// !!! - оставим для себя отметку что эта функция не реализована
// @param  {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1}           Яблоки, собранные с потомков
var harvestChilds = function(childs){
  if(childs.length==0){
    return []; // базовый случай
  }else{
    //  рекурсивный случай
  }
};

Осталось самое интересное — рекурсивный случай. На входе нас ждет массив поддеревьев-потомков, каждый элемент которого надо обработать следующим образом: если у элемента есть яблоко тогда надо прибавить к результирующему массиву один элемент, если яблока нет... Так, стоп. Догадались? У нас уже есть функция которая это делает — harvest.

Мы подошли к ключевому моменту — созданию цикла взаимной рекурсии. Давайте взглянем на функцию harvest. Для своих потомков она вызывает функцию harvestChilds, а harvestChilds для каждого потомка будет вызывать функцию harvest и так далее. Таким образом мы обработаем все наше дерево слево-направо. Представим работу алгоритма визуально, зеленым подсвечиваются обработанные узлы на данном шаге:

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

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

// @param  {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1}           Яблоки, собранные с потомков
var harvestChilds = function(childs){
  if(childs.length==0){
    return []; // базовый случай
  }else{
    //  рекурсивный случай
    var first = childs[0];
    var rest  = childs.slice(1, childs.length);
    return harvest(first).concat(harvestChilds(rest));
  }
};

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

var n1 = {apple: 1, childs: []}
var n2 = {apple: 1, childs: []}
var n3 = {apple: 0, childs: []}
var n4 = {apple: 0, childs: []}
 
var n5 = {apple: 0, childs: [n1,n2,n3]}
var n6 = {apple: 1, childs: []}
var n7 = {apple: 1, childs: [n4]}
 
var root = {apple: 1, childs: [n7, n6, n5]}
 
// @param  {object: tree} Дерево              
// @return {arrayof: 1}   Массив яблок
var harvest = function(tree){
  if(tree.apple==1){
    return [1].concat(harvestChilds(tree.childs));
  }else{
    return harvestChilds(tree.childs);
  }
};
 
// @param  {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1}           Яблоки, собранные с потомков
var harvestChilds = function(childs){
  if(childs.length==0){
    return []; // базовый случай
  }else{
    //  рекурсивный случай
    var first = childs[0];
    var rest  = childs.slice(1, childs.length);
    return harvest(first).concat(harvestChilds(rest));
  }
};

Все вроде готово, давайте проверим. В нашем дереве root есть 5 яблок, следовательно если запуск функции harvest с деревом root возвратит нам меньше 5 яблок тогда мы что то сделали не так. Для продвинутых читателей предлагаю реализовать автоматический тест, а мы же просто запустим функцию:

harvest(root);

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

Выше мы представили визуально цикл натуральной рекурсии, давайте так же представим цикл взаимной рекурсии:

Практика

Небольшое задание для вас. Представим что у нас есть хтмл-дерево со структурой:

Представим эту структуру в виде объектов яваскрипта:

var p    = {element: "p", id: "some-text", childs: []};
var li1  = {element: "li", id: "list-el-1", childs: []};
var li2  = {element: "li", id: "list-el-2", childs: []};
var ol   = {element: "ol", id: "list", childs: [li1, li2]};
var img  = {element: "img", id: "pic-of-me", childs: []};
var body = {element: "body", id: "", childs: [p, ol, img]};
var html = {element: "html", id: "", childs: [body]};

Ваша задача будет вывести в консоль все id элементов в этой структуре. Если у элемента нету id тогда ничего выводить в консоль не надо.

Заключение

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

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

Я вас уже в какой-то мере наверное замучил своими приглашениями на курсы, но сегодня произошло то, о чем я просто не могу молчать. Сегодня началась очередная сессия курса «Введение в систематический программный дизайн» от замечательного инструктора Грегора Кинцалеса, профессора Университета Британской Колумбии.

Почему я вас не приглашаю на этот раз, а просто оповещаю? Я уже закончил предыдущую сессию этого курса недели 2 назад, и скажу вам что это стоило каждой секунды времени которые я потратил. Для тех из вас кто никогда не программировал и хочет получать 150 тысяч рублей сидя на жопе (в Москве), это замечательный шанс попробовать, курс не требует никакого предыдущего опыта написания программ. Но для тех кто уже схватил карпальный туннельный синдром это тоже будет интересным опытом, особенно если вы до этого не программировали в функциональном стиле или ваши познания в методах дизайна программ не особо большие.

Попозже я напишу обзор на этот курс, думаю что он будет довольно большим потому что я в восторге от этого курса. А сейчас краткий ввод в курс дела. В процессе обучения вы изучите интересный метод дизайна программ, который состоит из трех частей: анализ проблемы, разработка структур данных для представления информации, разработка функций через написание тестов. Главная мантра этого метода — информация в проблеме влияет на представление данных в программе, которые в свою очередь влияют на структуру функций и всей программы. Этот метод позволяет бороться с главной проблемой при написании программного обеспечения — сложностью. Лично я о многих проблемах в процессе работы стал думать по другому, в более правильном ключе. Вы так же познакомитесь с языком программирования Ракет, оседлаете рекурсивные функции, научитесь работать с деревьями. Так же будет куча практических заданий в которых вы реализуете кучу интересных программ, самые интересные задания в моей сессии были связаны с отображением фракталов и написанием программы которая автоматически решает Судоку.

Перевод части описания курса:

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

Чтобы создавать свои собственные программы вам нужно знать две вещи: как использовать язык программирования и его библиотеки, а так же более общий навык проектирования программ.

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

Давайте сблизимся с природой, посадим дерево и соберем с него урожай. Чувствую ваше сердцебиение участилось и рука тянется к ⌘Ctrlw↑. Спокойно, от клавиатуры мы отходить не будем, нашей окружающей средой будет Яваскрипт, память компьютера будет почвой, а урожаем будет информация.

Деревья — одна из наиболее распространенных структур данных в информатике. И это не просто так, деревья позволяют представлять большое количество информации и при этом они очень просты и понятны для человека.

Перед тем как дать формальное описание давайте посмотрим как они выглядят:

Это дерево? В реальном мире деревья растут вверх, вниз у них растут только корни. Все у этих компьютерщиков не так.

ожидание и реальность

Структура

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

• Корневой узел
• Узел
• Терминальный узел
• Связь

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

Узел^• это потомок корневого узла. В отличии от корневого узла он может иметь узел-родитель. Если провести аналогию с настоящим деревом то узел и его потомки это ветка.

Терминальный узел^• - конечный узел нашего дерева. Он может иметь родителя, но не может иметь потомков. Он как лист у настоящего дерева.

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

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

Представление данных

Деревья позволяют представлять данные имеющие иерархию. Приведем пример структуры каталогов, представленной в виде дерева:

Как мы видим в корне у нас находится каталог с именем / который содержит каталоги дир1 и дир2, дир1 в свою очередь содержит дир3.

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

Давайте приведем еще более интересный пример. Знаете ли вы что любую конечную и последовательную игру (конечное число ходов, игроки ходят последовательно) можно представить в виде дерева? Шахматы, шашки, крестики-нолики: все они имеют конечное число ходов и комбинаций, вопрос только какое это число. Клод Шеннон в 1950 году вычислил количество возможных не повторяющихся шахматных партий — 10¹²⁰. Этой особенностью пользуются компьютерные программы которые успешно могут противостоять лучшим игрокам — людям.

У нас нет таких вычислительных мощностей чтобы посчитать все дерево шахмат, поэтому давайте построим игровое дерево для вот этой незаконченной партии в крестики-нолики, ходит крестик:

Данная партия складывается не в пользу нолика, только в одном узле данного дерева он выигрывает. Построить такое дерево очень просто:

1. Берем данную доску и поочередно ставим в каждую пустую клетку знак текущего игрока. Получившийся массив досок это потомки исходной доски.
2. Если при установке знака произошел выигрыш текущего игрока, или ничья, тогда у этой доски не может быть потомков.
3. Для каждого потомка данной доски, в котором нету выигрыша или ничьи, делаем то что описано в пункте 1.

Реализация на Яваскрипте

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

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

Данные это имя каталога, у нас это: /, дир1, дир2, дир3. Это можно представить в виде строки:

"/"
"дир1"
"дир2"
"дир3"

Еще у нас должно быть место для связи, но сначала давайте рассмотрим эту связь отдельно. Каталог дир3 не содержит потомков, следовательно это должно быть представлено в виде каких то пустых данных. Каталог дир1 содержит каталог дир3, а каталог / содержит каталоги дир1 и дир2. Это тип данных с неопределенной длинной, ага, это же массив.

И все это, данные и связи, должны быть представлены в виде одного элемента. Комбинировать данные нам поможет массив, представим каталог дир3:

["дир3",[]]

Первый элемент массива это наши данные, второй это собственно связи. Поскольку дир3 не имеет связей вторым элементом массива идет пустой массив.

Непонятно и сложно? Яваскрипт спешит на помощь, в нем есть тип данных объект который представляет из себя ассоциативный массив. Давайте представим дир3 используя объект:

{name: "дир3", childs: []}

Стало намного понятнее, а теперь давайте представим всю структуру каталогов:

var dir3 = {name: "дир3", childs: []}
var dir2 = {name: "дир2", childs: []}
var dir1 = {name: "дир1", childs: [dir3]}
var root = {name: "/",    childs: [dir1, dir2]}

Тадамс, дерево посадили. Попробуем вывести имя каталога дир3, внука корневого каталога:

console.log(root.childs[0].childs[0].name)

Практика

Небольшая задача для вас. В Студии Лебедева продается набор матрешек «Матрешкус бланко», он состоит из шести матрешек: бит, байт, килобайт, мегабайт, гигабайт, терабайт. Представьте эти матрешки в виде древа, в корневом узле должен находится терабайт, далее его потомок гигабайт и так далее. Решение в комменты.

Дальше — больше

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