Some thoughts:
- You don't need a list of all the diagonals, what you need is the two diagonals for each queen in the board
- 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))