Coordinated motion of objects on a grid

Question

This is the problem:

I have 9 objects on a 3 $\times$ 3 grid. They move simultaneously to an adjacent node on the grid (an object in the center can move to any of the other nodes on the grid, an object on one of the corners can move in three possible directions, etc). Which branch(es) of mathematics should I be studying in order to prove that it's possible for all of the objects on the grid to move without colliding (overlapping) with another object on the grid and come up with an algorithm to dictate how the objects can move on the grid given the direction of a single object on the grid?

Note: I'm a junior software engineer trying to code functionality into a game, not a mathematician. I've started with game theory (because its the math of decision making) and graph theory (because my problem can be visually represented as a graph with 9 nodes and 20 edges). I understand the topics that I am asking about could be over my head (currently). Please be patient. Also, has this exact problem (or a very similar problem) been solved yet?

Answer 1

As mentioned, graph theory is going to be what you're after. As an example of how graph theoretic tools can help, consider the following example results (with verbose proofs as you said this is not a familiar topic) that one might use graph theory to demonstrate.

Proposition: There is no way of simultaneously moving all 9 objects if they may only move in cardinal directions (no diagonal moves).

Proof: Consider each square in your board a vertex; two vertices share an edge if and only if an object in one has an allowable move to the other (note this relation under the rules in is symmetric so this is well defined). The resulting graph resembles a $3$x$3$ grid.

Then a collection of simultaneous moves for all objects (one starting on each node) within the allowable moveset is equivalent to looking for a directed cycle that hits each node exactly once (a so-called Hamiltonian cycle).

Color the nodes on your graph like a chess board. Then any Hamiltonian cycle must take each black node to a white node (due to the limitations of objects only being able to move one square and only in cardinal directions) and vice versa. Thus any Hamiltonian cycle must connect an equal number of black and white nodes, and hence the total number of nodes must be even. But we have 9 vertices so this is impossible, so such a cycle does not exist.

Corollary: Under the movement rules in the initial question, in any allowable simultaneous movement of all $9$ pieces, at least one piece necessarily makes a diagonal move.

As for existence of such a simultaneous movement, it suffices to exhibit one: numbering from top-left to bottom-right in the order as one would read a book in:

$$1\to 2$$ $$2\to 3$$ $$3\to 6$$ $$6\to 5$$ $${\bf 5\to 9}$$ $$9\to8$$ $$8\to7$$ $$7\to 4$$ $$4\to 1$$ where the bolded move, $$5\to 9$$ is the requisite diagonal leap.