Forever Functional #20 — «Решение головоломок с помощью рекурсии и JavaScript».

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

Некоторые основные понятия

Все головоломки, которые мы будем рассматривать, связаны с различными числами. Предположим, у нас есть набор из 3 элементов: A, B и C. Тогда мы имеем:

Перестановки — это все способы упорядочения элементов, а именно ABC, ACB, BAC, BCA, CAB и CBA.
Компоновки — это способы выбора элементов p (по порядку) из набора элементов n. С нашим набором и p=2 у нас есть AB, AC, BA, BC, CA и CB. Если бы вместо этого у нас было p=1, ответ был бы просто A, B и C, а для p=3 ответ был бы шестью перестановками, которые мы видели выше. .
Комбинации — это способы выбора p элементов из n, но без учета порядка. В том же примере, что и с аранжировками, для p=2 комбинациями будут AB (или BA, это одно и то же), AC (или CA) и BC (или CB), а для p=1 ответом будут три отдельных значения, а для p=3 у нас будет одно ABC.

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

Перестановки

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

const allPermutations = (arr) => {
  if (arr.length === 0) {
    return [[]];
  } else {
    const answer = [];
    for (let i = 0; i < arr.length; i++) {
      const rest = allPermutations(arr.slice(0, i).concat(arr.slice(i + 1)));
      rest.forEach((p) => answer.push([arr[i], ...p]));
    }
    return answer;
  }
};

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

Выберите элемент в качестве первого элемента перестановки.
Сгенерируйте все перестановки других элементов.
Получите ответ, добавив выбранный элемент в начало всех произведенных перестановок.

В массиве answer есть все перестановки, каждая из которых представляет собой отдельный массив, а в массиве arr есть элементы для перестановки. Мы циклически выбираем элемент ( arr[i] ) всеми возможными способами и (рекурсивно) устанавливаем переменную rest как все перестановки оставшихся элементов. Наконец, мы используем цикл forEach, чтобы добавить выбранный элемент ко всем сгенерированным перестановкам.

Давайте решим пару головоломок с помощью этой логики.

Магические квадраты

Магические квадраты представляют собой сетки nx n со всеми числами от 1 до n ², так что числа в каждой строке, каждом столбце и Две главные диагонали в сумме дают одно и то же число. На изображении ниже показан магический квадрат 4x4.

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

allPermutations([1, 2, 3, 4, 5, 6, 7, 8, 9]).forEach((p) => {
  const sum = p[0] + p[1] + p[2];
  if (
    p[3] + p[4] + p[5] === sum &&
    p[6] + p[7] + p[8] === sum &&
    p[0] + p[3] + p[6] === sum &&
    p[1] + p[4] + p[7] === sum &&
    p[2] + p[5] + p[8] === sum &&
    p[0] + p[4] + p[8] === sum &&
    p[2] + p[4] + p[6] === sum
  ) {
    console.log("SOLUTION...");
    console.log("   ", p[0], p[1], p[2]);
    console.log("   ", p[3], p[4], p[5]);
    console.log("   ", p[6], p[7], p[8]);
  }
});

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

SOLUTION...
    2 7 6
    9 5 1
    4 3 8
SOLUTION...
    2 9 4
    7 5 3
    6 1 8
SOLUTION...
    4 3 8
    9 5 1
    2 7 6
SOLUTION...
    4 9 2
    3 5 7
    8 1 6
SOLUTION...
    6 1 8
    7 5 3
    2 9 4
SOLUTION...
    6 7 2
    1 5 9
    8 3 4
SOLUTION...
    8 1 6
    3 5 7
    4 9 2
SOLUTION...
    8 3 4
    1 5 9
    6 7 2

Суммы пар

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

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

// Each number is the sum of the two below: A+B=F, B+C=G, etc.
//   F G H I      5 6 7 8
//  A B C D E    0 1 2 3 4

allPermutations([1, 2, 3, 4, 5, 6, 7, 8, 9]).forEach((p) => {
  if (
    p[0] + p[1] === p[5] &&
    p[1] + p[2] === p[6] &&
    p[2] + p[3] === p[7] &&
    p[3] + p[4] === p[8]
  ) {
    console.log(JSON.stringify(p));
  }
});

Элементы в нижней строке находятся в позициях от 0 до 4 перестановок; элементы наверху находятся в позициях с 5 по 8. После создания всех перестановок мы проверяем, являются ли верхние элементы суммой нижних элементов, как описано. Выполнение этого приводит к следующим результатам:

[1,3,6,2,5,4,9,8,7]
[1,4,3,6,2,5,7,9,8]
[2,6,3,4,1,8,9,7,5]
[5,2,6,3,1,7,8,9,4]
[5,4,2,1,7,9,6,3,8]
[7,1,2,4,5,8,3,6,9]

Первая строка, например, говорит, что нижний ряд состоит из 1, 3, 6, 2 и 5, а верхний ряд состоит из 4, 9, 8 и 7. Просто!

Повтор сеанса для разработчиков

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

Удачной отладки! Попробуйте использовать OpenReplay сегодня.

Распоряжения

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

const allArrangements = (arr, size) => {
  if (arr.length === 0 || size === 0) {
    return [[]];
  } else {
    const answer = [];

    for (let i = 0; i < arr.length; i++) {
      const rest = allArrangements(
        arr.slice(0, i).concat(arr.slice(i + 1)),
        size - 1
      );
      rest.forEach((p) => answer.push([arr[i], ...p]));
    }

    return answer;
  }
};

Как это работает? Это так, как описано выше. Для генерации аранжировок заданного размера всеми возможными способами делаем следующее:

