Forever Functional: Solving puzzles with recursion and JavaScript

by Federico Kereki

How do you solve Kakuro or Killer Sudoku puzzles? Or create Magic Squares? Or possibly solve Cryptarithmetic puzzles? We can do all that with JavaScript, some recursive techniques, and some extra code, as we'll see below.

Some basic concepts

All the puzzles we'll be considering have to do with distinct numbers. Suppose we have a set of 3 elements: A, B, and C. Then we have:

• Permutations - This is all the ways of ordering the elements, namely ABC, ACB, BAC, BCA, CAB, and CBA.
• Arrangements - These are the ways of picking p elements (in order) out of a set of n elements. With our set and p=2, we have AB, AC, BA, BC, CA, and CB. If we had p=1 instead, the answer would simply be A, B, and C, and for p=3, the answer would be the six permutations we saw above.
• Combinations - These are the ways of picking p elements out of n, but without considering the order. In the same example as with arrangements, for p=2 the combinations would be AB (or BA, it's the same), AC (or CA), and BC (or CB), while for p=1 the answer would be the three individual values, and for p=3 we'd have the single ABC.

Permutations, arrangements, and combinations are at the heart of many puzzles, so we will now see how to generate them using recursive techniques, and we'll apply the code to several different puzzles.

Permutations

How do we arrange n books on a shelf? We may pick any book and place it in the leftmost place. Then, out of the rest of the books, we may select any one of them and put it at the next available spot. We can repeat the procedure until all the books are placed. Of course, when there are no books, we are done. We can implement this recursively as follows.

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;
  }
};

Let's see how this works. The idea is as described above. To generate all permutations of a given set, we must do the following in all possible ways:

1. Pick an element as the first one of the permutation.
2. Generate all permutations of the other elements.
3. Produce the answer by adding the picked element at the beginning of all the produced permutations.

Array answer has all the permutations, each an array by itself, and array arr has the elements to be permutated. We loop to pick an element (arr[i]) in all possible ways, and we (recursively) set the variable rest to be all permutations of the remaining elements. Finally, we use a forEach loop to add the picked element to all the generated permutations.

Let's solve a couple of puzzles with this logic.

Magic Squares

Magic Squares are n*x*n grids, with all numbers from 1 to n², so that numbers in each row, each column, and the two main diagonals add up to the same number. The image below shows a 4x4 magic square.

Let's try to find all possible 3x3 squares now. The code below will do that.

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]);
  }
});

We generate all permutations of the numbers from 1 to 9 and then check if the eight sums (three rows, three columns, two diagonals) are equal. Running this produces eight solutions.

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

Sums of pairs

Let's do another puzzle. In the following figure, you must place digits 1 to 9, so every number in the top row is the sum of the two numbers below it.

We can do this with a similar logic: we generate all permutations of the numbers from 1 to 9, and we check if their arrangement is OK.

// 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));
  }
});

The elements at the bottom row are at positions 0 through 4 of the permutations; elements at the top are at positions 5 through 8. After generating all permutations, we check if the top elements are the sum of the bottom elements as described. Running this produces the following results:

[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]

The first row, for instance, says that the bottom row is formed by 1, 3, 6, 2, and 5, and the top row consists of 4, 9, 8, and 7. Simple!

Open Source Session Replay

OpenReplay is an open-source, session replay suite that lets you see what users do on your web app, helping you troubleshoot issues faster. OpenReplay is self-hosted for full control over your data.

Start enjoying your debugging experience - start using OpenReplay for free.

Arrangements

After what we wrote for permutations, the logic for arrangements is very similar - but we stop generating when the desired size has been achieved. To find arrangements of a given size, after we pick a first element, we find all arrangements of the rest of the elements, but of size-1 elements. We are done when we try to get arrangements of an empty array or of size 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;
  }
};

How does this work? It is as described above. To generate arrangements of a given size, we do the following in all possible ways:

1. Pick an element as the first one of the permutation.
2. Generate all arrangements of size-1 of the other elements.
3. Produce the answer by adding the picked element at the beginning of all the produced arrangements.

We use arrays answer and arr as in our permutation-generation code.

Let's apply this logic to doing some cryptarithmetic!

Cryptarithmetic puzzles

In cryptarithmetic puzzles, you have to assign (distinct) values to letters, so some result is achieved. Let's work out a classic puzzle from about a century ago: SEND+MORE=MONEY. If you do this assignment correctly, you'll get a valid sum. A usual restriction is that no numbers should start with a leading zero.

In this case we have 8 letters, so the solution is an arrangement of 8 out of the 10 possible digits. (The order in which we assign numbers to letters is important, so we are dealing with arrangements, not combinations as in the next section.)

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);
    }
  }
});

We generate all possible arrangements, and we:

1. check that no number starts with 0
2. calculate the values of SEND, MORE, and MONEY
3. check if SEND+MORE equals MONEY, which means we have a solution.

Running the code produces the only solution: 9567+1085=10652.

Numerous puzzles exist; you may want to try your hand at CROSS+ROADS=DANGER, BASE+BALL=GAMES, TEN+TEN+FORTY=SIXTY, or INTERNET-NETWORK=MONITOR.

Combinations

Given an array with n elements, how can we pick p? Obviously, with an empty array or with p equal to zero, there's nothing to be done. Otherwise, you have two possibilities:

• include the first element (arr[0]) in the output, and find all the ways to pick p-1 out of the other n-1 elements, or
• ignore the first element, and find all the ways to pick p elements out of the other n-1 ones. Of course, this will only work if n is not less than p.

We can implement this in a simple way.

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;
  }
};

We return an empty combination in the base cases (empty array, zero size). Otherwise, we first (recursively) find all combinations that include the first element, and next, if possible, we (also recursively) find all combinations without the first element.

Kakuro

When solving Kakuro puzzles, you must find sets of (distinct) numbers that add a specific total. (Killer Sudoku puzzles also have a similar mechanism.) In the former kind of puzzle (see below) you are given a "crossword" in which each "word" is made of different digits, and instead of clues, you are told the sum of those digits.

For example, in the diagram above (taken from Wikipedia) the first horizontal "word" has two different digits that add up to 16; the second horizontal "word" is three digits long, adding up to 24, etc.

We won't try to solve a complete puzzle, but let's just focus on finding all possibilities for a given total and number of terms, which will be a handy aid. The idea is: let's find all the picks of the nine digits from 1 to 9 of the right size, and check if the sum is correct.

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
  );

Let's do some examples.

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 ]
// ]

OK, so there's a single way of adding 17 with 2 digits (8+9), two ways of adding 8 with 3 digits (1+2+5, 1+3+4), and 8 ways of adding 29 with 6 terms. It works!

Some caveats...

We have seen how to apply recursive algorithms to solve several puzzles, but be careful because "exponential growth" could bite you! I didn't want to go into Maths, but let me explain. If you have n elements, there are n! possible permutations; that's n factorial, and is equal to n times n-1 times n-2 ... times 2 times 1. So, for a puzzle involving 10 elements, there will be 10! = 3,628,800 permutations to study.

If you had a puzzle involving, say, the 15 balls of a pool game, you'd require analyzing 15!= 1,307,674,368,000 permutations; if the computation succeeds, it will require quite a while! So, even if our logic is totally correct, for some kinds (sizes) of puzzles, another type of algorithm could be more proper; be warned!

Summary

In this article, we've seen how we can apply JavaScript and recursion to solve various puzzles, usually involving numbers. This doesn't cover all the possible puzzles that can be solved with code, obviously, but it provides a broad scope of tools to use, so we were able to see both actual problem solving and recursive algorithms design; a double win!

A TIP FROM THE EDITOR: Several articles in the FOREVER FUNCTIONAL series have used recursion: check for instance Working With Functions... But Partially! and Many Flavors Of Currying to see more applications of this algorithm design technique.