UVa 10094 - Place the Guards

Accepted date: 2016-10-17
Run Time: 0.000
Ranking (as of 2016-10-17): 9 out of 422
Language: C++

For more information, see Wikipedia's article Eight queens puzzle.

/*
  UVa 10094 - Place the Guards

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10094_Place_the_Guards.cpp
*/

#include <cstdio>
#ifdef DEBUG
#include <cassert>
#include <cstdlib>
#endif

const int n_max = 1000;
int rows[n_max + 1]; // rows[i] is the row number for i-th column

#ifdef DEBUG
bool validate_rows(int n)
{
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i != j) {
        if (rows[i] == rows[j] || abs(i - j) == abs(rows[i] - rows[j]))
          return false;
      }
  return true;
}
#endif

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    if (n < 4)
      puts("Impossible");
    else {
      int m = n;
      if (m & 1) { // odd
        rows[m] = m;
        m--;
      }
      int i, j, k;
      if ((m - 2) % 6)
        for (i = 1, j = m / 2; i <= j; i++) {
          k = 2 * i;
          rows[i] = k, rows[j + i] = k - 1;
        }
      else
        for (i = 1, j = m / 2; i <= j; i++) {
          k = (2 * i + j - 3) % m;
          rows[i] = 1 + k, rows[m + 1 - i] = m - k;
        }
#ifdef DEBUG
      assert(validate_rows(n));
#endif
      for (int i = 1; i <= n; i++)
        printf("%d%c", rows[i], ((i < n) ? ' ' : '\n'));
    }
  }
  return 0;
}