C - パズルのお手伝い (8 queens, 8クイーン問題)

Quiz

https://atcoder.jp/contests/arc001/tasks/arc001_3

AC Code

https://atcoder.jp/contests/arc001/submissions/6028256

解法

  • 最初の3つが条件を満たして置かれているなら、まだ空いているX座標、Y座標は共に5つ候補がある
  • それらをnext_permutationで全探索してQueenを配置
  • 配置した盤面が条件を満たすかチェック
    • 満たせばそこで終了
    • 満たすものがなければNo Answer

一般的なポイント

  • 配置の状態数が少ないので全探索すればいい

私のコードのポイント

  • 空いているX座標、Y座標をそれぞれ1回ずつしか使わないことにより、縦横の条件は最初から満たされているので、斜めのチェックだけすればいい