0
\$\begingroup\$

I am quite new to C++ programming, and would appreciate any comments.

How many combinations of N chess queens on a N×N board exist that there is no two queen attacking each other?

Input

8

Output

92

I solved the task by iterative approach using three additional arrays which are depicting the direction of attacks: vert contains all vertical attacks, udiag - up-down diagonal and ddiag - down-up diagonal attacks.

This scheme shows a state of variables on each iteration. White squares on the figure mean 0, and colored ones - 1. enter image description here I have chosen for the first iteration (1,0) position, because it gives one correct combination, but not (0,0).

#include <iostream>

int resolve(int col, int n, int vert[], int udiag[], int ddiag[]) {
  if (n == col)
    return 1;
  udiag++;
  ddiag--;
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (vert[i] + udiag[i] + ddiag[i] == 0) {
      vert[i] = 1;
      udiag[i] = 1;
      ddiag[i] = 1;
      //the figure is showing the state of variables here
      count += resolve(col + 1, n, vert, udiag, ddiag);
      vert[i] = 0;
      udiag[i] = 0;
      ddiag[i] = 0;
    }
  }
  udiag--;
  ddiag++;
  return count;
}

int main() {
  int n;
  std::cin >> n;
  int vert[n];
  int udiag[2*n];
  int ddiag[2*n];
  for (int i = 0; i < n; i++)
    vert[i] = 0;
  for (int i = 0; i < 2 * n; i++) {
    udiag[i] = 0;
    ddiag[i] = 0;
  }
  std::cout << resolve(0, n, vert, udiag, ddiag + n);
  return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.