ALDS1_13_A: 8 Queens Problem

8クイーン問題、問題は知ってたけど解くのは初めてだなあ
思考も実装も星三つ
けっこう難しい問題という位置づけなんだ
64マスに置いたり置かなかったり、そのまま書くとすごい計算量になる？
コードの長さはいつもより少し長くなりそうな予感

ヒントの絵はバックトラックっぽい
素直なバックトラックでも計算量は減ってんだっけ
早めにあきらめる分お得ってことか

データ構造はどんなのがいいだろう
クイーンの位置を覚えておくのがいいか
8x8の配列に状態を覚えておくのがいいか

位置をどう記憶するかっていうのもあるかな
第一感は縦0～7、横0～7で覚えるところだろうけど
順番に試していくことを考えると0から63まで書くのが楽だったりするかもしれない
どっちでやっても変換するだけだけど

クイーンの位置を縦横で覚えておく、で書いてみる
位置はタプルでもいいけどnamedtupleで書いてみよう

from collections import namedtuple

Pos = namedtuple("Pos", "r c")

まずは入出力
このへんそろってると動かしてみるときにわかりやすいので

def read_queens():
    qs = []
    k = int(input())
    for _ in range(k):
        r, c = [int(x) for x in input().split()]
        qs.append(Pos(r, c))
    return qs

def print_board(qs):
    for r in range(8):
        for c in range(8):
            print("Q" if (Pos(r, c) in qs) else ".", end="")
        print()

rとcが逆になってて提出したらなんでWAなんだと悩んだのは内緒だ

次
クイーンの位置で覚えることにしたから、当たり判定を作らないとな
こんな感じでいけてる？

def is_attacked(p, qs):
    return (
        (p.r in [q.r for q in qs])
        or (p.c in [q.c for q in qs])
        or (any([abs(p.r - q.r) == abs(p.c - q.c) for q in qs]))
    )

in使ってるとちょっとループしてるんだけど最大でも8回だしとりあえず無視

ところでreturnにおもしろいカッコがついてるのはBlackさんの流儀
Blackさんは縦に長くするのが好き
自分の好みとしては横も適度に伸ばして縦横バランスよく広がっているのがいいんだけど
スタイルのカスタマイズとかしてる余裕がないので自由度ほぼ0のBlackさんを使ってる

では本体
ごくシンプルに

盤面左上から開始
クイーンを8個置けたら成功 クイーンの配列を返す
盤面全部使ってもダメだったら失敗 Falseを返す
今の位置が攻撃されてたら次の位置を試す
攻撃されてなかったらクイーンを置いてみて続行
置いてみてダメだったら置くのをやめて次の位置を試す

def eight_queens(qs):
    def rec(p, qs):
        if len(qs) == 8:
            return qs
        elif over(p):
            return False
        elif is_attacked(p, qs):
            return rec(next_sq(p), qs)
        else:
            result = rec(Pos(p.r + 1, 0), qs + [p])
            return result if result else rec(next_sq(p), qs)

    return rec(Pos(0, 0), qs)

ひとつ置けたらもうその行には置けないから次の行までスキップする、くらいの工夫はした
あとは
qsに要素を足すときにはappendで直接変更するとバックトラックできないので
コピーができるように+を使ったとか

補助関数

    def next_sq(p):
        if p.c == 7:
            return Pos(p.r + 1, 0)
        else:
            return Pos(p.r, p.c + 1)

    def over(p):
        return p.r > 7

あとmainな
Pythonではグローバルな識別子は処理が遅いのでとにかく関数の中に入れろって
じっちゃんが言ってた
今回Posはグローバルに定義したけど（さすがに引数で渡す気はしないし

def main():
    qs = read_queens()
    print_board(eight_queens(qs))

main()

AC 00.04s 6056KB
余裕
バックトラックだけで十分に高速化されたってことだな

書いてて疑問だったんだけど、解けない形ってないのかな
解けない場合はこういう風に出力しろって書いてない
開始時ですでに当たってるとかでなければ大丈夫なのかな

あーこれか

入力に対する解はただ１つ存在する。

ちゃんと読んでなかった
読めよな
そういうとこやぞ