今回はチェスのコマを使ったパズルゲームである
8クイーン問題を解いてみました。

解説動画はこちら



8クイーンをご存じない方のために説明すると
クイーンはチェスのコマで
縦横斜め全てのマスに行く事ができます



このコマを8つ用いて
8x8マスの中にうまく
お互いのクイーンが利かないように
配置出来るかどうかというのが
8クイーンというものになります。

8x8マスなので結構大変ですね


さて解き方を考えてみましょう

愚直に一個一個置いてみて
縦横斜めに置けているかを判定してみれば
行けますかね！！！

for文を用いて全通り試せば行けますね

コードはこんな感じになりました。

sol_num ,count = 0 , 0

def check(i, j, k, l, m, n, o, p):
    return(i!=j) and (i!=k) and (i!=l) and (i!=m) and (i!=n) and (i!=o) and (i!=p) and (j!=k) and (j!=l) and (j!=m) and (j!=n) and (j!=o) and (j!=p) and (k!=l) and (k!=m) and (k!=n) and (k!=o) and (k!=p) and (l!=m) and (l!=n) and (l!=o) and (l!=p) and (m!=n) and (m!=o) and (m!=p) and (n!=o) and (n!=p) and (o!=p) and (abs(i-j)!=1) and (abs(j-k)!=1) and (abs(k-l)!=1) and (abs(l-m)!=1) and (abs(m-n)!=1) and (abs(n-o)!=1) and (abs(o-p)!=1) and (abs(i-k)!=2) and (abs(j-l)!=2) and (abs(k-m)!=2) and (abs(l-n)!=2) and (abs(m-o)!=2) and (abs(n-p)!=2) and (abs(i-l)!=3) and (abs(j-m)!=3) and (abs(k-n)!=3) and (abs(l-o)!=3) and (abs(m-p)!=3) and (abs(i-m)!=4) and (abs(j-n)!=4) and (abs(k-o)!=4) and (abs(l-p)!=4) and (abs(i-n)!=5) and (abs(j-o)!=5) and (abs(k-p)!=5) and (abs(i-o)!=6) and (abs(j-p)!=6) and (abs(i-p)!=7)

def print_sol(i, j, k, l, m, n, o, p):
    li = [i, j, k, l, m, n, o, p]
    for num in li:
        for a in range(8):
            if a ==num:
                print('Q' , end='\t')
            else:
                print('.' , end='\t')
        print()
    print('\n')

for i in range(8):
    for j in range(8):
        for k in range(8):
            for l in range(8):
                for m in range(8):
                    for n in range(8):
                        for o in range(8):
                            for p in range(8):
                                count+=1
                                if check(i, j, k, l, m, n, o, p):
                                    #print_sol(i, j, k, l, m, n, o, p)
                                    sol_num+=1
print(sol_num , count)

92 16777216

一応答えは出て8x8マスだと
92通り有るようです。


でも8回もfor文を使ったり
判定のところがめちゃくちゃ長かったり
結構酷いプログラムですねえwww

16777216回も判定を行っています
凄い数計算しちゃってますね

もう少し効率の良いものに
直していきましょう

まずfor文は8個も使わなくても
行列の組み合わせを考えれば
効率よく行けますね！！！

Pythonにはitertoolsというライブラリがあり
順列を生成することのできる
permutations というものがあるので
これを使うと8個もfor文を書かなくて済みます

from itertools import permutations

N=8
print(len([combo for combo in permutations(range(N))]))
for combo in permutations(range(N)):
    print(combo)
    break

40320
(0, 1, 2, 3, 4, 5, 6, 7)

順列だと4万通り程度で済むので
だいぶ効率よさそうです

次に判定のところは
2つのクイーン同士の
利きを判定するものにしてみます

# (x1, y1) と (x2, y2) の位置にいるクイーンが互いの効き筋にいるかを判定
def threat(x1, y1, x2, y2):
    return (x1 == x2) or (y1 == y2) or (abs(x1-x2) == abs(y1-y2))

縦横はそれぞれの場所が一緒ならすぐ判定できますね
斜めは縦横が同じ長さなら正方形になるので
その位置の対角線上かどうかが分かります

そういったことで縦横斜めの利きがあるかが
判定できました。

これを使って効率よく書くとこうなりました。

from itertools import permutations

def threat(x1, y1, x2, y2):
    return (x1 == x2) or (y1 == y2) or (abs(x1-x2) == abs(y1-y2))

N,count=8,0
for combo in permutations(range(N)):
    board1 = [(i,c) for i,c in enumerate(combo)]
    board2 = [board1[i+1:] for i,d in enumerate(board1) if i<N-1]
    tmp = 0
    for i,(y1,x1) in enumerate(board1):
        if i==N-1:
            break
        flg=True
        for y2,x2 in board2[i]:
            if y1==y2 and x1==x2:
                continue
            if threat(x1,y1,x2,y2):
                flg=False
        if flg:
            tmp+=1
    if tmp==N-1:
        count+=1
        #for z in board1:
        #    print(' _ ' * z[1] + ' Q ' + ' _ ' * (8-z[1]-1))
        #    print('')
        #break
print(count)

92

一応答えは出ましたね。
だいぶ早く終わるようになりました。

最後にもっと短くて
効率の良いものを見つけました。
それはこちらです。

from itertools import permutations

N,count = 8,0
for combo in permutations(range(N)):
    s1 = set(combo[i]+i for i in range(N))
    s2 = set(combo[i]-i for i in range(N))
    if N==len(s1)==len(s2):
        #print("\n".join(' _ ' * c + ' Q ' + ' _ ' * (N-c-1) for c in combo) + "\n\n")
        count+=1
        #break
print(count)

92

これだと10行程度で終わりますね
自分が見た中でこれが一番
短いかなーと思います。

一応答えは
プリントの部分のコメントアウトすると
こんな感じで出力することもできます。



8クイーンは
色々な人の解法が有って
たくさんコードがありますが

長いよりは短くて分かりやすいのが
いいですよね

もっともっと短く出来る可能性が
有って面白い問題です

誰か1行とかで出来ないかなwww

今回はここまでです
それでは

タグ ：

#Python

#プログラミング

#8クイーン

#チェス

#パズル