Recursively get all combinations of tiles

Question

Recursively get all combinations of tiles

For a game, I need to calculate all possible combinations of a set of a grid in a 5x5-grid and do some calculations on these.

Some combinations of tiles will match a certain algorithm, which is not important for this part of the code, and if it matches, the player will get some points.

To check if the game is over, a very expensive recursive function needs to run which will check all possible combinations. If it doesn't find one, the game is over.

To speed this up, I need to create a cache of all the possible combinations.

What I am asking for help about is how to create a nested list of all combinations, following the Rules for selection below.

This will be used to check if the game is over.

Rules for selection.

1. Tile needs to be adjacent to the previous tile, e.g. directly above, below, to the left or to the right.
2. Tile cannot be on the list of already selected tiles.
3. User must select at least two tiles, up to a maxium of the whole board.
4. If the user selects a different tile, the selection will be cleared, and the user can start over selecting a different tile.

Goal of selection

This is a numbers-based game, where the goal is to combine some tiles, that together will "add up" to the last selected tile.

I will not go into the details of the algorithm here, so I will use an example of a basic addition-algorithm.

For instance, let's say that the board is like the screenshot below. Here, the user could select tile 1, 2, and then 3, and since 1+2=3, the user would get some points. Another example would be selecting 3, 2, 7, 12, since 3 + 2 + 7 = 12

Checking for game over.

Now, I would like to add a function which checks if there are any possible moves left, and this would basically need to check every combination of tiles. Since this is very exhaustive, I was thinking of creating a nested list of possible combinations ahead of time, and then while the user is playing it would check those combinations.

Example grid:

A valid selection above would be 0, 1, 6, 7, but 0, 10(rule 1), 0, 5, 0(rule 2) is not valid.

What I've tried.

I've tried to create a recursive function, but keeping track of the current path while creating a nested path seems to be very difficult.

I've therefore extracted the relevant code of what I've tried. This is for a grid of 5x5.

EDIT: Code now returns a flat list of combinations, however it doesn't actually get them all.

A flat list would be huge, since it repeats the data quite often:

[
  [
    0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17, 
    22, 23, 18, 13, 8, 3, 4, 9, 14, 19, 24
  ],
  [
    0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17, 
    22, 23, 18, 13, 8, 3, 9, 4
  ],
  [
    0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17, 
    22, 23, 18, 13, 8, 3, 9, 4, 14, 19, 24
  ],
  [
    0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
    22, 23, 18, 13, 8, 14, 9, 4, 3 
  ], 
  [ 
    0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
    22, 23, 18, 13, 8, 14, 9, 19, 24
  ],
  ...(3473 more objects)
]

It would be a lot better if I could nest these into an object.

Current code

// A list of all neighbours. I've just inlined it here, since my actual functions for creating it are inside an object.
const neighboursArray = [[5, 1], [6, 2], [7, 1, 3], [8, 2, 4], [9, 3], [10, 6], [1, 11, 5, 7], [2, 12, 6, 8], [3, 13, 7, 9], [4, 14, 8], [5, 15, 11], [6, 16, 10, 12], [7, 17, 11, 13], [8, 18, 12, 14], [9, 19, 13], [10, 20, 16], [11, 21, 15, 17], [12, 22, 16, 18], [13, 23, 17, 19], [14, 24, 18], [15, 21], [16, 20, 22], [17, 21, 23], [18, 22, 24], [19, 23], [20]]

const nested = (position) => {
  const paths = []
  const getAllNeighbours = (pos, path) => {
    // console.log('checking', pos, path)
    // Lookup neighbours for this pos
    const neighbours = neighboursArray[pos]
      // Make sure neighbours are not in list of already selected path.
      .filter((tile) => path.indexOf(tile) < 0)
      if (neighbours.length === 0) {
        paths.push(path)
      }
      for (const neighbour of neighbours) {
        path = [...path, neighbour]
        getAllNeighbours(path[path.length -1 ], path)
      }
      }

  getAllNeighbours(position, [position])
  return [paths]
}

Example of output

I've created part of the tree-structure visually for position 0. As you can see, nodes can have 0-3 children (the first can have 4 children), up to 24 levels deep for a 5x5-grid. The deeper the level, it tends to have fewer children as there would be less possibilities available.

Answer 1

So my best attempt would be something like this :

1. Initialize a x per y array, let's call it map.
2. Let the player chose an authorized path following your neighbour rules.
3. Keep the choosen tiles in memory in another array, let's call this one path.
4. Once the path is valided, remove all the path tiles from map so you don't have to care about them anymore.
5. Clear path array.
6. Check if at least two tiles can be chose by running a simple loop on map array which breaks if a pair is found. This way you don't have to iterate through all possibilities, only one is enough for the game to go on.
7. If a pair exists, go back to step 2, if not, it's game over.

This induces the following behavior : The more tiles in map array, the more possible combinations exists, the quicker it is for the algorithm to find at least one possible combinations. The less tiles in map array, the less possible combinations exists, maybe even none ! But if less tiles exists, less imaginable combinations are possible.

I let you think about the mathematical function that can compute if two tiles are neighboured or not, i guess you already have it ;)

Hope it helps

Answer 2

I figured out a way to do this. There might be more effective ways, but it works. It now generates first an array of all possible combinations, and then creates a nested object from that.

From this I generated two files, to compare sizes. The array is now huge, at 80 MB (7.8 MB compressed), while the nested object is 8.4 MB (424 KB), a reduction of almost 90%.

// A list of all neighbours. I've just inlined it here, since my actual functions for creating it are inside an object.
const neighboursArray = [[5, 1], [6, 2], [7, 1, 3], [8, 2, 4], [9, 3], [10, 6], [1, 11, 5, 7], [2, 12, 6, 8], [3, 13, 7, 9], [4, 14, 8], [5, 15, 11], [6, 16, 10, 12], [7, 17, 11, 13], [8, 18, 12, 14], [9, 19, 13], [10, 20, 16], [11, 21, 15, 17], [12, 22, 16, 18], [13, 23, 17, 19], [14, 24, 18], [15, 21], [16, 20, 22], [17, 21, 23], [18, 22, 24], [19, 23], [20]]

const getCombinationsForPosition = (position) => {
  const getAllNeighbours = (pos, path) => {
    // Lookup neighbours for this pos
    const neighbours = neighboursArray[pos]
      // Make sure neighbours are not in list of already selected path.
      .filter((tile) => path.indexOf(tile) < 0)
      paths.push(path)
      for (const neighbour of neighbours) {
        const p = [...path, neighbour]
        getAllNeighbours(p[p.length -1 ], p)
      }
      }

  getAllNeighbours(position, [position])
}

function assign(obj, prop) {
    if (prop.length > 1) {
        var e = prop.shift();
        assign(obj[e] = Object.prototype.toString.call(obj[e]) === "[object Object]" ? obj[e] : {},
               prop);
    } else
        obj[prop[0]] = -1;
}

const length = neighboursArray.length
const paths = []
const nesty = {}

for (var i = 0; i < length; i++) {
  getCombinationsForPosition(i)
}
paths.map(path => assign(nesty, [...path]))

const sorted = paths.sort((a,b) => a.length - b.length)
while (sorted[0].length < 2) {
  sorted.shift()
}