Combinatorics Arrangement Problem

[Quinn Liu]

Hi everyone,

I hope your summer is going well. My name is Quinn and I am currently a junior CS and math major at VT. This summer I am doing some brain simulation research and I have come across a Combinatorics arrangement problem that I am stuck on. I was hoping someone here could shed some light with your expertise.

- Imagine you have an 8x8 empty chessboard.

- You have just 10 pawns that will be unique because they will be placed at a unique position on the chessboard.
QUESTION: How many different unique ways can I place those 10 pawns on the chessboard where each pawn is at least some variable D(straight line) distance away from any of the other pawns?
Additional notes:

- If you don't have the time to solve this problem could you please let me know what subfield of Combinatorics I can learn to solve this problem?

- Lastly, if the above problem is too difficult, how would you do this if instead of a chessboard that is 8x8, but have a very long board that is 64 x 1 in dimensions?

Thank you very much for your time,

Quinn Liu

Virginia Tech
walnutiq.com
quinnliu@vt.edu

 

[jedishrfu]

You might get some insight on how to solve it from the wiki article:

https://en.wikipedia.org/wiki/Eight_queens_puzzle

 

[Quinn Liu]

Not quite what I am looking for but thanks for the reply. My question allows 2 queens to be in the same row or column as long as they are a variable "D" distance away from any of the other queens.

 

[jedishrfu]

If you have a line of squares say 12 squares and 10 pawns that can be 1 square apart then

for pawn 0 you have 12 possible choices
for pawn 1 you have 11 possible choices
...

which means you have 12*11*10*9*8*7*6*5*4*3 or (12!/2!) choices but wait there's more...

Next you have to realize that the pawns are indistinguishable from one another and so so you have to factor that in too as you'll be over counting choices.

As an example, given the letters a,b,c,d,a you could make 5! words but the dcba'a is the same as dcbaa' since the a's are really indistinguishable.

Perhaps you can extend the ideas above to figure out your problem.

We're here to help but we can't solve problems for you only give you pointers as you show your work.

 

[JCVD]

I'm afraid the ideas in the previous post won't be too helpful in solving your problem for D>1 (for D=1 with p pawns and any board with n spaces the answer is n choose p), but what will do the trick is setting up a recurrence relation with initial conditions and either solving it in general or just writing a program to solve it using recursion.

Suppose you want to find f(D,p,n), where f(D,p,n) counts the ways to arrange p pawns on a 1 by n chessboard so that any two are at least distance D apart. Fix D; we shall see how to compute f(D,p,n) for any p and n.

Note that for initial conditions we have f(D,1,n)=n for all n and f(D,p,n)=0 if n<=D(p-1), so we may assume p>1 and n>D(p-1). Since either you have a pawn in the first square, in which case there are f(D,p-1,n-D) ways to place the p-1 remaining pawns on the n-D available squares, or you have no pawn in the first square, in which case there are f(D,p,n-1) ways to place all p pawns on the n-1 remaining squares, we have f(D,p,n)=f(D,p-1,n-D)+f(D,p,n-1).

 

[JCVD]

The link to the eight queens puzzle, however, is a good start for solving your problem on any board (go down to the "Exercise in algorithm design" section).

For instance, you can use a recursive algorithm to find all the ways to place p pawns at least distance D apart on a given board, by phrasing your problem inductively in terms of adding a single pawn at least distance D away to each pawn in any solution to the problem of placing p−1 pawns on the given board. The base case is the solution of placing 0 pawns on the board, which is the empty board.

If you don't consolidate identical board positions along the way, your algorithm will spit out p! copies of each valid board position of p pawns, one copy for each way of ordering the pawns to be added to the board.