General algorithm to solve a maze with n balls

Question

I got asked the other day about "Outlining a general algorithm for solving a maze with n balls, where the goal is to get all the balls to a given position in the maze (the maze has no exit)". The only rules are that the algorithm must be effective (better than randomly moving the balls) and that all the commands issued will affect all the balls, so that is one ball is moved north, so will all the others if they are not blocked.

To do this I made some assumptions, namely that

• The maze is standard/perfect
• The balls cannot block each other
• The balls can get to the position asked
• A command will let the balls roll until the hit a wall
• A command can only be N/S/E/W
• The maze is randomly constructed and the balls randomly distributed each time it is reset
• All of the maze can be observed at once by the maze-operator

And, to make my algorithm work

• The balls are not identical (e.g. the have a number or something on them)
• The maze-operator has a photographic memory

Given this, I thought the best idea would be to

1. Randomly (or in a smart way) move the balls until two balls get to the target position
2. Save the path from their starting position to their end position.
3. Identify those balls and where they came from, and for each of them, do 1.

The "break" in this recursive algorithm would be when all the balls have a way to reach the given target (O(log(n)) recursions I think?)

Does this work? Does anyone else have a better algorithm for doing this?

I had another idea involving moving all the balls to the same random position and then moving them all as one ball, but that seemed like a worse algorithm.

Another idea would be to generate a graph (graph theory that is) where all the stable points for a ball would be a node, and the move would be an edge, but I can't see how that doesn't need a lot of brute force to be done.

Inestimable

It seems to me that "the balls cannot collide" contradicts some of the other assumptions. – Carin

You are right, that's poor wording on my part. I meant to say that they cannot block each other (or are all ghost-balls that cannot collide). I'll edit that! – Inestimable

Answer 1

I would suggest the following algorithm:

1. Create a data structure for the maze where for each free cell (square) the following is known:

   a. the coordinates (row, column)
   b. the target cells for the 4 moves (north, east, south, west)
   c. the reverse of b: the cells from where marbles can come to this cell (if any).

2. Perform a BFS starting from the target cell, performing reverse moves with one imaginary marble, assigning to each visited cell, the least number of moves necessary from that cell to reach the target cell. Note that some cells might not get visited this way, meaning that if a marble would be placed there, there would be no way to get it to the target cell by performing legal moves. These cells will get an infinite distance attributed to them (initial value).

3. Create an evaluation function that will assign a cost to a certain configuration of marbles. The suggested evaluation function would sum up the squares of the distances of each of the cells occupied by at least one marble. By taking the square, higher distances will bring a relatively high cost, so that the algorithm will favour moves that improve the position of the marble that has the worst position. This function would not count double the cells that are occupied by more than one marble. That way, configurations where marbles share a cell are favoured.

4. From the starting position, generate the 4 possible moves with their evaluated cost. Sort them ascending by their cost, and in that order perform a DFS, repeating this step recursively. When the cost becomes zero, a solution is found, and during the immediate backtracking out of recursion, the "path" of moves is returned. When the cost is infinite, then the search is stopped, and the next move is tried, ...etc.

5. During the search keep a list of visited positions. When a position is visited again, the evaluation function will give it a value of infinity, so that the search will backtrack when this happens.

Here is a JavaScript implementation of the above algorithm:

