Inspiration Problem that was posed here. It can be restated as "Within a n x n chessboard, what is the maximum number of rooks that can be placed on the board, where each rook has a path off the board?" Similar statements can be constructed for the knight, bishop, and queen.
This solution was developed in Answer Set Programming, using the generate, define, and test methodology.
Here, we use the choice rule:
{rook(X, Y, D) : occupied(D)} = 1 :- X=1..x, Y=1..y.
To generate all possible grids. Similar choice rules exist for the other pieces.
We define the atom freePath/2 in a recursive manner in order to generate which spaces are part of an unbroken sequence of empty spaces to the boundary based on the type of piece being packed.
We prune branches by removing any grids where a piece cannot reach a free path.
Assume clingo is the alias to the local clingo instance. Run in your command line:
clingo rooks-game.lp -c x=3 -c y=3
Where x and y are the dimensions of the grid and the name of the file refers to which piece is being packed.
Given a n x n grid, the maximum has been found for the first few integers:
| Integer | Rooks | Knights | Bishops | Queens |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 4 | 4 | 4 |
| 3 | 8 | 9 | 8 | 8 |
| 4 | 13 | 16 | 12 | 14 |
| 5 | 21 | 24 | 19 | 22 |
| 6 | 28 | 34 | 28 | 31 |
| 7 | 37 | 44 | 37 | 42 |
| 8 | 50 | 58 | 48 | 54 |
| 9 | 73 | 57 | ||
| 10 | 91 | 72 | ||
| 11 | 87 |
Rooks: A335445 Knights: A337722 Bishops: A337746 Queens (To Be Confirmed): A054347
- Look for symmetry breaking features or structures to exploit to reduce search space
- Run on more computational power to generate more entries
- Confirm equivalency or non-equivalency of Queens sequence with A054347