Getting Stuck On the Algorithm for q bishops on an n*n chessboard

Question

I'm using C++, but my question is more about algorithms than implementation.

The problem is the following:

Write a program that inputs two integers n and k, where n>=k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessboard.

My basic idea is to represent each bishop as a struct with an X value and a Y value. Then I place the bishops on the board to get a configuration.

I have written a method called moveToNextPlace that allows me to move a bishop into the next available spot. I return a string to help with debugging.

struct bishop {
int y=0;
int x=0;
string moveToNextPlace (int n){
    if (y<n-1) {y++; return "move to next y value";}
    else if (x<n-1) {x++; return "move to next x value";}
    else {reset(); return "reset";};
}
void setValuesLike (bishop b){
    y=b.y;
    x=b.x;
}
void reset (){
    y=0;
    x=0;
}
bool clashesWith (bishop b){
    if (b.x==x && b.y==y){
        return true;
    }
    if ( b.y-y == b.x-x ) return true; //if their slope is 1
    return false;

}
};

I then set the board to an initial configuration by calling findSolutions with my desired settings.

int findSolutions (int k, int n){ //k bishops on n*n board
bishop *b = new bishop [k];
for (int i=0; i<k; i++){
    findAspot (b, n, i);
}
}

bool check (int num, bishop b[]){
for (int i=0 ; i<num; i++){
    if (b[i].clashesWith (b[num])) return false;
}
return true;
}

void findAspot (bishop b[], int n, int num){ //n=boardsize
while (1){
    if (check(num, b)){return;}
    if (b[num].moveToNextPlace(n) == "reset") break;
}
b[num-1].moveToNextPlace(n);
findAspot (b, n, num-1);
b[num].setValuesLike ( b[num-1] );
findAspot (b, n, num);

}

I then want to keep backtracking until I have a total number of solutions, but I get stuck on how to find the next solution.

I thought I could write a findNextSolution that keeps getting called at the end of the findSolutions function until it reaches a cycle. But I don't know what algorithm to use to find the next solution.

Answer 1

You're off to a good start with your idea of storing the bishop positions in an array. This is a compact representation of a board state.

You'll have to correct your method of checking whether one bishop clashes with another. Bear in mind that two clashing bishops may be separated by a vertical distance dy and a horizontal distance dx such that dx == -dy. Therefore, you will want to compare the absolute values: the bishops clash if abs(dx) == abs(dy).

Now on to the general problem of counting the number of board states in which k bishops are arranged without clashing. You'll want to define a function that returns an integer value. Let's say that this function looks like

count(currentBishops, numRemaining)

where currentBishops is a feasible placement of bishops and numRemaining is the number of bishops you haven't placed yet.

Then the solution to the problem is

count([], k)

where [] means that no bishops have been placed yet.

The count function can be implemented according to the following pseudocode.

count(currentBishops, numRemaining):
  if numRemaining == 0:
    return 1
  sum = 0
  for each possible board position (x, y):
    if (x, y) does not clash with any bishop in currentBishops:
      let nextBishops be currentBishops augmented with (x, y)
      sum += count(nextBishops, numRemaining-1)
  return sum

In order to avoid an exponential explosion of recursive calls, you'll want to cache the result of each subproblem. This technique is called memoization, and you can implement it as follows.

let memo be a map from (currentBishops, numRemaining) to an integer value

count(currentBishops, numRemaining):
  if numRemaining == 0:
    return 1
  if memo contains (currentBishops, numRemaining):
    return memo[(currentBishops, numRemaining)]
  sum = 0 
  for each possible board position (x, y):
    if (x, y) does not clash with any bishop in currentBishops:
      let nextBishops be currentBishops augmented with (x, y)
      sum += count(nextBishops, numRemaining-1)
  memo[(currentBishops, numRemaining)] = sum
  return sum

The mapping of currentBishops should be one that doesn't care about the order in which you have placed the bishops. You can accomplish this by sorting the bishop positions or making a bitmap of the board when you compute the key for memo.