"use strict";
function createMaze(mazeStr) {
    var maze, lines, cell, row, ch, id, r, c, n, m;
    
    maze = {
        nodesRowCol: [],
        nodes: [],
        target: null,
        marbles: []
    };
    id = 0;
    lines = mazeStr.split("\n");
    for (r = 0; r < lines.length; r++) {
        maze.nodesRowCol[r] = row = [];
        for (c = 0; c < lines[r].length; c++) {
            ch = lines[r].charAt(c);
            if (ch !== '#') {
                maze.nodes[id] = row[c] = cell = {
                    row: r,
                    col: c,
                    id: id++,
                    comeFrom: [],
                };
                // Keep track of target and marbles
                if (ch === '*') maze.target = cell;
                if (ch === '.') maze.marbles.push(cell);
            }
        }
    }
    // Add neighbours
    for (n = 0; n < maze.nodes.length; n++) {
        cell = maze.nodes[n];
        cell.neighbours = [
            maze.nodesRowCol[cell.row-1][cell.col], /* north */
            maze.nodesRowCol[cell.row][cell.col+1], /* east  */
            maze.nodesRowCol[cell.row+1][cell.col], /* south */
            maze.nodesRowCol[cell.row][cell.col-1]  /* west  */
        ];
    }
    // Add marble moves in two steps
    for (n = 0; n < maze.nodes.length; n++) {
        cell = maze.nodes[n];
        cell.moves = [ 
            cell.neighbours[0] ? cell.neighbours[0].moves[0] : cell, /* north */
            null,
            null,
            cell.neighbours[3] ? cell.neighbours[3].moves[3] : cell, /* west  */
        ];
    }
    for (n = maze.nodes.length - 1; n >= 0; n--) {
        cell = maze.nodes[n];
        cell.moves[1] = cell.neighbours[1] ? cell.neighbours[1].moves[1] : cell; /* west */
        cell.moves[2] = cell.neighbours[2] ? cell.neighbours[2].moves[2] : cell; /* south */
    }
    // add reverse-move ("marble can come from") data
    for (n = maze.nodes.length - 1; n >= 0; n--) {
        cell = maze.nodes[n];
        for (m = 0; m < 4; m++) {
            if (cell.moves[m] !== cell) cell.moves[m].comeFrom.push(cell);
        }
    }
    return maze;
}

function setDistances(maze) {
    var n, cell, distance, stack, newStack, i;
    // clear distance information
    for (n = 0; n < maze.nodes.length; n++) {
        maze.nodes[n].distance = Number.POSITIVE_INFINITY;
    }
    // set initial distance
    cell = maze.target;
    cell.distance = distance = 0;
    // BSF loop to set the distance for each cell that can be reached
    stack = cell.comeFrom.slice();
    while (stack.length) {
        distance++;
        newStack = [];
        for (i = 0; i < stack.length; i++) {
            cell = stack[i];
            if (distance < cell.distance) {
                cell.distance = distance;
                newStack = newStack.concat(cell.comeFrom);
            }
        }
        stack = newStack;
    }
}

function evaluatedPosition(position, visited) {
    // Assign heurstic cost to position
    var m, ids;
    
    position.cost = 0;
    ids = []; // keep track of marble positions
    for (m = 0; m < position.marbles.length; m++) {
        // If mulitple marbles are at same cell, only account for that cell once.
        // This will favour such positions: 
        if (ids[position.marbles[m].id] === undefined) { 
           // Make higher distances cost a lot, so that insentive
           // is to improve the position of the worst placed marble 
           position.cost += Math.pow(position.marbles[m].distance, 2);
           ids[position.marbles[m].id] = position.marbles[m].id;
        }
    }
    // Assign some unique string, identifying the marble configuration
    position.id = ids.join(','); 
    // If position was already visited before, give it the maximum cost
    if (visited[position.id]) position.cost = Number.POSITIVE_INFINITY;
    // Mark position as visited
    visited[position.id] = 1;
    return position;
}

function createMove(dir, marbles, visited) {
    var m, movedMarbles;
    
    movedMarbles = [];
    for (m = 0; m < marbles.length; m++) {
        movedMarbles[m] = marbles[m].moves[dir];
    }
    return evaluatedPosition({
        dir: dir,
        marbles: movedMarbles,
    }, visited);
}