Выберите элемент в качестве первого элемента перестановки.
Сгенерируйте все расположения размера-1 других элементов.
Произведите ответ, добавив выбранный элемент в начало всех созданных аранжировок.

Мы используем массивы answer и arr, как и в нашем коде генерации перестановок.

Давайте применим эту логику к криптоарифметике!

Криптоарифметические головоломки

В криптоарифметических головоломках вы должны присваивать (различные) значения буквам, так что достигается некоторый результат. Давайте решим классическую головоломку столетней давности: ОТПРАВИТЬ+БОЛЬШЕ=ДЕНЬГИ. Если вы сделаете это задание правильно, вы получите правильную сумму. Обычное ограничение состоит в том, что никакие числа не должны начинаться с начального нуля.

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

allArrangements([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 8).forEach((p) => {
  if (p[0] > 0 && p[4] > 0) {
    const SEND = p[0] * 1000 + p[1] * 100 + p[2] * 10 + p[3];
    const MORE = p[4] * 1000 + p[5] * 100 + p[6] * 10 + p[1];
    const MONEY = p[4] * 10000 + p[5] * 1000 + p[2] * 100 + p[1] * 10 + p[7];

    if (SEND + MORE === MONEY) {
      console.log(SEND, MORE, MONEY);
    }
  }
});

Мы генерируем все возможные аранжировки, и мы:

проверьте, чтобы ни одно число не начиналось с 0
рассчитать значения ОТПРАВИТЬ, БОЛЬШЕ и ДЕНЬГИ
проверьте, равно ли ОТПРАВИТЬ+БОЛЬШЕ ДЕНЬГАМ, что означает, что у нас есть решение.

Запуск кода дает единственное решение: 9567+1085=10652.

Существует множество головоломок; вы можете попробовать свои силы в CROSS+ROADS=DANGER, BASE+BALL=GAMES, TEN+TEN+FORTY=SIXTY или ИНТЕРНЕТ-СЕТЬ=МОНИТОР.

Комбинации

Учитывая массив с элементами n, как мы можем выбрать p? Очевидно, что с пустым массивом или с p равным нулю ничего не поделаешь. В противном случае у вас есть две возможности:

включить в вывод первый элемент (arr[0]) и найти все способы выбрать p-1 из других элементов n-1, или
игнорировать первый элемент и найти все способы выбрать p элементов из остальных n-1. Конечно, это будет работать, только если n не меньше, чем p.

Мы можем реализовать это простым способом.

const allCombinations = (arr, size) => {
  if (arr.length === 0 || size === 0) {
    return [[]];
  } else {
    const answer = [];

    const rest = allCombinations(arr.slice(1), size - 1);
    rest.forEach((p) => answer.push([arr[0], ...p]));

    if (arr.length > size) {
      const rest2 = allCombinations(arr.slice(1), size);
      rest2.forEach((p) => answer.push(p));
    }

    return answer;
  }
};

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

Какуро

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

Например, на диаграмме выше (взято из Википедии) первое горизонтальное «слово» имеет две разные цифры, которые в сумме дают 16; второе горизонтальное «слово» состоит из трех цифр, что в сумме дает 24 и т. д.

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

const kakuro = (sum, terms) =>
  allCombinations([1, 2, 3, 4, 5, 6, 7, 8, 9], terms).filter(
    (p) => p.reduce((x, y) => x + y, 0) === sum
  );

Давайте сделаем несколько примеров.

console.log(kakuro(17, 2));
// Output:
// [ [ 8, 9 ] ]

console.log(kakuro(8, 3));
// Output:
// [ [ 1, 2, 5 ], [ 1, 3, 4 ] ]

console.log(kakuro(29, 6));
// Output:
// [
//   [ 1, 2, 3, 6, 8, 9 ],
//   [ 1, 2, 4, 5, 8, 9 ],
//   [ 1, 2, 4, 6, 7, 9 ],
//   [ 1, 2, 5, 6, 7, 8 ],
//   [ 1, 3, 4, 5, 7, 9 ],
//   [ 1, 3, 4, 6, 7, 8 ],
//   [ 2, 3, 4, 5, 6, 9 ],
//   [ 2, 3, 4, 5, 7, 8 ]
// ]

Итак, есть один способ сложения 17 с 2 цифрами (8+9), два способа сложения 8 с 3 цифрами (1+2+5, 1+3+4) и 8 способов сложения 29 с 6 слагаемыми. . Оно работает!

Некоторые предостережения…

Мы видели, как применять рекурсивные алгоритмы для решения нескольких головоломок, но будьте осторожны, потому что «экспоненциальный рост» может вас укусить! Я не хотел углубляться в математику, но позвольте мне объяснить. Если у вас есть n элементов, их будет n! возможные перестановки; это n факториал, который равен n умножить на n-1 умножить на n-2 … умножить на 2 умножить на 1 Итак, для головоломки с 10 элементами будет 10! = 3 628 800 перестановок для изучения.

Если бы у вас была головоломка, включающая, скажем, 15 шаров для игры в бильярд, вам потребовалось бы проанализировать 15! = 1 307 674 368 000 перестановок; если вычисление завершится успешно, это займет довольно много времени! Таким образом, даже если наша логика полностью верна, для некоторых видов (размеров) головоломок более подходящим может быть другой тип алгоритма; имейте в виду!

Краткое содержание

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

СОВЕТ ОТ РЕДАКТОРА: В нескольких статьях серии FOREVER FUNCTIONAL использовалась рекурсия: отметьте, например, Работа с функциями… но частично! и Many Flavors Of Currying, чтобы увидеть больше применений этого метода разработки алгоритма.

Первоначально опубликовано на https://blog.openreplay.com.