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))
Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Check this out rosettacode.org/wiki/N-queens_problem#Racket \$\endgroup\$
    – ಠ_ಠ
    Aug 13, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 3:00

1 Answer 1

Reset to default
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)))
Improve this answer
\$\endgroup\$
3
  • \$\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, 2014 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, 2014 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, 2014 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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