![見出し画像](https://assets.st-note.com/production/uploads/images/94259042/rectangle_large_type_2_576165afe36639ef2ef48c9842d37a45.png?width=800)
関数「under_attack」解説
先の記事『8-Queens Problem』における関数「under_attack」について解説を追記します。
記事『8-Queens Problem』についてはこちら。
関数「under_attack」
まず、関数「under_attack」を再掲します。
def under_attack(col, queens):
left = right = col
for r, c in reversed(queens):
left, right = left - 1, right + 1
if c in (left, col, right):
return True
return False
solve(4)
前記事に記載した solve(4) で使用したパターンを考えます。
既に、
solution = [(1, 1), (2, 5), (3, 8)]
にクイーンを配置しています。
![](https://assets.st-note.com/img/1672180505843-j5IfDNvOcz.png)
(4, 7)
まず、 (4, 7) に置くことができるかどうか考えてみます。
下図の★印のマスです。
![](https://assets.st-note.com/img/1672180582223-yehAIBUGVh.png)
このとき、関数「under_attack」は次のように呼び出されます。
under_attack(7, [(1, 1), (2, 5), (3, 8)])
初めに、
left = right = col = 7
でスタートします。
ループは
for r, c in reversed(queens):
ですから、「queens」を逆順に処理します。
「queens」は、
queens = [(1, 1), (2, 5), (3, 8)]
です。
「reversed」がなければ
(1, 1)→(2, 5)→(3, 8)
の左から右の順序で処理されますが、
「reversed」があると
(1, 1)←(2, 5)←(3, 8)
右から左の順序で処理されます。
left, right = left - 1, right + 1
で、
left を1つ左に
right を1つ右に
ずらします。
すなわち、下図の「L」「C」「R」が、それぞれ、left、col、rightに対応し、この3つのマスにクイーンがあるかどうかをチェックするわけです。
![](https://assets.st-note.com/img/1672180696233-2kXiXmfIyF.png)
このケースの場合、「R」のマスにクイーンがいるため、次の条件にヒットします。
if c in (left, col, right):
この条件文は
「c が、 left か col か right のどれかと一致したら真」
という意味になります。
(4, 3)
では、(4, 3) にクイーンは配置できるでしょうか。
下図の★印のマスです。
![](https://assets.st-note.com/img/1672180801659-FOxfOBLJYV.png)
まず、ループの最初の LCR はここになります。
LCR のどこにもクイーンはいません。
![](https://assets.st-note.com/img/1672180848865-rFBYZqDNT0.png)
ですので、次のループに進みます。
このとき、left、right は更に左右に1つずつずれるので、次のようになります。
![](https://assets.st-note.com/img/1672180913099-LLkH4GNvij.png)
ここには「R」のマスにクイーンがいるため、★印のマスには置けません。
(4, 4)
では、(4, 4) は?
![](https://assets.st-note.com/img/1672181002114-hHHmovHitL.png)
最初のループ。
LCR のどこにもクイーンはいません。
![](https://assets.st-note.com/img/1672181054227-Anm21p0L7w.png)
次のループ。
ここにもクイーンはいません。
![](https://assets.st-note.com/img/1672181102082-IB44WBa5mE.png)
そして最後のループ。
「L」のマスにクイーンがいます。
やはり★印のマスには置けません。
![](https://assets.st-note.com/img/1672181146194-gleHP8U2uJ.png)
(4, 6)
ちなみに (4, 6) であれば、3回のループの LCR のどこにもクイーンはいません。ですから (4, 6) には新たにクイーンを置けることになります。
![](https://assets.st-note.com/img/1672183040941-OnmgPlzQri.png)
この記事が気に入ったらサポートをしてみませんか?