Checkerboard Moves and Bipartite Graphs

I was wondering the other day, if you were on a checkerboard, what would be your smallest move?

If you could move to any color, you would have 8 choices; the squares in your neighborhood.

This is not just your neighborhood, but also your max amount of possible single moves.

Now what if you could only move to black squares? You lose half of your possible moves.

Moving Beyond the Neighborhood

This move restriction becomes interesting outside of the neighborhood. Previously, without color restriction, movement from one square to any other of the same color (by choice, not restriction) would result in a straight path.

If we can only move to black squares, this path looks different:

This forces us into a Taxicab geometry; we are on a plane where the shortest distance between two points is no longer a straight line (euclidean distance) but an “L”.

Shortest (Permitted) Moves

Under color restrictions, the amount of your shortest possible moves within your neighborhood has been reduced by half. However, the amount of shortest possible moves to nearest permitted squares (black squares) remains the same, but half of these moves leave the original neighborhood.

Shortest Paths

Your shortest path is then also affected. Without color restriction, your shortest path is a straight line and you travel 1 square to reach the nearest other square.

With color restriction, you no longer have a single shortest path, but 2, and they are no longer straight lines, but “L”‘s, and you must travel an extra square to reach your destination no matter which path you choose.

This can be represented with a bipartite (2-color) graph:

Your shortest path will contain either 1 or 2 nodes to get to the next (nearest) node of a like color. There will also be either one path or two.

You could make a larger graph, which looks like a grid, but really isn’t…

It would have some interesting circuits:

And travel would be interesting, as well…