Submission #1755196

---

Source Code Expand

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def can_set(y, x, field):
    if y >= 8:
        return True

    prev = field[y][x]
    field[y][x] = "Q"

    ng = False
    for i in range(8):
        ng |= (i, x) != (y, x) and field[i][x] == "Q"
        ng |= (y, i) != (y, x) and field[y][i] == "Q"
        ng |= (y - i, x - i) != (y, x) and inside(y - i, x - i, 8, 8) and field[y - i][x - i] == "Q"
        ng |= (y + i, x + i) != (y, x) and inside(y + i, x + i, 8, 8) and field[y + i][x + i] == "Q"
        ng |= (y + i, x - i) != (y, x) and inside(y + i, x - i, 8, 8) and field[y + i][x - i] == "Q"
        ng |= (y - i, x + i) != (y, x) and inside(y - i, x + i, 8, 8) and field[y - i][x + i] == "Q"
    if ng:
        field[y][x] = prev
        return False

    for i in range(8):
        if can_set(y + 1, i, field):
            return True

    field[y][x] = prev
    return False


def main():
    field = []
    for _ in range(8):
        field.append(list(input()))

    for x in range(8):
        if can_set(0, x, field):
            for line in field:
                print(*line, sep="")
            return
    print("No Answer")


if __name__ == '__main__':
    main()

Submission Info

Judge Result