Submission #1607739

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 8;
bool row[N], col[N], dpos[2 * N - 1], dneg[2 * N - 1];
bool used[N][N];
bool ok = false;

void printBoard(void) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << (used[i][j] ? 'Q' : '.');
    }
    cout << endl;
  }
}


void dfs(int i) {
  if (i == N && !ok) {
    printBoard();
    ok = true;
    return;
  }

  if (row[i]) {
    dfs(i + 1);
  } else {
    for (int j = 0; j < N; j++) {
      if (col[j] || dpos[i + j] || dneg[N - 1 + i - j]) continue;
      row[i] = col[j] = dpos[i + j] = dneg[N - 1 + i - j] = true;
      used[i][j] = true;
      dfs(i + 1);
      used[i][j] = false;
      row[i] = col[j] = dpos[i + j] = dneg[N - 1 + i - j] = false;      
    }
  }
}

int main(void) {
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < N; j++) {
      if (s[j] == '.') continue;
      used[i][j] = row[i] = col[j] = dpos[i + j] = dneg[N - 1 + i - j] = true;
    }
  }

  dfs(0);

  if (!ok) cout << "No Answer\n";

  return 0;
}

Submission Info

Judge Result