Задача о n-ферзях
В это статье мы на примере шахматной проблемы n-ферзей рассмотрим как соединить наши знания о рекурсивных функциях и представлении данных в виде деревьев для решения сложных проблем. Если вы не читали предыдущие статьи (рекурсия, деревья) то советую их изучить перед продолжением чтения этой статьи. Для решения задачи мы так же изучим еще пару интересных трюков: как с помощью рекурсии создавать деревья и как в них искать данные методом поиска с возвратом. Я надеюсь, что я заинтриговал вас. Приступим.
Постановка задачи
Для начала определим задачу. На шахматной доске с заданным размером n клеток по ширине и n клеток по высоте, всего n×n клеток, необходимо расставить n ферзей так, чтобы каждый ферзь не атаковал друг друга. Для простоты поставим себе задачу найти первое возможное решение.
На какой клетке, черной или белой, стоит ферзь не имеет значения. Если вы не знакомы с правилами шахмат, то ферзь может атаковать и ходить по своей колонке, своему ряду и по диагонали.
Ферзь ходит по красным клеткам
Приведем пример почти решенной задачи для доски 4 на 4. Попробуйте сами закончить это решение кликнув на нужной ячейке:
Кликните на клетку где должен стоять ферзь
А вот одно из возможных решений для доски 8 на 8:
Задача не такая простая, как может показаться. К примеру, общее число расположения ферзей на доске 8 на 8 равняется 4 426 165 368. Разумеется, человек не будет решать эту задачу за счет простого перебора, но в любом случае при возрастании доски сложность увеличивается во много раз, и тут нам на помощь приходит компьютер.
Анализ проблемы
Разберем нашу проблему на составляющие.
Первое что приходит на ум при разборе любой шахматной проблемы это шахматная доска. Поскольку наша доска квадратная, она имеет только один параметр, который отвечает за высоту и ширину — назовем его размерность и обозначим n. Доска с размерностью n=8 имеет высоту и ширину в 8 клеток. Всего на данной доске 8×8=64 клетки:
Каждая клетка имеет координаты вида ряд:столбец. Она может быть пустой, или на ней может находится ферзь.
Ферзь атакует другого ферзя если они находятся на одном ряду, или на одной колонке, или на одной из диагоналей (слева-направо, справа-налево).
Решением является доска, которая удовлетворяет следующим условиям:
- Количество установленных на доске ферзей равно размерности доски.
- Ни один ферзь не атакует другого.
Алгоритм решения
Самое сложное при решении любой проблемы, а тем более незнакомой, это сделать первый шаг. Не пытайтесь объять незнакомую проблему разом, первый шаг должен быть максимально простым.
Мы начинаем с пустой доски. Представьте себе доску с минимальной размерностью. 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, которое мы приводили выше, то заметим, что там первая клетку свободна, следовательно менять позицию первого установленного ферзя имеет смысл.
Наша попытка не увенчалась успехом в виде решения задачи, но мы получили нечто большее — алгоритм. И, если с него скинуть частные детали, то его можно будет применить для решения задачи с любой размерностью доски. Давайте немного формализуем то, что мы описали выше. Для большей наглядности и простоты предположим, что размерность доски больше единицы:
- Начинаем с пустой доски.
- Ставим фигурку в первую свободную клетку:
- Если фигурка атакует другую, тогда переставляем ее на следующую свободную клетку:
- Если больше нет не попробованных клеток, тогда возвращаемся к предыдущей установленной фигурке и переставляем ее:
- Но если текущая фигурка является начальной, тогда предыдущей быть не может, следовательно задача не имеет решения.
- Если больше нет не попробованных клеток, тогда возвращаемся к предыдущей установленной фигурке и переставляем ее:
- Если количество фигурок равно размерности доски тогда данная доска является решением.
- Если количество фигурок меньше размерности доски тогда берем еще одну фигурку и возвращаемся к пункту 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.
Для каждой из этих функций нам важно две вещи: позиция первой фигурки и позиция второй фигурки. Если ряд нашей фигурки совпадает с рядом другой фигурки значит она ее атакует по горизонтали. Если столбец нашей фигурки совпадает со столбцом другой фигурки то она ее атакует по вертикали.
С диагональю немножечко посложнее. Посмотрим на пример:
(3−6)÷(3−6)=−1; |−1|=1
Если мы разницу ряда первой фигурки и второй фигурки разделим на разницу их колонок и получим 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, в рекурсивном стиле:
- Берем первую фигурку из маcсива позиций.
- Проверяем не атакует ли она позиции в оставшийся части массива используя функцию notAttackOthers.
- Рекурсивно вызываем эту же функцию, но с массивом уже без первого элемента.
- Возвращаем результаты рекурсивного вызова и вызова функции 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 элементов. Забавно, я это заметил уже только когда делал визуализацию.
Заключение
Как мы видим по тестам производительности наш алгоритм не самый быстрый в мире и не позволяет получить ответ по щелчку пальцев. Но что у него не отнять так это то, что он отлично показывает силу деревьев и рекурсии.
С помощью деревьев мы организовали простую и эффективную структуру для хранения наших данных, а рекурсия помогла нам удобно организовать их обработку. Что мне нравится в этой парочке так это то, как одно очень красиво ложится на другое. Как будто это одно и тоже, просто представленное с другого ракурса.
А о методах ускорения поиска по деревьям поговорим в следующих статьях.