## N-Queens

### June 11, 2010

We present today a classic exercise that has been on my to-do list since the start of Programming Praxis.

The *n*-queens problem is to find all possible ways to place *n* queens on an *n* × *n* chess board in such a way that no two queens share a row, column, or diagonal. The diagram at right shows one way that can be done on a standard 8 × 8 chess board.

Your task is to write a program to find all such placements. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

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

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

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.

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

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

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)

Another usefull website about the N queens problem is http://sites.google.com/site/nqueensolver/

which has algorithms and executables for download

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)))))

Java implementation:

Source

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

Knuth discusses this in his dancing links paper.

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