matrix - 获取矩阵中的对角线

Question

使用 Racket，并避免任何有状态函数(以感叹号结尾的函数)，我试图获取列表列表中的所有“对角线条”，或者向量(如果更容易的话)。

这是解决“N-Queens”国际象棋问题的一部分，但我不想看到关于如何解决整个问题的剧透。相关性在于，我试图确定是否有任何皇后可以对角攻击任何其他皇后。我想我可以像水平和垂直攻击那样做到这一点——将每一行或每一列变成自己的列表，然后查看该列表中是否存在多个皇后。

但是，创建对角线条的代码变得非常丑陋且复杂!必须有一个好的、简洁的方法来解决这个问题。

示例:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

我想由此形成以下列表:

'(1 6 11 16) '(2 5) '(2 7 12) '(3 6 9) '(3 8) '(4 7 10 13) '(5 10 15)
'(9 14) '(8 11 14) '(12 15)

我注意到这些列表具有 a 形式，其中附加元素要么比前一个元素多 (+ n 1) ，要么是 (- n 1) 比前一个元素更多，但边界检查其他问题使我的代码过于复杂，并且不太可能解决合理的解决方案。 (在本例中，n 是一维的长度。)

我的处理方式是错误的吗？有没有更简单的方法来检查对角线是否受到另一皇后的威胁？或者这是正确的想法，但我缺少一些方便的功能，使这一切比我想象的要简单得多？

Answer 1

一些想法:

1. 您不需要所有对角线的列表，您需要的是棋盘中每个皇后的两条对角线
2. 如果您真的非常想要所有对角线，那么最好更改数据结构。虽然我确信这个问题可以使用列表来解决，但我宁愿切换到向量，这样我就可以有效地使用索引

当然，无论如何，您可以通过 list-ref 编写一个引用列表上索引的解决方案，但它不会高效/优雅。或者，您可以使用 list->vector 将列表转换为向量，使用 vector-ref 编写基于索引的解决方案，然后使用 vector- 返回到列表>列表

例如，您可以尝试以下解决方案(改编自此 post )。它接收一个向量向量作为输入(如果您想使用列表列表作为输入，只需将 vector-ref 替换为 list-ref，效率会较低不过)，并返回带有对角线的列表的列表。元素以不同的顺序添加，但值是正确的(读者练习:格式化输出，使其与问题中的示例匹配)。请注意我如何使用 iterations and comprehensions对于循环，这是惯用的 Racket，适合这种严重依赖索引的问题:

; Returns a list of lists with all the diagonals in a square matrix
; omitting the diagonals that have a single element
; m: the matrix represented as a vector of vectors
; n: the number of rows (or columns, because it's square)
(define (diagonals m n)
  ; join two results
  (append
  ; first: the leading diagonals
   (for/list ([slice (in-range 1 (- (* 2 n) 2))])
     (let ((z (if (< slice n) 0 (add1 (- slice n)))))
       (for/list ([j (in-range z (add1 (- slice z)))])
         (vector-ref (vector-ref m (sub1 (- n j))) (- slice j)))))
  ; second: the antidiagonals
   (for/list ([slice (in-range 1 (- (* 2 n) 2))])
     (let ((z (if (< slice n) 0 (add1 (- slice n)))))
       (for/list ([j (in-range z (add1 (- slice z)))])
         (vector-ref (vector-ref m j) (- slice j)))))))

您可以按如下方式测试，它可以按预期工作:

(define matrix '#(#(1 2 3 4) #(5 6 7 8) #(9 10 11 12) #(13 14 15 16)))
(diagonals matrix 4)

=> '((14 9)
     (15 10 5)
     (16 11 6 1)
     (12 7 2)
     (8 3)
     (2 5)
     (3 6 9)
     (4 7 10 13)
     (8 11 14)
     (12 15))