function solve(maze) {
    var visited = {}; // nothing visited yet
    
    function recurse (position) {
        var ids, m, moves, i, path;
        if (position.cost == 0) return []; // marbles are all on target spot.
        if (!isFinite(position.cost)) return false; // no solution
        // get move list
        moves = [];
        for (i = 0; i < 4; i++) {
            moves[i] = createMove(i, position.marbles, visited);
        }
        // apply heuristic: sort the 4 moves by ascending cost
        moves.sort(function (a,b) { return a.cost - b.cost });
        for (i = 0; i < 4; i++) {
            //console.log('=== move === ' +  moves[i].dir);
            path = recurse(moves[i]);
            if (path !== false) return [moves[i].dir].concat(path);
        }
        return false; // no solution found
    }
    // Enrich initial position with cost, and start recursive search 
    return recurse(evaluatedPosition({
        marbles: maze.marbles
    }, visited));
}


// # = wall
// * = target
// . = marble

var mazeStr = `
###########
#   #   #*#
# # #.#  .#
# #.  #.# #
# # # ### #
#   #     #
###########
`.trim();

var maze = createMaze(mazeStr);
setDistances(maze);
console.log('#=wall, .=marble, *=target\n\n' + mazeStr);

var moves = solve(maze);
console.log('moves (0=north,1=east,2=south,3=west): ' + moves);

The found solution is not necessarily optimal. It performs an evaluation with depth 1. For better solutions, the algorithm could do an evaluation at greater depths.

Silvia

This answer kicks my answer's butt in so many ways. I get how this solved, and why it is better doing greater depth, but wouldn't that take up greater computing power, maybe exponentially-ish? – Inestimable

Of course, the depth should be limited, and not be arbitrarily big, as then the evaluation would to take too much time. Increase of depth with 1 will triple the number of positions to look at. But you could use some other heuristic to "prune" some branches in the evaluation search tree, when the evaluation of a position leads to a cost that is too high compared to others. You might accidentally prune a good branch, as optimal solutions might need to go over a "hill" (temporary high cost). – Silvia

I'm so sorry for the delay, I have been busy at work :/ The answer is really good and I understood (after quite a few youtube-clips on pruning) what you ment for increasing complexity. Thank you again for clearing this out! – Inestimable

Answer 2

The maze and allowed movements can be modelled as a deterministic finite automaton (DFA) on an alphabet of four symbols. Each cell in the maze is a DFA state, and cell x has a transition to cell y on symbol s whenever a ball at cell x would move to cell y when issued the command s.

The algorithm has three stages:

1. Construct a DFA consisting of only those states reachable by any ball in the maze, by some sequence of commands.
2. Find any synchronizing word for the DFA. A synchronizing word, or "reset word", is any sequence of symbols for which all initial states end at the same state. Note that we really only need a word which synchronizes all the initial states of the balls, not every state in the DFA.
3. Find a shortest sequence of moves from the reset word's end state to the target position in the maze. This can be done using any shortest-path algorithm, e.g. breadth-first search (BFS).

This needs some explanation.

Firstly, not every DFA has a reset word, but if the DFA constructed in step 1 has no reset word then, by definition, no sequence of commands can bring all balls to the same target cell. So this algorithm will solve every solvable instance of the problem.

Secondly, finding a minimum-length reset word is a hard problem which takes exponential time in the worst case. But the question says only that "the algorithm must be effective (better than randomly moving the balls)", so any reset word will do.

The simplest way to construct a reset word is probably using breadth-first search on the Cartesian product of the DFA with itself. For a DFA with n states, it takes O(n²) time to find a word which synchronizes two states; this must be repeated up to k - 1 times to synchronize the k initial states of the balls, giving an O(kn²) running time, and a reset word of length O(kn²).

---

Put in plainer language, the simplest form of this algorithm uses BFS to get two of the balls into the same place, then BFS again to get a third ball into the same place as those two, and so on, until all the balls are in the same place. Then it uses BFS to get them all to the target in unison. But the algorithm can be improved by plugging in a better reset-word-finding algorithm; generally, a reset word shorter than n² symbols should exist even in the worst case (this is believed but unproven), which is much better than kn².

Abisia