ALDS_13_A - 8 クイーン問題(精選17）未了

問題

チェス盤に互いに干渉しないように８つのクイーンを配置する問題です。

有名な問題のようです。

すでにいくつかクイーンが置かれている入力に対し，１通りだけ配置可能な組み合わせがあります。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A&lang=ja

考察

最初に入力のクイーンを配置し，干渉する場所をマークし，干渉しない場所にクイーンを置きながら新たに干渉する場所をマークし，最終的に８つのクイーンがおけるかを判定していくことを考えました。

全部のクイーンがおけない場合，配置可能な場所をDFSで探索していくようにすればよいと思いました。

もっとも，干渉する場所をマークするところからうまくいかず，今の実力では書ききれませんでした。

後日，改めて挑戦します。

仕掛けのコード

#include <bits/stdc++.h>
using namespace std;

int S[8][8];
int T[8][8];

int main(){
  int n=0;
  cin>>n;
  int r,c;

  for(int i=0;i<n;i++){
    cin>>r>>c;
    S[r][c]=1;
  }
  
  /*for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cout<<S[i][j];
    }
    cout<<endl;
  }
  cout<<endl;
  */
  
  
  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      if(S[i][j]==1){
        for(int k=0;k<8;k++){
          if(S[i][k]==0){
            S[i][k]=2;
          }
          if(S[k][j]==0){
            S[k][j]=2;
          }
        }
        for(int k=max(0,i+k-7);k<min(i+j,8);k++){
          if(S[k][i+j-k]==0){
            S[k][i+j-k]=2;
          }
        }
        if(i>=j){
          for(int k=i-j;k<8;k++){
            if(S[k][k-i+j]==0){
              S[k][k-i+j]=2;
            }
          }
        }
        if(j>i){
          for(int k=j-i;k<8;k++){
            if(S[k-j+i][k]==0){
              S[k-j+i][k]=2;
            }
          }
        }
      }
    }
  }

  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cout<<S[i][j];
    }
    cout<<endl;
  }
  cout<<endl;
  
  return 0;
}