競プロ初中級者100問

ALDS1 13A 8クイーン問題

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

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

この問題は全探索を用いて解くことができます。

方針

工夫して全探索

単純に全探索すると候補は64C8となります。各候補に対する判定でさらにループが回ることから、間に合わないでしょう。

縦横にクイーンが重なってはならないという制約を利用して候補を絞ります。

具体的には、二次元配列の各列各行に重複があってはならないということなので、1~8までの重複を許さない順列として表現できます。例えば以下のような表現は

1
(6, 0, 2, 7, 5, 3, 1, 4)
1
2
3
0行目には、6列目にクイーンが存在する。
1行目には、0列目にクイーンが存在する。
2行目には、2列目にクイーンが存在する。

というような意味となります。

これにより計算量はO(8!)となります。

判定

先ほどの絞り込みにより縦横を見る必要がないので、あとは斜めに二つ以上のクイーンがあるかどうかを判定すれば良いですが、これが重めです。

判定する処理を作り、盤面を反転させて使い回すように実装すると楽でしょう。

コード

Nが十分に小さいので全探索しても間に合います。その場合、計算量はO(N!N)です。

しかし、さらに計算量を減らす方法を考えます。各経路の距離の期待値について考えます。すると

各経路の距離の期待値 = 各町の間の距離の期待値 * (N-1)

となることが分かります。つまり、各町の間の距離を計算すればよく、これは計算量O(N^2)です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from itertools import permutations
K = int(input())
N = 8
RC = []
for k in range(K):
    r, c = map(int,input().split())
    RC.append((r,c))

def diag(board): # 斜めの判定
    for i in range(2*N-1):
        sm = 0
        for j in range(i+1):
            if (i-j>=8 or j>=8):
                continue
            sm += board[i-j][j]
        if sm > 1:
            return False
    return True

def judge(ls):
    board = [[0]*N for _ in range(N)]
    for r in range(N):
        c = ls[r]
        board[r][c] = 1
    for r, c in RC: # 指定された箇所にクイーンを置いているか判定
        if board[r][c] == 0:
            return False
    
    if not diag(board):
        return False
    
    if not diag(board[::-1]): # 反転
        return False
    return True

for ls in permutations(range(N)):
    if judge(ls):
        for c in ls:
            s = ['.'] * N
            s[c] = 'Q'
            print (''.join(s))
        exit()

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月10日