# Solving the N-queens puzzle the Racket or Scheme way

My final version is a direct translation from Python. Thanks to build-in support for generator, its speed is almost the same as Python. As I quite like using generator and list comprehension in Python, I am not sure I get the right way in Racket.

Moreover, I've only found explicit support for generator in Racket these days, other scheme languages like MIT scheme and chez scheme seem not. So maybe there are some better way or more "schemeic" way to solve this problem and I am very curious about it.

This is my racket code, if needed:

#lang racket
(require racket/generator)

(define (safe? x y sln)
(if (null? sln)
#t
(let ((px (caar sln)) (py (cadar sln)))
(if (or (= y py) (= (- py y) (- px x)) (= (- py y) (- x px)))
#f
(safe? x y (cdr sln))))))

; input-> n, output-> a generator that yields
;            every possible list of n queens' coordinates
(define (nqueen n)
(let recur ((x (- n 1)))
(generator ()
(if (= x -1)
(yield '())
(for* ([sln (in-producer (recur (- x 1)) (void))]
[y   (range n)])
(and (safe? x y sln)
(yield (cons (list x y) sln)))))
(void))))

(for ([e (in-producer (nqueen 8) (void))])
(displayln e))

• Check this out rosettacode.org/wiki/N-queens_problem#Racket – ಠ_ಠ Aug 13 '14 at 19:52
• If the code is working but you want suggestions on how to make it more idiomatic, then it might be a better idea to post this question in the Code Review site. – Óscar López Aug 13 '14 at 20:22
• Notice that the lazy version on rosettacode could be shorter using racket primitives rather than implementing streams SICP style. – Sylwester Aug 14 '14 at 0:15
• @Sylwester Yes, but as xiang mentioned in the question, "I've only found explicit support for generator in Racket these days, other scheme languages like MIT scheme and chez scheme seem not. So maybe there are some better way or more "schemeic" way to solve this problem and I am very curious about it." That suggests that things that don't use Racket primitives are probably preferred in this case. – Joshua Taylor Aug 14 '14 at 2:34
• I test the Racket cases in rosettacode page when N=18. Mine can generate first solution in 3 seconds while others seem to take a long time (I don't know, because they never work out even after I am back from a shower). I also found that when N is large, my racket generator version is obviously faster than the python equivalent version, I got to say: Racket rocks! – xiang Aug 14 '14 at 3:00

Not sure if this is "the Racket way" but this one is faster, using Racket's sets and for loops:

(define (queens n)    ; n-queens, see http://en.wikipedia.org/wiki/Eight_queens_puzzle

(define res null)   ; accumulator for results

(define (s lst diags1 diags2 row columns)
(if (= row n)
(set! res (cons lst res))        ; got a result, remember it
(for ((col (in-set columns)))    ; for every column left
(define diag1 (+ col row))     ; compute diagonal 1
(define diag2 (- col row))     ;     and diagonal 2
(unless (or (set-member? diags1 diag1) (set-member? diags2 diag2)) ; if diagonals not already taken
(s (cons (cons row col) lst)

• I inlined the diag procedure, which makes the code look even shorter. You're right, there's nothing special, and the code could easily be ported to standard Scheme (with set support, such as SRFI-1). – user39182 Aug 15 '14 at 8:05