2
\$\begingroup\$

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))
\$\endgroup\$

migrated from stackoverflow.com Aug 14 '14 at 12:35

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ Check this out rosettacode.org/wiki/N-queens_problem#Racket \$\endgroup\$ – ಠ_ಠ Aug 13 '14 at 19:52
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Óscar López Aug 13 '14 at 20:22
  • 1
    \$\begingroup\$ Notice that the lazy version on rosettacode could be shorter using racket primitives rather than implementing streams SICP style. \$\endgroup\$ – Sylwester Aug 14 '14 at 0:15
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Joshua Taylor Aug 14 '14 at 2:34
  • \$\begingroup\$ 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! \$\endgroup\$ – xiang Aug 14 '14 at 3:00
3
\$\begingroup\$

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-add diags1 diag1) 
               (set-add diags2 diag2) 
               (add1 row) 
               (set-remove columns col))))))

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

(time (for-each displayln (queens 8)))
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – xiang Aug 15 '14 at 4:42
  • \$\begingroup\$ 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). \$\endgroup\$ – user39182 Aug 15 '14 at 8:05
  • \$\begingroup\$ FWIW, I wrote the Python 3 equivalent: github.com/uselpa/n-queens-puzzle/blob/master/n-queens.py \$\endgroup\$ – user39182 Aug 16 '14 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.