縦横 n マスのボードに n 個のクイーンをおきます。ただし互いに相手の効き筋にいてはいけません。クイーンは、縦、横、斜めに動く事ができます。さてクイーンをどのように配置したらよいでしょうか、というのが問題です。
まずは解が得られたとして、その配置を表示する関数 print_board を書いてみましょう。たとえば、行と列の 2 要素のタプルを要素にもつタプルとして解が表されるとき:
((1, 0), (3, 1), (0, 2), (2, 3))
これを次のように表示するとします。
+---------+ | . Q . . | | . . . Q | | Q . . . | | . . Q . | +---------+
def print_board(size, board):
def border():
return '+' + '-' * (size*2+1) + '+'
def line(x):
return '| ' + '. ' * x + 'Q ' + '. ' * (size-x-1) + '|'
print border()
for x,y in board:
print line(x)
print border()>>> print_board(4, ((1, 0), (3, 1), (0, 2), (2, 3))) +---------+ | . Q . . | | . . . Q | | Q . . . | | . . Q . | +---------+
文字列同士の足し算は文字列の連結になります。
>>> 'foo' + 'bar' 'foobar' >>> 'a' + 'b' + 'c' 'abc'
演算子 * を使えば、その文字列を繰り返し連結します。
>>> 'foo' * 3 # 'foo' + 'foo' + 'foo' と同じ 'foofoofoo' >>> ' ' * 5 ' '
タプルはリストにとてもよく似ています。リストは「[」と「]」で囲まれますが、タプルは「(」と「)」で囲まれたものです。リストと同じように各要素には添え字でアクセスできます。
>>> (1, 2, 3)[0] 1 >>> (1, 2, 3)[1] 2 >>> (1, 2, 3)[-1] 3
しかしタプルでは、各要素を上書きすることは出来ません。
>>> lst = [1, 2, 3] >>> lst[1] = 10 # リストは書き換え可能 >>> lst [1, 10, 3] >>> tup = (1, 2, 3) >>> tup[1] = 10 # タプルでは書き換えできない TypeError: object doesn't support item assignment
また、タプルの括弧は文法上曖昧にならなければ省略できます。
>>> 1, 2, 3 (1, 2, 3) >>> x = 1, 2, 3 x[1] 2
リストがあるのに何故にタプルが存在するのか『はじめての Python』では次のように書かれています：
リストとタプルがあるのは、おそらく歴史的なことも理由の一部である。しかし、タプルの更新不能性によって、なにがしかの保全性が得られるからというのが、最良の解なのではないだろうか。タプルであれば、プログラムのどこか他の場所から参照を通して更新される事はないと確信できる。リストの場合はそのような保証はない。いくつかの組み込み演算はリストではなく、タプルを要求する。
リファレンスマニュアルには:
ターゲットが丸括弧や角括弧で囲われたターゲットリストの場合: オブジェクトはターゲットリスト中のターゲット数と同じ数の要素からなる配列でなければならず、その各要素は左から右へと対応するターゲットに代入されます。
と書かれています。ターゲットとは代入文の左辺と考えてください。= の左辺がリストやタプルの場合には、右辺のそれも同じ要素数を持たなければならないという意味です。
>>> a, b = 1, 2, 3 ValueError: unpack tuple of wrong size >>> [a, b] = [1, 2, 3] ValueError: unpack list of wrong size >>> [a, b, c] = 1, 2 ValueError: unpack tuple of wrong size >>> a, b, c = 1, 2, 3, 4 ValueError: unpack tuple of wrong size >>> [a, b] = 1, 2 >>> print a, b 1 2 >>> a, b = 4, 5 >>> print a, b 4 5 >>> (a, b) = [8, 9] >>> print a, b 8 9
for 文での、各要素の値が格納される変数にも同様な代入が行われています。
>>> for x,y in [[1, 2], [3, 4]]:
print x, y
1 2
3 4
>>> for x,y in [(1, 2), (3, 4)]:
print x, y
1 2
3 4
>>> for x,y in [[1,2,3]]:
print x, y
ValueError: unpack list of wrong size
クイーンの問題に戻ります。次に、クイーンの置く場所を決めなくてはなりません。そのためにまず 2 つのクイーンが互いの効き筋にいるかどうかを調べる必要が出てきますので、これを調べる関数 threat を作成します。
# (x, y) と (a, b) の位置にいるクイーンが互いの効き筋にいるか def threat(x, y, a, b) return x == a or y == b or abs(x-a) == abs(y-b)
関数 abs は引数の絶対値を返します。
>> abs(10) 10 >> abs(-10) 10
クイーンの斜めの位置に対しては、2 つのクイーンを四角形の対角だとみなして、その縦と横の長さを比較しています。もし縦と横の長さが同じなら、それは正方形ということになり、すなわちこれらのクイーンが斜めの効き筋にいるということになります。
この threat 関数を用いて、これまでに置いたクイーンに対して、位置 x, y にクイーンを置いても安全かどうかを調べる conflict 関数を作成します。
def conflict(x, y, board):
for a,b in board:
if threat(x, y, a, b):
return True
return Falseあとはボードのサイズに合わせてクイーンの置ける場所を探していきます。
def queen(size):
def rec(x, y, board):
if x < size:
if not conflict(x, y, board):
bd = board + ((x,y),)
if y+1 == size:
print_board(size, bd)
else:
rec(0, y+1, bd)
rec(x+1, y, board)
rec(0, 0, ())>>> queen(4) +---------+ | . Q . . | | . . . Q | | Q . . . | | . . Q . | +---------+ +---------+ | . . Q . | | Q . . . | | . . . Q | | . Q . . | +---------+
not は真偽値を反転させます。つまり真(True)は偽(False)になり、偽は真になります。
>> not True False >> not False True >> not 1 == 1 False
1 つの要素からなるタプルは次のようにして作ります。
>>> 1, (1,)
一つの要素からなるタプルを他のタプルに連結させるには、次のように書きます。
>>> (1, 2, 3) + (4,) (1, 2, 3, 4)
これを次のようには書けません。
>>> (1, 2, 3) + 4, TypeError: can only concatenate tuple (not "int") to tuple
チェス盤はサイズが 8 です。関数 queen に 8 を渡すと、92 個の解が出力されます。
>>> queen(8) +-----------------+ | Q . . . . . . . | | . . . . Q . . . | | . . . . . . . Q | | . . . . . Q . . | | . . Q . . . . . | | . . . . . . Q . | | . Q . . . . . . | | . . . Q . . . . | +-----------------+ …(以下略)
queen 関数では、クイーンの置く場所を端から端まで順番にクイーンを置けるかどうかを調べています。
def queen(size):
def rec(x, y, board):
if x < size:
if not conflict(x, y, board):
bd = board + ((x,y),)
if y+1 == size:
print_board(size, bd)
else:
rec(0, y+1, bd)
rec(x+1, y, board)
rec(0, 0, ())
しかし例えば、もし (0, 1) の位置にクイーンを置いたとしたら、それ以降にクイーンが x が 0 になる位置に置かれる事はありません。ですから、この時点で x が 0 であるような位置に対して、クイーンが置けるかどうかを調べる事には意味がありません。
そのため、一度置いたクイーンの x の値を保持しておいて、それ以外の x に対してのみ「クイーンを置けるかどうか」を調べるように関数を書き直してみます。
def queen2(size):
def rec(y, board, rst):
for x in rst:
if not conflict2(x, y, board):
bd = board + ((x,y),)
if y+1 == size:
print_board(size, bd)
else:
rec(y+1, bd, filter(lambda a: a!=x, rst))
rec(0, (), range(size))rst はその時点で調べるべき x のリストです。さらに、conflict 関数も書き直します。
def conflict2(x, y, board):
def threat2(a, b):
return abs(x-a) == abs(y-b)
for a,b in board:
if threat2(a, b):
return True
return Falseボードに置いたクイーンとの効き筋判定で、縦方向と横方向についてはもはや調べる必要はありません(実は先ほどの queen 関数でも横方向は調べる必要はないです。しかしながら 2 つのクイーンが互いの効き筋にいるかどうかを調べるということで threat は作成しています)。
また threat2 は conflict2 からしか呼ばれないので、conflict2 の中で threat2 を定義することにします。
再帰的に呼び出していたものを一部 for 文にしたりなど変更があるので、単純に queen と queen2 を比較することは出来ないのですが、参考の為にプロファイルをとってみます。プロファイラについては PerformanceTips を参考にしました。
> python queen.py
80160 function calls (62476 primitive calls) in 1.965 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 1.674 1.674 <string>:1(?)
0 0.000 0.000 profile:0(profiler)
1 0.291 0.291 1.965 1.965 profile:0(queen(8))
46752 0.459 0.000 0.459 0.000 queen.py:14(threat)
15720 0.655 0.000 1.115 0.000 queen.py:17(conflict)
1 0.000 0.000 1.674 1.674 queen.py:23(queen)
17685/1 0.560 0.000 1.674 1.674 queen.py:24(rec)
34308 function calls (32344 primitive calls) in 0.797 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.797 0.797 <string>:1(?)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 0.797 0.797 profile:0(queen2(8))
5508 0.300 0.000 0.496 0.000 queen.py:38(conflict2)
19368 0.196 0.000 0.196 0.000 queen.py:39(threat2)
1 0.000 0.000 0.797 0.797 queen.py:47(queen2)
1965/1 0.241 0.000 0.797 0.797 queen.py:48(rec)
7464 0.060 0.000 0.060 0.000 queen.py:56(<lambda>)参考文献: