N-Queens

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))
        (append
          (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))
92
> (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.

About these ads

Pages: 1 2

12 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
    end
    end

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

    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") }
        end
    
        def print_board
            puts "Board:"
            @board.each_index do |row|
                @board.each_index do |col|
                end
                puts
            end
        end
    
        def safe_row(suggested_row)
            0.upto(@n-1) do |col|
                return false if @board[suggested_row][col] == "Q"
            end
    
            return true
        end
    
        def safe_col(suggested_col)
            0.upto(@n-1) do |row|
                return false if @board[row][suggested_col] == "Q"
            end
    
            return true
        end
    
        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
            end
    
            return true
        end
    
        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
        end
    
        def solve
            solve_1(0)
        end
    
        def solve_1(row)
            0.upto(@n-1) do |col|
                if safe(row, col)
                    @board[row][col] = "Q"
                    if row == (@n-1)
                        print_board
                    else
                        solve_1(row+1)
                    end
                    @board[row][col] = "b"
                end
            end
        end
    end
    
    
    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)))
            (let-syntax
                ((do-loop (syntax-rules ()
                            ((for (x range ...) body ...)
                             (for ((x (in-range range ...))) body ...)))))
              (thread
               (λ ()
                 (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.
              (thread
               (λ ()
                 (case R
                   ((2)
                    (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))
                   ((8)
                    (do-loop (i 0 (sub1 n-odd) 2)
                             (set-V! (+ i n-even) (* 2 (add1 i)))
                             (set-V! (+ i n-even 1) (* 2 i))))
                   (else
                    (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)
              V))
          (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:

    Source

  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 [...]

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

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: