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
And, to make my algorithm work
Given this, I thought the best idea would be to
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.
I would suggest the following algorithm:
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).
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).
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.
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.
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.