Get Diagonals in a Matrix

Question

Using Racket, and avoiding any stateful functions (ones that end with an exclamation mark), I am trying to get all "diagonal strips" in a list of lists, or a vector if that is easier.

This is a part of solving the "N-Queens" Chess problem, but I'd rather not see spoilers on how to solve that problem in its entirety. The relevance is that I am trying to determine if any Queen can attack any other Queen diagonally. I figured I could do this the way I do it for horizontal and vertical attacks -- turn each row or column into its own list and see if more than one Queen exists in that list.

However, creating the diagonal strips is becoming very ugly and complicated code! There has got to be a nice, concise way to solve this problem.

Example:

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

I would like to form the following lists from this:

'(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)

I've noticed these lists have the a form where additional elements are either (+ n 1) more than the previous element, or they are (- n 1) more than the previous element, but boundary checking other issues are making my code far too complicated, and unlikely to resolve to a reasonable solution. (In this case, n is the length of one dimension.)

Am I going about this the wrong way? Is there an easier way to check if diagonals are threatened by another Queen? Or is this the correct idea, but I'm missing some handy functions that make this all a ton simpler than I'm thinking?

Answer 1

Some thoughts:

1. You don't need a list of all the diagonals, what you need is the two diagonals for each queen in the board
2. If you really, really want all the diagonals then it's better to change the data structure. Although I'm certain that this problem can be solved using lists, I'd rather switch to vectors so I can use indexes efficiently

Granted, anyway you can write a solution referencing indexes on a list via list-ref but it wouldn't be efficient/elegant. Or you could transform the lists into vectors with list->vector, write an index-based solution with vector-ref and then go back to lists with vector->list

For instance, you can try the following solution (adapted from this post). It receives a vector of vectors as input (if you want to use a list of lists as input simply replace vector-ref with list-ref, it'll be less efficient though), and returns a list of lists with the diagonals. The elements get added in a different order, but the values are correct (exercise for the reader: format the output so it matches the sample in the question). Notice how I'm using iterations and comprehensions for looping, this is idiomatic Racket and appropriate for this kind of problem that relies heavily on indexes:

; 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)))))))

You can test it as follows, it works as expected:

(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))