# 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, 2014 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. Aug 13, 2014 at 20:22
• Notice that the lazy version on rosettacode could be shorter using racket primitives rather than implementing streams SICP style. Aug 14, 2014 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. Aug 14, 2014 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, 2014 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)
(set-remove columns col))))))

(s null (set) (set) 0 (apply set (range n))) ; initial call
res)

(time (for-each displayln (queens 8)))

• Actually your algorithm is far better than mine despite the fact that your grammar has nothing special. Maybe I should be more curious about algorithms rather than language features. Thanks. Aug 15, 2014 at 4:42
• 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, 2014 at 8:05
• FWIW, I wrote the Python 3 equivalent: github.com/uselpa/n-queens-puzzle/blob/master/n-queens.py
– user39182
Aug 16, 2014 at 14:36