# Maximum reachable checkers on a checkerboard

This is a problem inspired by a video game that I've been thinking about for a long while, and I haven't convinced myself that I can do any better than brute force + pruning techniques, which would still take way too long to solve.

Is there anything better? Any class of algorithm I should look into more?

## Problem description

• You are on a checkerboard. Let's say 8x8 for now, but interested in general solutions too.
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

• There is a "start square" on the board, somewhere along the edge.
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ S │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

• You may place checkers onto the board anywhere you like, with the following restrictions:
• You cannot place a checker on the start square.
• Each square may contain 0 or 1 checker; you can't place multiple in one square.
• All checkers must be "reachable" (described further in the next bullet).
• From the start square, you are able to traverse the board, using up/down/left/right movements to adjacent squares (diagonals are not considered adjacent).
• You cannot "traverse" into a square that is occupied by a checker.
• You must remain on the board.
• To "reach" a given checker, you must be able to traverse to a square adjacent to the square that checker is placed on.
• What is the maximum amount of checkers you can place on the board?

## Examples

• Valid (but not the maximum solution: this has 36, I've found 38 by hand for this start square configuration):
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ ● │ ● │ ● │ ● │ ● │ ● │ ● │ ● │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ ● │ ● │ ● │ ● │ ● │ ● │ ● │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ ● │ ● │ ● │ ● │ ● │ ● │ ● │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │ ● │ ● │ ● │ ● │ ● │ ● │ ● │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │ ● │ ● │ ● │ ● │ ● │ ● │ ● │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ S │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

• Valid (but definitely not the maximum):
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ ● │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ ● │ S │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

• Invalid (corner checker is not "reachable"):
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ ● │ ● │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ ● │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ S │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘


## My current approach

My current approach is just brute force, unfortunately:

• Generate a 2d bool array (for an 8x8 checkerboard, I'd just use a 64-bit int)
• Flood-fill from the start square for "reachability"
• Check every checker and make sure it's "reachable"
• As you find valid boards with n checkers, you can stop trying any board that has <= n checkers.

Obviously, for an n by m board (with one start square), you'd have to check 2^(n*m-1) different combinations to be sure you found the maximum. Not great.

One realization I've had is that if a given checker configuration is invalid, adding more checkers to it won't magically make it valid. So, there's some opportunity to prune the problem space that way, but I'm not sure if there's an efficient way to implement it. Turning this into a recursive problem ("if you have a valid board, try adding one more checker to it in all available locations, and recurse for any of those boards that are valid") would end up either:

• trying certain configurations much more than once (depth-first), or
• turning the problem into a 2^(n*m-1) memory complexity problem to prevent that, I think? (breadth-first).