N queens and checking for diagonals

Question

I have an assignment where I have to solve the n queens problem. the placement of the queens HAS to be randomized which is why i have a shuffle function.

Our teacher wants us to prompt the user to enter n an and from that n an array of int[n] will initialize. Then I have to call my shuffle function that shuffles and checks the array until the queens in column indexes Q1 = q1,q2,qn... do not attack each other and then print the first solution.

For example, {0 2 1 3} would correspond to the 4 queens in positions (0,0) (row 0, column 0), (1,2) (row 1, column 2), (2, 1) (row 2, column 1), and (3, 3) (row 3, column 3). Note that in our representation, we do not use row indexes: the ithe queen is placed in the ithe row and its column index is qi. To check whether a sequence Qn solves the n-Queens problem you need to make sure that:

1. Two queens do not share a column, i.e. qi ≠ qj, for i ≠ j, and
2. Two queens do not share a diagonal, i.e. |qi - qj| - |i - j|, when i ≠ j

ex: n = 4;

int main(){

• prompts user //user puts 4 for n = int b [n]

-displays array before shuffle//0,1,2,3
-shuffle function(array,n) //shuffles each 
time a queen is under attack until checkB 
== 1(no queens under attack, so until array 
findsa solution.
-displays array after finding the first 
solution


}
void shuffle(){
//shuffles elements of array to create 
random permutations

}

int checkB(int [] b, int n){
do{
//checks if a queen attacks another in the 
same column or diagonally
}while(checkfunction == 0);
//checks if the shuffled array has any 

queens attacking eachother, if it doesnt, stops the loop

}

int displayB(int []b, int n){
//prints the solution b 

My issue if im not sure how to write the check method, i have an idea of how to check the columns but diagonally i am stumped as our teacher doesnt want us to convert the board into a matrix until we find the solution and then print it.ive written everything else but have come up short with thisfunction, heres my checkB function, any help as to how to check it diagonally atleast (column as well) would be appreciated! the b[] is the array of column indexes which gets printed.

int checkBoard(int b[], int n){
int result = 1; 
int delta R;
int deltaC;
int result =1; 
for(int c = 0; c<n; c++){
 for(int x = 0; x<n; x++){
    deltaR=abs(c - (c+1));
    deltaC=abs(b[x]-b[x+1]);
    if(deltaR==deltaC){
     result =0;
   }
   }
   }
return result;
}

The output is supposed to be the solution for n but, as you can see, something must be going wrong in my check function for it to print an invalid array. It's invalid because one of the queens is in the same diagonal!

Answer 1

Let's see some of the issues.

• If the function that shuffles the array is well written, it will change the order of elements in the array, without "loosing" any of them. That means that if the array is properly initialized with unique values there's no need to check if any of the queens shares a column.

• The checkBoard function doesn't return anything even if it should, because of its signature and how it's used in the code. It should also return as soon as it finds a queen under attack, to save computation time.

• Regarding the implementation of that function, I'd make some changes to the nested loops:

  • for every i less than n, starting from 0.
    • declare two variables L and R both equal to b[i].
    • for every j less than n, starting from i + 1 (we don't need to check the previous rows, the queens there already checked their diagonals).
      • increment R by one and decrement L by one (remember to use a signed type).
      • If L == b[j] or R == b[j] return false, these two queens are on the same diagonal.
  • return true, because no queen is under attack.

• Shuffling the whole array every time an attempt is unsuccessful, may not be a good idea performance-wise. Consider implementing some kind of backtracking strategy.