ALDS1_13_A: 8 Queens Problem (続き)

解説を読む

1行にひとつしか置けないとか、
次の行にクイーンを置くときはまだ置かれてない列にとか、
8クイーン問題固有の事情をガッツリ組み込んである感じだな
その方が速いんだろうな

おーなるほど
縦・横だけじゃなくて斜めも列とみて、この列は配置済みっていう状態を持たせるのか
それは思いつかなかった
これなら速くてメモリも取らないし
8x8の配列を使うとループして埋めていかなきゃいけないからな

どれどれ書いてみよう

・・・

from collections import namedtuple

State = namedtuple("State", "queen row col dpos dneg")

def put_queen(s, r, c):
    s.queen[r] = c
    s.row[r] = s.col[c] = s.dpos[r + c] = s.dneg[r - c + 8 - 1] = True

def unput_queen(s, r, c):
    s.queen[r] = None
    s.row[r] = s.col[c] = s.dpos[r + c] = s.dneg[r - c + 8 - 1] = False

def read_board(s):
    k = int(input())
    for _ in range(k):
        r, c = [int(x) for x in input().split()]
        put_queen(s, r, c)
    return s

def print_board(s):
    for r in range(8):
        for c in range(8):
            print("Q" if s.queen[r] == c else ".", end="")
        print()

def eight_queens(s):
    def rec(r):
        if r == 8:
            return True
        elif s.queen[r] is not None:
            return rec(r + 1)
        else:
            for c in range(8):
                if s.col[c] or s.dpos[r + c] or s.dneg[r - c + 8 - 1]:
                    continue
                put_queen(s, r, c)
                if rec(r + 1):
                    return True
                unput_queen(s, r, c)
            return False

    rec(0)
    return s

def main():
    s = State(
        [None] * 8,
        [False] * 8,
        [False] * 8,
        [False] * (2 * 8 - 1),
        [False] * (2 * 8 - 1),
    )
    print_board(eight_queens(read_board(s)))

main()

サンプルコードがちゃんと理解できなくて
タテヨコナナメの利きを覚えておくところと
1行に1個ずつ置いていくところ以外はだいたい書き直してしまった気分

return sって書いてるのは関数を入れ子に書きたかっただけで
返さなくても呼び出し元でsを参照すれば同じという
sを変更しちゃってるからね

00.03sで6052KB
少し速いみたいだ