June 11, 2010

Here is our solution:

(define (queens n)
  (let loop ((qs (range n 0)) (xs '()) (bs '()))
    (if (null? qs)
        (if (pair? xs) '() (list bs))
          (if (not (safe? (car qs) 1 bs)) '()
            (loop (append (cdr qs) xs) '() (cons (car qs) bs)))
          (loop (cdr qs) (cons (car qs) xs) bs)))))

We build up the board one column at a time, placing the next queen so that it doesn’t attack any queens already on the board. Qs is the list of queens to be placed, xs is a list of queens that failed to place on the current board, and bs is the current board.

Safe? checks the diagonals; there is no need to check columns, since the algorithm places them one after the other, and there is no need to check rows because the list of queens is established at the beginning of the run:

(define (safe? row offset board)
  (or (null? board)
      (and (not (= (+ row offset) (car board)))
           (not (= (- row offset) (car board)))
           (safe? row (+ offset 1) (cdr board)))))

Here’s an example:

> (length (queens 8))
> (queens 5)
((2 4 1 3 5) (3 1 4 2 5) (1 3 5 2 4) (2 5 3 1 4) (5 2 4 1 3)
  (1 4 2 5 3) (5 3 1 4 2) (4 1 3 5 2) (4 2 5 3 1) (3 5 2 4 1))

We used range from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/BL9RmfPM.

Pages: 1 2

13 Responses to “N-Queens”

  1. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/06/11/programming-praxis-n-queens/ for a version with comments):

    import Data.List
    queens :: Int -> [[Int]]
    queens n = filter (safe . zip [1..]) $ permutations [1..n]
    safe :: [(Int, Int)] -> Bool
    safe []     = True
    safe (x:xs) = all (safe' x) xs && safe xs where
        safe' (x1,y1) (x2,y2) = x1+y1 /= x2+y2 && x1-y1 /= x2-y2
  2. […] Praxis – N-Queens By Remco Niemeijer In today’s Programming Praxis we have to solve the classic n-queens problem. The provided Scheme solution has […]

  3. I was trying to make a version that printed and counted, and would fit in 4 lines so you could use it as a .signature file. Didn’t quite succeed, mostly because I need to include to get printf, but here’s where I got it.

    #include <stdio.h>
    int t,i,j,b[8],r;c(){r=1;for(i=0;i<7;i++)for(j=i+1;j<8;j++)r&=(b[i]-b[j]&&abs(i
    -j)!=abs(b[i]-b[j]));return r;}p(){for(i=0;i<8;i++){for(j=0;j<8;j++)putchar(
    " Q"[j==b[i]]);puts("");}puts("");t++;}s(n){int i;if(n--){for(i=8;i;){b[n]=--i;
    s(n);}}else if(c(b))p(b);}main(){s(8);printf("%d solutions.\n",t);}
  4. N = 8

    def valid? stack
    q2 = stack.length – 1
    (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] ||
    (q1-q2).abs == (stack[q1]-stack[q2]).abs

    def queens stack, n
    if n == N
    puts “[ #{stack.join(‘, ‘)} ]”
    (1..N).each do |rank|
    queens(stack, n+1) if valid?(stack)

    queens [], 0

  5. slabounty said

    Here’s a ruby version (commented at http://steamcode.blogspot.com/2010/06/n-queens-problem-in-ruby.html)

    class Board
        def initialize(n)
            @n = n
            @board = Array.new(n)
            @board.map! { Array.new(n, "b") }
        def print_board
            puts "Board:"
            @board.each_index do |row|
                @board.each_index do |col|
        def safe_row(suggested_row)
            0.upto(@n-1) do |col|
                return false if @board[suggested_row][col] == "Q"
            return true
        def safe_col(suggested_col)
            0.upto(@n-1) do |row|
                return false if @board[row][suggested_col] == "Q"
            return true
        def safe_diag(suggested_row, suggested_col, row_mod, col_mod)
            row,col = suggested_row+row_mod, suggested_col+col_mod
            while true do
                break if (row >= @n) || (col >= @n) || (row < 0) || (col < 0)
                return false if @board[row][col] == "Q"
                row += row_mod
                col += col_mod
            return true
        def safe(suggested_row, suggested_col)
            return false if !safe_row(suggested_row)
            return false if !safe_col(suggested_col)
            return false if !safe_diag(suggested_row, suggested_col, 1, 1)
            return false if !safe_diag(suggested_row, suggested_col, 1, -1)
            return false if !safe_diag(suggested_row, suggested_col, -1, 1)
            return false if !safe_diag(suggested_row, suggested_col, -1, -1)
            return true
        def solve
        def solve_1(row)
            0.upto(@n-1) do |col|
                if safe(row, col)
                    @board[row][col] = "Q"
                    if row == (@n-1)
                    @board[row][col] = "b"
    board = Board.new(8).solve
  6. Jos Koot said

    http://en.wikipedia.org/wiki/Eight_queens_puzzle section ‘constructing a solution’ shows an algorithm that is linear in the number of columns of the board when implemented with a vector. It allows you to go to boardsizes up to N=200000000 (I can’t go higher because of memory)

    (define (queens N)
      (if (and (exact-nonnegative-integer? N) (> N 3))
          (let* ((R (remainder N 12))
                 (n-even (floor (/ N 2)))
                 (n-odd (- N n-even))
                 (V (make-vector N))
                 (set-V! (lambda (f r) (vector-set! V f r)))
                 (sema (make-semaphore 0)))
                ((do-loop (syntax-rules ()
                            ((for (x range ...) body ...)
                             (for ((x (in-range range ...))) body ...)))))
               (λ ()
                 (case R
                   ((3 9)
                    (do-loop (F 0 (sub1 n-even)) (set-V! F (+ (* 2 F) 3)))
                    (set-V! (sub1 n-even) 1))
                   (else (do-loop (F 0 n-even) (set-V! F (add1 (* 2 F))))))
                 (semaphore-post sema))) ; Signal completion.
               (λ ()
                 (case R
                    (do-loop (F 2 (- n-odd 1)) (set-V! (+ F n-even) (+ (* 2 F) 2)))
                    (set-V! n-even 2)
                    (set-V! (add1 n-even) 0)
                    (set-V! (sub1 N) 4))
                   ((3 9)
                    (do-loop (F 0 (- n-odd 2)) (set-V! (+ F n-even) (+ (* 2 F) 4)))
                    (set-V! (- N 2) 0)
                    (set-V! (sub1 N) 2))
                    (do-loop (i 0 (sub1 n-odd) 2)
                             (set-V! (+ i n-even) (* 2 (add1 i)))
                             (set-V! (+ i n-even 1) (* 2 i))))
                    (do-loop (F 0 n-odd) (set-V! (+ F n-even) (* 2 F)))))
                 (semaphore-post sema))) ; Signal completion.
              (semaphore-wait sema) ; Wait for both loops to complete.
              (semaphore-wait sema)
          (raise-type-error 'queens "exact integer greater than 3" N)))
  7. Another usefull website about the N queens problem is http://sites.google.com/site/nqueensolver/
    which has algorithms and executables for download

  8. programmingpraxis said

    Here’s a different, somewhat simpler, solution in Scheme:

    (define (attack? q1 q2)
      (or (= (car q1) (car q2))
          (= (cadr q1) (cadr q2))
          (= (abs (- (car q1) (car q2)))
             (abs (- (cadr q1) (cadr q2))))))

    (define (safe? q qs)
      (cond ((null? qs) #t)
            ((attack? q (car qs)) #f)
            (else (safe? q (cdr qs)))))

    (define (queens n)
      (let queen ((n n) (x 1) (y 1) (qs '()) (qss '()))
        (cond ((< n x) (cons (reverse qs) qss))
              ((< n y) qss)
              ((safe? (list x y) qs)
                (queen n x (+ y 1) qs
                  (queen n (+ x 1) 1
                    (cons (list x y) qs) qss)))
              (else (queen n x (+ y 1) qs qss)))))

  9. Ying Yin said

    Java implementation:


  10. simonliu2008 said

    can any one tell me how to convert n-queens problem to exact cover problem?

  11. programmingpraxis said

    Knuth discusses this in his dancing links paper.

  12. […] problem with n queens on an n by n chessboard. After finding it again in older posts on both Programming Praxis and DataGenetics, I decided to go ahead and take a crack at it and I think the solution is pretty […]

  13. Hi I am new to Ruby,I wrote a program in ruby which based on NQueen java program by Robert Sedgewick and Kevin Wayne http://introcs.cs.princeton.edu/java/23recursion/Queens.java.html,The problem is My program is not outputting the result,please help me here
    my program source : http://repl.it/1jv

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 701 other followers

%d bloggers like this: