Engineering Note

プログラミングなどの技術的なメモ

8クイーン問題(すべての解を求める) (Pythonによるアルゴリズムとデータ構造)

8queens

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonアルゴリズムとデータ構造について学習していきます。

今回は、前回で学んだ8クイーン(Eight Queens Puzzle)からすべての解を求める方法について学んでいきます。

 

 

8クイーン問題とは

8クイーン(Eight Queens Puzzle:エイト・クイーン)とは、チェス盤と駒のクイーンを使ったパズルのことを言います。

クイーンは、将棋でいう飛車と角を合わせた動きが可能で、以下のように移動することができます。

 

fig1. クイーンの動き

fig1. クイーンの動き

 

そして、どのように8つのクイーンを互いに利いていない場所に配置していくかを考えるのが、今回の8クイーン問題になります。

1848年にMax Bezzelが発表し、数学者のC.F.Gauss(有名なガウスです)などもこの問題に挑戦しましたが、数学的な解法は見つかっておらず、一つ一つ盤上の駒と駒の関係を確かめながら解いていくしかないようです。 

 

Pythonで8クイーンを作成

それでは、Pythonで8クイーン問題のすべての解を求めるスクリプトを作成します。

 

# 8queens_all.py
from copy import deepcopy

SUCCESS = 1
FAIL = 0

FREE = 1
NOT_FREE = 0
N = 8

class Queens:
    def __init__(self):
        self.pos = [-1 for _ in range(N)]
        self.col = [FREE for _ in range(N)]
        self.up = [FREE for _ in range(2*N-1)]
        self.down = [FREE for _ in range(2*N-1)]
        self.count = 0
        self.answer = {}

    def print_queens(self, pos):
        for i in range(N):
            for j in range(N):
                if pos[i] == j:
                    print("Q ", end="")
                else:
                    print(". ", end="")
            print()
        print("---------------")

    def put_queen(self, a):
        for b in range(N):
            if self.col[b] == FREE and self.up[a+b] == FREE and \
                self.down[a-b+(N-1)] == FREE:
                self.pos[a] = b
                self.col[b] = NOT_FREE
                self.up[a+b] = NOT_FREE
                self.down[a-b+(N-1)] = NOT_FREE

                if a + 1 >= N:
                    self.count += 1
                    pos = deepcopy(self.pos)
                    self.answer[self.count] = pos
                else:
                    self.put_queen(a+1)

                self.pos[a] = -1
                self.col[b] = FREE
                self.up[a+b] = FREE
                self.down[a-b+(N-1)] = FREE

    def run(self):
        self.put_queen(0)
        if self.count:
            print("Found {} solutions.".format(self.count))
        else:
            print("Sorry, but there is no solution.")

if __name__ == '__main__':
    q = Queens()
    q.run()
    for k in q.answer.keys():
        q.print_queens(q.answer[k])

 

動作確認 

それでは上記で作成したスクリプトを実行してみます。

 

 > python 8queens_all.py
 Found 92 solutions.
 Q . . . . . . .
 . . . . Q . . .
 . . . . . . . Q
 . . . . . Q . .
 . . Q . . . . .
 . . . . . . Q .
 . Q . . . . . .
 . . . Q . . . .
 ---------------
 Q . . . . . . .
 . . . . . Q . .
 . . . . . . . Q
 . . Q . . . . .
 . . . . . . Q .
 . . . Q . . . .
 . Q . . . . . .
 . . . . Q . . .
 ---------------
 
 ...
 
 ---------------
 . . . . . . . Q
 . . . Q . . . .
 Q . . . . . . .
 . . Q . . . . .
 . . . . . Q . .
 . Q . . . . . .
 . . . . . . Q .
 . . . . Q . . .
 ---------------

 

8クイーンでは12種類の基本解があり、そのうち11種類は8つの変形があり、残りの1種類は4つの変形があるため、合計で 8\times11+4=92 の解が存在します。

また、 n\times n のチェス盤に n 個のクイーンを配置するものをnクイーンと言います。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)