Nクイーン（アルゴリズム）配列を介しが数行

Question

http://jeffe.cs.illinois.edu/teaching/algorithms/notes/03-backtracking.pdf

enter image description here

を理解していない強調表示された画像の尋ね

Qを説明[I] = jはQ [I] = J + RI Q [i] = j-r + i

どのようにこれらのステートメントは、行の列または対角線で2つのクイーン攻撃をチェックするか？

Answer 1

これは、数年前に私が明らかなアルゴリズムを桁違いに打ち砕いたときよりも優れた解決策です。

基本的には、ボードを維持して、クイーンが移動できる3つのパスをチェックするのではなく（単にクイーンの背後を見る必要があります。 （row-1）* 3のセルをチェックする必要がある（まだいくつかのボードがありますが、最初に境界の対角線をテストするほうが安いかもしれません）、を1つ維持しています dimension彼らが脅していることに気づいた。これにより、各配置テストが3つの正方形に減少します。 （そして、加算のみを使用し、乗算は使用しません。これとは関係なく、時間を大幅に節約します。）

私はすべてのものを見て、1つの配列ではなく私はそれをしました（列の脅威、斜めの脅威、対角線の脅威、後者の配列は2倍の大きさです）。